无线通信网络分布式调度的复杂性

摘要：在无线通信网络中，调度通常是以分布式方式进行的，并且需要通过无线信道来进行信息交换。文章根据完成调度所需的通信位数，研究分布式调度的通信开销。并在完整连接图的特殊情况下，使用通信复杂性理论来推导相应下限，从而提出实用的广播协议来完成分布式调度。

关键词：通信复杂性；分布式调度；无线通信网络

无线通信网络中并非所有的节点都可以同时传输信号。因此，确定可在干扰限制内进行传输链路的调度非常重要。文献[6]中提出了多跳网络中的调度策略，该策略实现了能够稳定数据流量的容量区域（吞吐量最佳）。最近，研究热点已经转移到分布式调度上，这在adhoc网络[7]中更加合理。许多调度算法都是基于某些优先级权重的比较。目前大多数文献简单地让发射机广播其权重，并允许具有最高优先级的发射机进行传输。但发送器仅需要知道它们是否具有最高权重并获得发送权，无需完全了解其他节点的优先权重，缺乏了分布式调度最小开销的研究。在本文中，首先考虑广播网络中基于优先级比较的分布式调度所需的通信位数，从而进行分布式调度开销的研究。并且采用交流复杂性理论[8]，假设A有一个数字x，而B有另一个数字y；A和B需要共同计算函数f（x，y）。通信复杂度定义为在A和B之间对于计算f的任何协议交换的最小位数。x和y表示优先权重，f（x，y）=I（x≥y）。当f（x，y）=1时，A传输;否则B传输；此时假设在x=y时，A传输。然后，利用通信复杂性理论中的工具分析调度的开销，但也不限于此；其次给出了一些背景知识。主要研究包括第三节和第四节中介绍的无错误和可容错的案例；最后总结全文。整篇文章使用以下数学符号：表示向量X的第k个元素。

1调度和通信的复杂性

假设在无线通信网络中有N个传输链路，用1，...，N标记。在每个数据帧中的数据传输之前设置一个前同步码周期。每个发送器都有一个整数值，范围从1到q（假设对于数据n，q=2n），并且用i表示链路i的优先权重。在前同步码周期中，发送器广播其优先权重的部分信息进行调度。其中被确定为具有最高优先级的链路获得传输权。假设前同步码使用TDMA结构，如图1所示。对于前导码和调度，有以下假设：（a）没有从发送切换到接收或者接收切换到发射的周转时间；（b）广播的顺序取决于广播的历史记录（某些节点可以在整个过程结束之前退出广播）；（c）每个节点在一个时隙仅广播一位[2]，具体取决于广播历史记录和该节点的值；为简化问题，我们假设使用开关键控（OOK）；（d）网络连接图完整，这意味着所有节点都可以解码所有广播；（e）权重{i}在给定范围内均匀分布。定义（优先权重相同时，随机发送）。本节研究了分布式计算函数f的通信复杂度，并且考虑了两种类型的度量标准[3]（关于所有可能的输入）：（a）在最坏情况下的最小通信位数，用表示；（b）用表示通信比特的最小平均数。如文献[8]中的两节点情况，每个通信协议都可以由一个二叉树表示，其中每个叶代表一个输出。决策过程等效于从根到叶的遍历（图2）。参照两节点矩形的概念，在N节点情况下定义一个超级矩形：定义1：如果中的区域X称为超矩形，其中是[1：q]的子集。如果f（x）对于所有点x∈X都是相同的，我们将X称为单色超矩形（相对于f）。容易验证协议树的每个叶节点是否对应于输入域中的单色超矩形，该矩形的每个点都导致相同的广播序列和该给定协议的最终输出。分别用L和Rl表示叶子节点的集合和对应于叶子l的超矩形。

2无错误的情况

本节主要研究没有调度错误情况下的通信复杂性。

2.1的下限

