无线网络中可靠的链路调度算法设计与分析

张 鑫，张 旭，张入文，于琪琦，王玉霞，韦迎新，黄宝贵

(曲阜师范大学信息科学与工程学院，山东 日照 276800)

0 引 言

无线网络通信技术中一些应用领域对通信的可靠性要求很高，如无线网络工业通信[1-2]、军事通信等。但是信号传输衰落及信号之间的干扰通常会降低网络容量，导致无线通信失败。基于SINR(Signal to Interference plus Noise Ratio)的无线通信链路调度是目前无线网络通信技术中最常用的一种空间复用技术[3-6]，可以解决网络容量和延迟的问题[7-11]，提高空间利用率和通信可靠性。目前链路调度主要分为2大类：1)最大链路调度[12-13]，即最大化单时隙内可以并发调度的链路数目；2)最短链路调度[14-18]，即用最少的时隙调度所有链路。

设计具有SINR约束的链路调度算法是NP难的，SINR干扰模型可以处理全局性干扰[19]，如何控制无线信号之间的干扰是个极具挑战性的问题。基于平面划分的SINR干扰控制是设计链路调度算法常用的一种思路[20-23]，其核心思想是：首先，把通信链路集划分为子集，把网络区域划分为不相交的小区域；然后，从距离较远的小区域中选择链路集合，采用TDMA运行机制，为链路集合分配不同的传输时隙，确保同一时隙中的通信链路在满足SINR干扰约束的条件下同时传输。常用的平面划分有正方形和正六边形划分。Yu等[20]和马春梅等[21]采用了蜂窝移动通信系统的六边形划分法，把网络区域划分为正六边形，从六边形中选取链路集进行调度。文献[20]根据链路长度把通信链路集划分为log (lmax/lmin)个子集，其中lmax是最长链路长度，lmin是最短链路长度。文献[21]则为保证QoS的公平性，不对链路进行分类，而是所有链路一起调度。Huang等[16]采用正方形划分的方法划分网络区域。通常全局性功率分配有一致功率分配和线性功率分配。采用局部功率分配可以优化全局功率分配导致的能量消耗，文献[16]根据链路的长度为链路分配不同的传输功率，减少能量消耗。本文采用正三角形划分的方法，把网络区域划分为不相交的正三角形，将链路放入正三角形中进行调度。首先根据链路的长度把链路集划分为不同的子集，不同的子集把网络区域划分为边长不同的正三角形，然后给正三角形有规律地进行编号，使相邻的三角形具有不同的编号。从编号相同的每个正三角形中选择其中的一条链路进行调度，这些正三角形中的链路就是一个可同时调度的链路集。

1 网络模型及定义

假定一组通信请求为L={l1,l2,l3,…,ln},其中,lv=(sv,rv)(v=1,2,3,…,n)表示从发送端sv到接收端rv的一条通信链路。假设通信节点随机分布在二维平面内。节点sv到rv的欧几里得距离记为d(lv)=d(sv,rv)。本文将最短链路长度归一化，设为1。定义2条链路lv=(sv,rv)和le=(se,re)之间的距离是sv和re的欧几里得距离，即d(lv,le)=d(sv,re)。本文使用一致功率分配，记为P，链路在rv处的接收功率为Prv=P/dα(lv)，α是路径损耗指数(path loss exponent)。如果链路lv=(sv,rv)和链路le=(se,re)同时调度，那么链路le对链路lv的干扰记为Ile(lv)=P/dα(lelv)。在SINR干扰模型中链路lv通信成功，当且仅当：

(1)

成立。其中，N是环境噪声，β是SINR约束条件成立的最小阈值，T为可同时调度的链路集合。如果集合T中任意一条链路都满足式(1)，那么集合T就称为SINR可行集。

本文提出一种基于SINR约束的最短链路调度算法，其目标是：给定一组通信链路集合L={l1,l2,l3，…，ln}，把L划分为数目最少的子集，使每个子集中的链路在SINR干扰约束条件下能够通信成功。即，用最短的时间调度所有的链路。

2 算法设计

2.1 链路分类及平面划分

然后对链路进行分类调度。对于子集Ai，把网络区域划分为边长为μ2i+1(μ是常数)的正三角形。按照如下规则对三角形进行编号：从左上角开始，第一行的编号为5,4,3,6,1,2的重复，第二行的编号为6,1,2,5,4,3的重复，然后重复第一二行的编号过程至平面划分完毕。区域划分及编号结果如图1所示。这样，子集Ai中的所有链路都分布在某个三角形中。如果一条链路的发送端在某个正三角形内，那么这条链路就属于该正三角形区域。

