一种基于SINR干扰模型的能量有效的链路调度方法

摘要

本发明公开了一种基于SINR干扰模型的能量有效的链路调度方法，对于一个以Sink为根节点的树型网络结构，每条链路的负载量已知，该方法按照链路负载量从小到大的顺序给链路分配时隙，对于相同负载量的链路，按照干扰度降序排序；在给某条负载量为load的链路分配时隙时，从初始时隙开始，寻找一个连续的load个时隙，使得该链路与这些时隙中已分配的链路间满足SINR要求。由于拥有load个负载量的链路分配到连续的load个时隙，减小了节点的状态转换次数，减少了网络能耗；对于每个转发节点，输出链路时隙在输入链路时隙之后到来，使得数据收集过程在一个TDMA帧中完成，减小了全网数据收集时延。

说明书

技术领域

本发明涉及一种基于SINR干扰模型的能量有效的链路调度方法，可以用于事件的持续监测和周期性的信息报告的无线传感器网络应用系统。

背景技术

无线传感器网络^[1](Wireless Sensor Network，WSN)是一种由大量传感器节点组成的无线自组织网络系统。这些传感节点被抛撒在监测区域内，采集和处理监测区域内的各种信息，并通过无线多跳方式传输给监测中心Sink。基于树的数据收集是无线传感器网络数据收集的传递方式之一，即将网络中的所有节点组成一棵以汇聚节点为根节点的树型网络结构，节点在传递数据时沿着事先建立好的树型网络结构通过多跳方式发送给汇聚节点。

Time Division Multiple Access(TDMA)是WSN的一种多址接入方式。基于TDMA的MAC协议具有避免冲突的优势。TDMA协议将时间划分成众多时隙，并将这些时隙分配给网络中所有链路，链路上的节点在分配的时隙内打开收发机，在其他时隙内关闭收发机，降低节点的能耗。如果需要传输多个数据量的链路分配的时隙不连续，则节点需要多次开启，在时隙结束后关闭。节点开启时间为毫秒级，当所传数据较小时，数据传输时间小于节点开启时间^[2]。频繁的开启和关闭一个节点，不仅会消耗更多的节点能量，也会增加数据收集时延，因此，在对WSN中的链路进行调度时，需要考虑减小节点的状态转换次数。

假设节点没有数据融合功能，TDMA的每个时隙允许传输单位数据量。对于一个转发节点，它有一条输出链路和多条输入链路，输出链路的数据量为该节点产生的数据和所有输入链路的数据量之和，因此输出链路需要多个时隙来传输数据。假设在分配给某个节点的输出链路时隙中，存在一些时隙，在输入链路时隙之前到来，则在数据收集阶段，在一个TDMA帧内有部分数据没有得到转发；需要在下一个TDMA帧中对应的输出链路时隙中转发数据。这种情况下Sink需要两个TDMA帧才能收集完网内所有节点的数据。

SINR干扰模型是一种常用的无线干扰模型。在该模型中，对于某一时隙中的一组链路，通过调整每条链路的发射功率，判断是否存在一组发射功率，使得每条链路上的接收节点的SINR值均大于一定阈值。如果不存在可行性发射功率，则需要重新分配该时隙中的链路，再次进行功率控制。如此循环，直到存在一组链路和一组对应的发射功率，使得这组链路满足SINR要求。

现有技术存在多种链路调度算法，下面给出两种常用的方案，对其特点和优缺点加以说明。

方案一

文献[3]提出了一种基于SINR的链路调度算法，其特点在于对于每个转发节点，当其数据转发缓冲区内有数据时，才给其分配一个时隙来转发数据。该方案由两个模块组成：①调度模块；②功率控制模块。具体实现过程如下：

(1)初始阶段：每个节点维护一个变量：buffer。如果某个节点有一个数据包待发送，则其buffer为full，否则为empty。初始每个节点的buffer为full。如果某个节点的buffer为empty，但是其某个子节点的buffer为full，则该节点处于活跃状态。初始时隙t＝1。