假设当多个节点达到最高权重时，任何输出都是正确的（当q足够大时，此类事件的概率可以忽略不计）。采用文献[2]的方法，并使用与其中的节点广播的比特序列。[1:q]N中的每个输入都与广播历史关联，得到如下定义：定义2：如果[1:q]N中的两个点（由v1和v2表示）满足以下两个条件，则将这两个点称为冲突对：（a）这两个点的调度输出相同，即s表示该函数；（b）存在j=1或2以及k，使得。示例1：对于N=4和q=8，v1=（4，3，2，1）和v2=（8，7，6，5）是一个冲突对，此时。根据冲突对的定义，证明以下引理：引理1：如果在完成协议时有冲突的对具有相同的广播历史记录，则调度输出中将存在错误。证明：假设节点2具有更高的优先级，并且两个节点都具有相同的广播历史记录。在时隙t上进行归纳，可以证明节点1将确定其具有最高优先级，从而导致调度错误。基于引理1，获得了最坏情况下的通信复杂性的下限：命题1：基于优先权重比较的调度最坏情况下的通信复杂度由下限来限定：（1）证明：可以将[1:q]N的不同点处的广播历史视为颜色。根据引理1，任何冲突的对都不能具有相同的颜色。可以通过得出颜色数量的下限来得出结论。

2.2和的上限

本节提出了一种实现分布式调度的方案，为通信复杂性提供了上限。（1）算法：使用二进制搜索在[1:q]N中定位一个点。描述如下：算法1：在整个过程中更新了两个数据结构：[ak：bk]表示第k轮的搜索间隔，Sk表示通过先前的比较保留的节点集。回合0（初始化）：设置和。回合k：如果[ak：bk]之间只有一个整数并且|Sk|>1，有两个或多个节点达到最高权重，此时该算法随机选择一个链接。否则Sk中的所有节点将按顺序广播。对于节点j∈Sk，如果，它将广播1，否则广播0（是节点j的权重）。在所有节点都完成了第k轮的广播之后，该算法将采取以下三个设a，；（b）如果有多个节点广播1，则设Sk+1为广播1的节点集，当N=2且q=4时，上述算法总结在图2的协议树中，其中0（1）表示节点1（2）拥有传输权，如果1=2，假设节点2拥有传输权。（2）最坏情况复杂度：很容易验证最坏情况发生在（q，q-1…，q-1）4处，其中通信复杂度由给出，比得出的下限大得多；因此需要缩小差距。

3容错情况

调度错误的概率很小，可以用仅降低边际性能为代价，大大降低通信的复杂性，因此该研究允许调度错误的情况。当可容忍的错误概率为时，用表示最坏情况的最小通信位数，用P（x）表示点x处的容错协议的输出，可能不同于f（x）。

3.1下限

关于的下限。（1）基于差异的下限：在这种情况下，使用文献[5]中的差异方法来获得通信复杂性的下限。定义3：对于任何超矩形R，R的差异定义为：，其中P是与文献[5]中的提案3.28类似，基于差异的概念，可以得到下限。

3.2上限

本节提出了一个实用的算法，用于的上限。对于分布式调度算法，在需要多个通信位的情况下，可以选择一个随机链路进行传输。假设一些常见的随机性可用于所有链接[3]。则可以用算法1，除了在第一轮比较后有超过k*个用户保留时，协议停止，并且通过通用随机性选择幸存者中的一个。

4结语

图3显示了在无错误和可容错（=0.1）的情况下从公式（2）和（6）中的递归不等式获得的。可以观察到，在N中几乎线性增加，而在n中增加缓慢，根据观察，当允许某些调度错误时，可以大大减少所需的通信开销。图4显示了在可容许的错误概率（0.05或0.15）下，根据提案3中的差异方法获得的最坏情况下的通信复杂度的下限，可以观察到下限相对于N是非线性的。此外每个节点的平均位数小于1。因为某些节点发现自己的优先级无法与其他节点竞争时它们不会传输任何信息。本文使用通信复杂性理论分析了无线网络中分布式调度所需的通信位数。当调度基于优先权重比较并且网络具有完整的连接图时，研究得到了上限和下限。但仍然存在许多未解决的问题，如任意网络拓扑、通用调度协议以及周转时间的影响。

作者：左晨微 单位：郑州工商学院