图1 平面划分为正三角形并用数字1到6进行有规则地编号

2.2 算法描述及伪代码

算法1调度伪代码

Input: A set of linksL;

Output:T1,T2,T3，…，Tt;

2:t=0;

3:for eachAi≠∅ do

4:Divide the network area into regular triangles with a side lengthμ2i+1;

5:Number the triangles with number 1, 2, …, 6, such that no neighboring triangles have the same number;

6:forj=1 to 6 do

7:t=t+1,Tt=∅;

8:for each regular triangle B numbered j do

9:pick one linkl∈Aifrom B;

10:Tt=Tt∪{l};

11：Ai=Ai{l};

12:end for

13:end for

14:end for

15:returnT1,T2,T3,…,Tt;

3 理论分析

证明：不失一般性，假设可行集Tt⊆Ai(0i设lv=(sv,rv)∈Tt，rv在三角形A中，A是图2中最中心的编号为1的正三角形。由算法1可知Tt中的其他链路位于其他编号为1的正三角形中(见图2)。以A为中心，第一圈有6个编号为1的正三角形，第二圈有12个编号为1的正三角形，依次递推，第n圈就会有6n个编号为1的正三角形。第一圈三角形中的链路与lv的最小距离为奇数圈的三角形中的链路距离lv的最小距离为偶数圈的三角形中的链路距离lv的最小距离为((3h/2)μ-1)2i+1。因为：

所以链路lv受到的累加干扰最大是：

Irv

图2 可同时调度的链路集

证明：不失一般性，考虑链路的分类集Ai,并且给出发送端属于同一编号的正三角形可以同时调度链路的上限值。假定lv=(sv,rv)∈Ai,最多有M个发送端与rv属于同一正三角形。用OSA表示最佳链路调度算法，它最多可以同时调度一个三角形中的y条链路。接下来，证明y(2μ+1)α2α/β。

反证法:假设在一个正三角形中有超过(2μ+1)α2α/β链路同时调度，根据SINR模型有：

因此，OSA一次最多调度三角形中的(2μ+1)α2α/β条链路，要调度所有M条链路，OSA需要的时隙数(用TOSA表示)必须满足TOSA≥(M/y)。另一方面，假设算法1在Talgorithm1个时隙中调度所有链路，则Talgorithm1所以，Talgorithm1/TOSA其中即，算法1的近似比为

4 实验比较

本文用C++编写程序验证算法1的有效性。网络区域设置为2000 m×2000 m的正方形，链路数目分别是200、400、600、800，最短链路长度归一化为1，最长链路长度设置为30，环境噪声为-70 dB，α=3，β=10 dB。文献[22]把平面划分为正方形并用1、2、3、4编号，其算法记为Blough；文献[20]把平面划分为六边形并用1、2、3编号，有2种功率分配策略，分别是与链路类相关的功率分配和一致功率分配。比较一致功率分配下的算法结果，记为YuUni。Blough和YuUni是2种典型的平面划分方案。本文算法记为Zhang，这3种算法的实验结果如图3所示。

图3 3种典型平面划分算法的比较结果

从图3可以看出，与其它2种方法相比，本文算法的性能更优。文献[22]算法中的“灰黑链路”对链路调度的延迟有明显的影响，平均调度次数最大。本文算法与文献[20]性能相当。虽然文献[20]使用六边形划分，用3种不同的编号，但是六边形的边长较大；本文使用正三角形划分，用6种不同的编号，三角形的边长较小。对于相同的链路类来说，编号相同的三角形的数目是六边形数目的1.14倍。所以，在同一时隙，从三角形中选择的链路的数目是从六边形中选择的链路的数目的1.14倍，调度相同数目的链路时本文所用的时间更短。

5 结束语

SINR模型的全局干扰特性使得设计一个可靠性很强的低延迟链路调度是NP难的。本文首先根据链路长度划分链路集，然后由正三角形划分法进一步划分子集，通过研究子集内可同时调度的链路得到链路可行集。同时利用了SINR模型可累计干扰的特点，采用TDMA运行机制避免干扰。由于SINR模型适用于网络中的动态链路，所以未来研究的方向可以根据链路的长度和数目，使链路的调度有一个动态变化，以在保证低耗的情况下解决链路内部的干扰问题，从而有效提高功率分配及传输信号的可靠性。