(2)在时隙t中，从与Sink相连且buffer为full的节点中，选取总负载量或剩余负载量最大的节点i，将链路(i,Sink)加入到待调度链路子集合A中；对于网络中处于活跃状态的节点node，随机选取一个buffer为full的子节点c，将链路(c,node)加入到待调度链路子集合A中。当待调度链路子集合为空时，算法结束。

(3)使用文献[4]中的功率控制算法处理步骤(2)中的待调度链路子集合A，主要是迭代寻找是否存在可行发射功率。在每次迭代过程中，根据每条链路的当前SINR值来确定下一次迭代过程中的发射功率，如式(1)所示，其中，β为SINR阈值。

$P_{\mathrm{new}}=\frac{\beta }{\mathrm{SINR}}*P_{\mathrm{current}}---\left(1\right)$

如果存在一组发射功率，使得该待调度链路子集合A中，所有链路的SINR值大于β，则t＝t+1，进入步骤(2)；如果迭代次数结束后，不存在一组发射功率，使得集合A中的链路SINR值大于β，则去除集合A中SINR值最小的链路，进入步骤(3)。

该方案存在如下缺陷：

1、每个节点的buffer为1或0，即最多有一个数据包等待发送。假如节点的buffer为full，且在时隙t内发送数据，则该节点对应的子节点不可能在t内发送数据；在t+1时隙内，节点的buffer为empty，该节点的子节点有机会发送数据；至少要在t+2时隙内，该节点的buffer才会为full，可以再次分配到时隙。因此链路分配到的时隙不会是连续的。

2、对于某条链路，只有它的发送节点的buffer为full，接收节点的buffer为empty，它才有可能加入到待调度链路子集合A中，限制了可选择的链路，减小了可同时调度的链路个数，使得时隙总数增加，增加了全网数据收集时延。

方案二

文献[5]提出了一种基于干扰图的链路调度算法。该算法利用非负矩阵最大特征值Perron-Frobenius定理^[6]来判断一组链路是否满足SINR要求。Perron-Frobenius定理如下：对于n条没有公共节点的一组链路，定义如式的n×n的矩阵G：

$G=\left(\begin{array}{cccc}0& \frac{g\left(\mathrm{2,1}\right)}{g\left(\mathrm{1,1}\right)}& ...& \frac{g(n,1)}{g\left(\mathrm{1,1}\right)}\\ \frac{g\left(\mathrm{1,2}\right)}{g\left(\mathrm{2,2}\right)}& 0& ...& \frac{g(n,2)}{g\left(\mathrm{2,2}\right)}\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ \frac{g(1,n)}{g(n,n)}& \frac{g(2,n)}{g(n,n)}& ...& 0\end{array}\right)$

其中，g(i,i)为第i条链路的信道增益，g(j,i)(i≠j)为第j条链路的发送节点到第i条链路的接收节点的信道增益。

假设ρ(G)为矩阵G的最大实特征值(或称Perron-Frobenius特征值半径)：

①当所有接收端的噪声p_noise为0时，当且仅当ρ(G)的倒数大于SINR阈值α时，即 时，上述n条链路可以分配在同一个时隙中。ρ(G)对应的任意正Perron特征向量均可为该组链路的发射功率向量P；

②当接收端噪声p_noise不可忽略时，当时，上述n条链路可以分配在同一个时隙中。此时的功率向量P_n＝c*P。这里的c为一个常数，满足下式：

$c\ge \underset{m\in n}{\max }\left\{\frac{{\mathrm{noise}}_m}{g(m,m)({\alpha }^{-1}-\rho \left(G\right))p_m}\right\}$

其中，noise_m为链路m的接收端噪声，p_m为链路m的发送功率。

方案二的具体实现过程如下：

