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

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

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

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）如果有多个节点广播1，则设Sk+1为广播1的节点集，设a，；（b）如果有多个节点广播1，则设Sk+1为广播1的节点集，设；（c）如果所有节点都广播0，则设以及。当N=2且q=4时，上述算法总结在图2的协议树中，其中0（1）表示节点1（2）拥有传输权，如果1=2，假设节点2拥有传输权。图2N=2，q=4时协议树的图示（2）最坏情况复杂度：很容易验证最坏情况发生在（q，q-1…，q-1）4处，其中通信复杂度由给出，比得出的下限大得多；因此需要缩小差距。（3）平均复杂度：使用表示该协议下交换比特的平均数量。当N=2时，容易验证。这也意味着如果。因此，初始条件意味着。对于通用N，递归计算平均通信位。显然。假设权重分布均匀，对于N个用户，第k个用户在第一轮保留的概率为满足下列递归不等式：（2）基于公式（2），我们可以得到以下平均复杂度的上限：命题2：对于任何n和N，都有。

3容错情况

调度错误的概率很小，可以用仅降低边际性能为代价，大大降低通信的复杂性，因此该研究允许调度错误的情况。当可容忍的错误概率为时，用表示最坏情况的最小通信位数，用P（x）表示点x处的容错协议的输出，可能不同于f（x）。3.1下限关于的下限。（1）基于差异的下限：在这种情况下，使用文献[5]中的差异方法来获得通信复杂性的下限。定义3：对于任何超矩形R，R的差异定义为：，其中P是权重在中的概率函数（假设为统一）。整个网络的差异定义为。显然，Df为正，因为对于单个点，（对于某些情况下的R，Df（R）可能为负）。与文献[5]中的提案3.28类似，基于差异的概念，可以得到下限。命题3：对于，通信复杂度的下限可以表示为：（3）证明：考虑任何复杂度为且错误概率小于或等于的协议，有。通过分析上述不等式中的二进制协议树和上限概率得出结论。（2）差异的计算：以下引理显示了超级矩形获得最大差异的必要条件。引理2：如果超矩形R的差异最大，则存在一个点和一个i，使得：（4）其中只有第i个间隔不同，且。证明：假设R达到最大差异，并表示为，其中的子集。进一步定义和。则有。由于对称性，假设i=1，其中i在引理2中定义，而不会失去一般性。当N足够大时，很难找到达到最大差异Df的精确超矩形。在考虑组合问题变成连续问题的渐近情况（即q→∞）。将范围[1:q]标准化为连续间隔[0，1]。那么对于满足的超矩形，差异可以有下列表达式表示：（5）当N=2时，。通过使微分等于零，最优点由和给出。当N>2时，可以通过数值最大化利用公式（5）来获得差异。图3平均通信复杂度的上限图4容错调度程序中的通信复杂性的下限3.2上限本节提出了一个实用的算法，用于的上限。对于分布式调度算法，在需要多个通信位的情况下，可以选择一个随机链路进行传输。假设一些常见的随机性可用于所有链接[3]。则可以用算法1，除了在第一轮比较后有超过k*个用户保留时，协议停止，并且通过通用随机性选择幸存者中的一个。显然k*满足。该算法通信位数的平均值的上限：（6）.

4结语

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

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