(1)初始阶段：针对已有的数据收集树，构建一个干扰图。每条链路的权重为该链路的干扰度和负载量之和。sumd为所有链路的负载量之和。St为时隙t内所有链路的集合。初始时隙t＝1。

(2)如果sumd>0，将网络中所有需要分配时隙的链路按照权重值降序排序T’。对于T’中每一条链路m，如果St∪m中所有链路在干扰图中不相连，并且存在可行性发射功率，则将m加入到St中，m的负载量减1。如果sumd＝0，该方案结束。

(3)给St中所有链路分配功率Ut，更新干扰图、链路权重值及sumd值。t＝t+1，进入步骤(2)。

该方案存在如下缺陷：

1、对于某条链路m，假设给其分配了一个时隙t。在时隙t+1中，给需要分配时隙的链路按权重值排序，选取权重值最大的链路m’，判断m’是否可以分配在t+1中。链路m’有可能不是m，使得链路m分配到的时隙不连续。

2、在时隙t中，按照需要分配时隙的链路的权重值，优先选取权重值最大的链路加入到时隙t中。对于一个转发节点，其输出链路的负载量较大，优先给输出链路分配时隙，使得输出链路时隙在输入链路时隙之前到来时，增加了全网数据收集时延。

关键术语定义

全网数据收集时延：汇聚节点收集网络中所有传感节点的数据需要的时隙总数。

干扰图：干扰图中的顶点为已有数据收集树的链路；如果不存在一组发射功率，使两条链路分配在同一时隙中，则这两条链路在干扰图中对应的顶点相连。

干扰度：某条链路的干扰度为在干扰图中，与该链路对应顶点相连的边的个数。

负载量：某条链路的负载量为该发送节点感知的单位数据量和该链路需要转发的数据量之和。

参考文献

[1]Ian F.Akyildiz,and Mehmet Can Vuran,Wireless Sensor Networks---Advanced Texts in Communications and Networking(John Wiley&Sons Press,2010),pp.9-10. 

[2]Wang A,Cho S H,Sodini C,et al.Energy efficient modulation and MAC for asymmetric RF microsensor systems[C].Proceedings of the 2001international symposium on Low power electronics and design.ACM,2001:106-111. 

[3]Incel O D,Ghosh A,Krishnamachari B,et al.Fast data collection in tree-based wireless sensor networks[J].Mobile Computing,IEEE Transactions on,2012,11(1):86-99. 

[4]T.ElBatt,and A.Ephremides,Joint Scheduling and Power Control for Wireless Ad-Hoc Networks[J],Proc.IEEE INFOCOM,pp.976-984,2002. 

[5]Gong D,and Yang Y.Low-latency SINR-based data gathering in wireless sensor networks[C],INFOCOM,2013Proceedings IEEE.IEEE,2013:1941-1949. 

[6]Matchin Borbash S A,and Ephremides A,The feasibility of matchings in a wireless network[J].IEEE/ACM Transactions on Networking(TON),2006,14(SI):2749-2755. 

发明内容

发明目的：针对WSN树型网络结构的链路调度过程中具有多个负载量的链路分配的时隙不连续，没有确保当转发节点的输入链路时隙后，在当前TDMA帧中存在相应的输出链路时隙来转发数据，从而增加节点状态转换能耗，全网数据收集时延较长等问题，提出一种基于SINR干扰模型的能量有效的链路调度方法，该方法在链路调度过程中，优先给负载量小的链路分配时隙，对于相同负载量的链路，优先给干扰度大的链路分配时隙；在给某条负载量为load的链路分配时隙时，从初始时隙开始，寻找连续的load个时隙，使得该链路与该load个时隙中已分配的链路间满足SINR要求。该方案减小了全网数据收集需要的总时隙数，同时也减小了节点状态转换次数，减小网络总能量。

技术方案：为实现上述目的，本发明采用的技术方案为：

一种基于SINR干扰模型的能量有效的链路调度方法，采用Perron-Frobenius定理来判断一组链路能否在同一个时隙中传输数据，对于一个以Sink为根节点的树型网络结构，每条链路的负载量已知，该方法按照链路负载量从小到大的顺序给链路分配时隙，对于相同负载量的链路，按照干扰度降序排序；在给某条负载量为load的链路分配时隙时，从初始时隙开始，寻找一个连续的load个时隙，使得该链路与这些时隙中已分配的链路间满足SINR要求。由于拥有load个负载量的链路分配到连续的load个时隙，减小了节点的状态转换次数，减少了网络能耗；对于每个转发节点，输出链路时隙在输入链路时隙之后到来，使得数据收集过程在一个TDMA帧中完成，减小了全网数据收集时延。该方法具体包括如下步骤：

步骤1：初始化阶段：针对已有的数据收集树，构建干扰图；

S_t为在时隙t内的链路集合，初始值为空集；

P_t为时隙t内链路的发射功率集合，初始值为空集；

load(m)为链路m的负载量； 

步骤2：链路排序阶段：将Sink的所有子树按照其根节点的负载量升序排序；对于负载量相同的子树，按照其根节点的干扰度降序排序；排序后的序列为T，T_i为T中第i个子树，初始时i＝1；进入步骤3；

步骤3：将T_i中所有链路按照负载量升序排序；对于负载量相同的链路，按照干扰度降序排序；T_i对应的链路序列为Q_i，链路m为Q_i中的第m条链路，初始时m＝1；进入步骤4；

步骤4：选择链路m的初始时隙：如果链路m不存在输入链路，则初始时隙t＝1；否则， 初始时隙t＝输入链路分配到的最大时隙数+1；进入步骤5；

步骤5：对链路m寻找连续时隙：在时隙t内，如果链路集合S_t∪m同时满足以下两个条件则进入步骤6，否则进入步骤8，这两个条件为：①对于该链路集合中的任意两条链路，在干扰图中，对应的顶点不相连；②所有链路存在可行的发射功率；

步骤6：如果链路m在时隙t之前分配到时隙t'，并且时隙t与t'不连续，则从已分配给链路m的所有时隙对应的链路集合中删除链路m，load(m)恢复原值；进入步骤7；

步骤7：时隙t分配给链路m，令S_t＝S_t∪m，load(m)＝load(m)-1；进入步骤8；

步骤8：t＝t+1；如果load(m)>0，表明链路m仍需要分配时隙，则进入步骤5；否则，判断Q_i中是否有链路需要分配时隙，如果存在，令m为Q_i中下一条链路，即m＝m+1，进入步骤4；如果Q_i中没有链路需要分配时隙，则进入步骤9；

步骤9：如果存在子树没有分配时隙，令i＝i+1，即T_i为T中下一棵子树；进入步骤3；否则，输出每个时隙t对应的链路集合S_t，并利用Perron-Frobenius定理求出S_t对应的发射功率集合P_t，该方案结束。

有益效果：本发明提供的基于SINR干扰模型的能量有效的链路调度方法，具有如下优点：1、对于网络中所有的转发节点，其对应的输入链路时隙均在其输出链路时隙之前到来，使得全网数据收集只需在一个TDMA帧内就可以完成，减小了全网数据收集时延；2、对于网络中所有链路，给其分配连续的对应负载量的时隙，减小节点的状态转换次数。

附图说明

表1已有数据收集树的第一棵子树的时隙分配表；

表2已有数据收集树的时隙分配表；

图1基于SINR干扰模型的能量有效的链路调度方法流程图；

图2数据收集树示意图；箭头代表数据流向，箭头旁的数字代表链路的负载量；

图3数据收集树对应的干扰图；

图4三种方案的全网数据收集总时隙数的性能仿真图；

图5三种方案的节点平均状态转换次数的性能仿真图；

图6三种方案的全网数据收集总能耗的性能仿真图。

具体实施方式

下面结合附图对本发明作更进一步的说明。

实施例采用的数据收集树如图2所示。实施例的仿真平台为MATLAB2012b。传感节点随机分布在500×500m2的感知区域内。最大的发送功率为-10dBm，高斯白噪声功率为-97dBm。路径损耗指数为3。

基于SINR干扰模型的能量有效的链路调度方法的具体实施例包含以下步骤：

步骤1：根据已有的数据收集树(图2)，构建干扰图(图3)，S_t和P_t均为空集。

步骤2：将Sink的所有子树按照其根节点的负载量升序排序；对于负载量相同的子树，按照其根节点的干扰度降序排序；排序后的序列T为：a、d。

步骤3：T₁为以a为根节点的子树，对应的链路序列Q₁为{(c,a),(b,a),(a,sink)}，当以a为根节点的子树中所有链路已分配时隙，对应的时隙表如表1所示；T₂为以d为根节点的子树，对应的链路序列Q₂为{(f,e),(e,d),(d,sink)}。

表1 已有数据收集树的第一棵子树的时隙分配表

时隙 链路 1 (c,a) 2 (b,a) 3 (a,sink) 4 (a,sink) 5 (a,sink)

步骤4：当链路m为链路(f,e)时，由于链路m不存在相应的输入链路，则初始时隙t＝1；当(f,e)分配了时隙1后，链路m为链路(e,d)，存在相应的输入链路(f,e)，则初始时隙t＝输入链路(f,e)分配到的最大时隙+1，即2。

步骤5：在时隙t内，如果S_t∪m中所有链路不冲突且存在可行的发射功率，比如链路(e,d)在时隙t＝2处，由于S_t∪m＝{(b,a),(e,d)}，这两条链路不冲突且存在可行的发射功率，则进入步骤6；否则，比如链路(e,d)在时隙t＝3处，由于S_t∪m＝{(a,sink),(e,d)}，这两条链路不存在可行的发射功率，则进入步骤8。

步骤:6：如果链路m在时隙t之前分配到时隙t'，并且时隙t与t'不连续,比如链路(e,d)已分配了时隙2后，下一个满足步骤5的时隙为6，由于时隙6和时隙2不连续，则从时隙2中删除链路(e,d)，load(e,d)恢复原值2。

步骤7：链路m可分配在时隙t中，令S_t＝S_t∪m，load(m)＝load(m)-1；比如链路(e,d)在时隙t＝2处，S₂＝{(b,a),(e,d)}，load(e,d)＝1。

步骤8：t＝t+1。如果load(m)>0，表明链路m还需要分配时隙，则进入步骤5，比如在时隙3内，load(e,d)＝＝1，链路(e,d)还需分配一个时隙，进入步骤5。否则，判断Q_i中是否有链路需要分配时隙，如果存在链路需要分配时隙，比如load(f,e)＝0，load(e,d)>0，进入步骤4；如果Q_i中所有链路均分配到时隙，比如load(a,sink)＝0，表明以a为根节点的子树中所有链路已分配了时隙，则进入步骤9。

步骤9：如果存在子树没有分配时隙，比如以d为根节点的子树还没有分配时隙，则T_i为以d为根节点的子树；进入步骤3；否则，根据S_t求出P_t，并输出S_t和P_t，该方案结束。

图2中的数据收集树的时隙分配表如表2所示。

表2 已有数据收集树的时隙分配表

时隙 链路 1 (c,a)(f,e) 2 (b,a) 3 (a,sink) 4 (a,sink) 5 (a,sink) 6 (e,d) 7 (e,d) 8 (d,sink) 9 (d,sink) 10 (d,sink)

在该实施例设置的同样实验场景，网络节点个数在100～200，分别对现有技术方案一、现有技术方案二、本发明技术方案的不同性能进行了仿真比较。图4是三种方案在全网数据收集时隙总数目的性能比较；图5是三种方案在节点状态转换次数的性能比较；图6是三种方案全网总能耗的性能比较。

以上所述仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。