链路相关性感知的无线传感器网络多播路由协议

姚 磊，沈 航，白光伟，徐佳佳

1(南京工业大学 计算机科学与技术学院，南京 211816)2(南京大学 计算机软件新技术国家重点实验室，南京 210093)3(南京邮电大学 通信与网络技术国家工程研究中心，南京 210003)

1 引 言

无线传感器网络(Wireless Sensor Network，WSN)是一种无线多跳自组织网络.节点通过电池供电，能量有限，因此，在无线传感器网络通信协议的设计过程中，如何节约能量、提高网络生命周期始终是研究人员关注的焦点[16-18].根据应用场景来划分，可以将传感器网络应用划分为四种场景：

1)单源到单汇聚点(Single-Source to Single-Sink，SSSS)[5]；

2)多源到单汇聚点(Multi-Source to Single-Sink，MSSS)[6]；

3)单源到多汇聚点(Single-Source to Multi -Sink，SSMS)；

4)多源到多汇聚点(Multi -Source to Multi -Sink，MSMS).

Brute Force(BF)和FCMN[7]是解决SSMS路由问题的典型方案，这两种方案都建立在链路独立的假设上进行路由设计的.

然而，大量文献[1-4,10,15]表明同一个源节点的无线链路之间并不是相互独立的，不同接收节点收到的数据包之间存在相关性.文献[15]分析了相关性产生的原因，一个是相关干扰，即现有无线技术基本都在工作在不需要授权的2.4GHz频段.这就导致高功率网络容易对低功率网络产生干扰，使低功率链路的丢包率更高.另一个是阴影效应，由于障碍物的存在，无线信号在传播过程中受到其影响，从而使链路丢包.文献[10]利用链路相关性提高洪泛的效率，降低了洪泛过程30%的转发次数.考虑到链路相关性的影响，有必要重新设计无线传感器网络多播路由协议.

本文提出链路相关性感知的无线传感器网络多播路由协议(LMR)，目的是减少多播路由中参与转发节点的数目，延长传感器网络的生命周期.多播节点将汇聚节点进行分团，根据位置信息计算合适的中继区域.转发节点利用反相关链路对进行机会转发，提高候选节点集中至少有一个节点能够收到数据包进行转发的概率.多播节点利用正相关链路对进行数据复制，增加下一跳节点同时接收到数据包的可能性.实验结果表明，LMR协议能有效减少转发节点数量，延长无线传感器网络的生命周期.

2 相关工作

链路相关性由Srinivasan[1]等人率先提出.此后，大量文献[2-4,12,15]验证了链路相关性的存在.目前，链路相关性研究主要集中在三个方面：1)洪泛[2,10,11]；2)机会路由[1,12]；3)网络编码[1,13,14].

2.1 链路相关性感知的协议

CF[2]利用累积ACKs机制减少了洪泛产生的ACK数量，将相关性较高的节点聚集在一起让它们同时接收源节点的广播包，减少了聚合中ACK的数目，降低了ACK风暴出现的可能性.

机会路由在数据包头部包含一个简单的进度表来描述潜在可以转发数据包接收者的优先顺序.接收者按照该优先顺序对数据包进行转发，即优先级最高的接收者最先转发数据包，优先级低的节点转发高优先级节点未转发的数据包.传统路由协议在数据包发送前确定转发节点，而机会路由在数据转发过程中动态选定最佳转发节点.机会路由充分利用无线网络的广播特性，提高无线网络的吞吐率.文献[8]等对机会路由进行了研究，但都是基于链路独立的假设，此时，候选节点的选择及优先级序列只与包接收率有关.文献[1]在基于链路相关的假设下对机会路由进行研究，分析不同相关性程度下转发节点的选择情况，进一步提升了无线网络吞吐率.

2.2 无线传感器网络多播路由

在WSN中，传感器节点采集到的数据信息被多个汇聚节点需求.例如：森林中传感器节点收集到的温度和湿度信息，需要发送给温度控制中心用来关注动植物的生活环境，同时也需要发送给火灾中心监控火灾的发生.

在无线传感器网络中，节点由干电池供电，而且大多部署在无人值守区域，在工作时充电或更换电源是不现实的.因此，节点能量受到电池寿命的限制.然而，很多应用场景要求传感器节点能长时间连续工作，这就要求传感器网络路由协议能节省节点能量.

关于解决SSMS问题的路由协议，近年来已经有了一些解决方案.Brute Force(BF)[6]使用SSSS的方法解决SSMS问题，对每一个汇聚点生成一条最短路径.该方案将SSMS问题分解为多个单源单汇聚节点问题，为每个汇聚节点生成一条路径.如图1所示，节点之间的虚线即是该方案为每个汇聚节点生成的最短路径.这些路径对于相应的汇聚节点来说是最优选择，但是从整体上考虑，该方案一共使用16个节点进行数据转发，增加了传感器网络的负担.为缓解BF方案能量消耗过大问题，FCMN方案[7]通过合并多个汇聚点的最短路径，使用跳数累加器选择下一跳节点，来节省数据传输过程的能耗.如图1所示，节点间的实线是FCMN生成的路径，只有12个节点参与并完成数据转发，从整体上减少了能耗.然而，该方案为全部汇聚节点分配了相同的优先级，导致数据多播节点出现在路径末端，数据分发后，转发节点需求量增加.

图1 多播路径及单播路径Fig.1 Multicast vs.unicast path

3 研究动机

首先介绍链路相关性的度量指标，接着分析链路相关性对无线网络数据传输性能的影响.

图2 链路数据接收相关性Fig.2 Correlation between packets received

3.1 链路相关性度量

链路相关性提出后，链路相关性的度量[15]成为业界研究的重点.下面介绍几种常见的衡量链路相关性性能的指标：1)条件包接收比[2]；2)互条件概率[9]；3)互相关指标[1]；4)归一化指标[1].

归一化指标是一个三元标量，如图2所示，t是发送节点，x和y两个随机变量分别对应两条链路t-x、t-y收包状况.x和y只有两个值：0表示丢包，1表示收包，因此x，y都服从伯努利分布.κ用公式

(1)

表示.κ的取值范围为[-1，1]，不同κ值反映链路对的相关程度.κ=0表示链路独立，κ>0表示链路对成正相关，κ<0表示链路对成反相关，κ=1表示链路对完全正相关，κ=-1表示链路对完全反相关.式中，

(2)

(3)

3.2 链路相关性对数据传输的影响

图2中，节点t同时对节点x、y、z进行广播，链路数据包接收率分别为0.7、0.6、0.4.

考虑节点t使用机会路由转发数据包到节点d1的情况.如果只考虑链路质量，则选择节点x和节点y作为候选节点，因为这两个节点的链路质量较高.但是如果考虑到链路相关性的影响，节点x和节点y，完全正相关，节点x未接收到的数据包节点y同样丢失，将这两个节点同时放在候选节点集中并不能减少节点t的传输次数.但是，选择反相关链路对接收节点x和z作为候选节点，能有效减少节点t的传输次数，因为节点x未接收到的数据包可以由节点z进行转发.虽然节点z丢包率比节点y高，但是，节点t发送一个数据包，节点x和节点z中必定有一个接收到数据包并进行转发.

考虑节点t为需要将数据包同时转发给节点d1和节点d2的情况.选择节点x和节点y作为中继节点，需要的传输次数为：

(4)

4 问题描述

这里将WSN形式化为一个有向图G=(V， E)，V表示全部节点的集合，E表示这些节点通信链路的集合，如图3所示.|V|和|E|分别表示节点数量和链路数量.

图3 LMR路径Fig.3 LMR path

低功耗的802.11无线传感器网络为环境监测提供了便利，网络中节点的位置信息根据信标节点的位置信息，通过定位算法确定.信标节点是指位置信息已知的节点，一般所占比例很小，通常配备 GPS 接收器或通过人工设置来获取自身的位置信息.

拟解决的最佳多播路径(Optimal Multicast Path，OMP)问题被建模为：

Minimize：

(5)

Subject to：

(6)

(7)

(8)

对于m从1到|D|的每一个目标汇聚节点，都存在一条路径，每一条路径都需要满足上面的约束条件.本文旨在减少参与转发的节点数量，从而减少能耗.

定理1.OMP问题为NP-hard问题.

证明：考虑这个问题的一个特殊情形，当只有一个汇聚节点时，这个问题就变成在有向图G(V，E)中，已知起始节点和终止节点，寻找最短路径的问题.最短路径问题的NP-hard是众所周知的，所以，OMP问题也是NP-hard问题.

针对OMP问题，本文提出了链路相关性感知的无线传感器网络多播路由协议.

5 路由设计

节点的位置信息已通过定位算法获得.WSN初始化阶段，汇聚节点将自己的位置信息广播给所有汇聚节点.节点的传输半径为设备提供的有效传输距离.LMR依据位置信息进行路由决策.路由的总体设计如下：

1)将目标汇聚节点集合进行分团，并计算分团的中继区域.对于当前发送节点来说，部分汇聚节点的路径可以合并.源节点将全部汇聚节点分解为多个可以合并路径的团.图3中的Source节点将三个汇聚节点分为一个团，并计算到中继区域为E1.

2)通过机会路由方式将数据包传输到中继区域边缘.图3中，Source节点将数据包传输到节点H1.

3)多播发送节点选择.数据包传输到中继区域边缘时，节点选择在区域内的节点进行数据包的分发.图3中，H1节点选择R1节点作为多播发送节点.

4)多播接收节点选择.多播发送节点接收到数据包后，选择合适的接收节点进行多播.同时，多播发送节点作为新数据包源节点多汇聚节点进行分团操作.转步骤1.

由于传感器网络中节点的存储能力受到限制，不能获取并保存整体网络拓扑，所以路由过程是分布式进行的.下面的内容将介绍分布式LMR协议的具体实现.

5.1 多播中继区域选择

图3中源节点的目标汇聚节点包括Sink1，Sink2和Sink3.源节点对全部目标节点进行分析，可以将哪些节点进行组合，让这些节点使用相同的路径进行数据传输.本节介绍目标汇聚节点组合的条件，并介绍对目标汇聚节点集进行分团的策略.

将源节点定义为发送节点s，其目标汇聚节点Sink1和Sink2分别定义为节点A和节点B，定义L(s,A)为节点s和节点A之间的距离.则如图4所示，寻找点m，使得L(s,m)+L(B,m)+L(A,m)的值最小.

图4 中继中心选择Fig.4 Relay center selection

当点m是三角形sAB的费马点时，L(s,m)+L(B,m)+L(A,m)最小.此时，m点的相对于s的位置可通过公式

(9)

确定.

用无向图G′(V,E)来表示当前发送节点的分团图.V(G′)表示当前发送节点的目标汇聚节点集合，E(G′)表示汇聚节点之间存在中继中心.Ri,j=1表示当前发送节点与汇聚节点vi,vj之间存在可用中继中心.

V(G′)={vivi∈D}

(10)

E(G′)={(vi，vj∈V(G′))|i≠j，Ri，j=1}

(11)

汇聚节点的位置信息在路由初始化阶段由汇聚节点广播给整个网络并由全部节点保存，节点自身的位置信息通过定位算法确定，通过公式(9)和节点的传输距离可以确定Ri,j的值.

在给定的图G′中，寻找没有交集的团.AG′为图的邻接矩阵，xi=1表示该节点被当前团选中.

Minimize：

f(x)=xT(AG′-I)x

(12)

Subject to：

s.t.x∈{0，1}n

(13)

使用贪心算法，将可以使用同一条路径进行数据包传输的目标汇聚节点组成一个团，这些目标汇聚节点使用相同的节点进行数据传输，减少参与转发的节点数量.

算法1.分团策略

1Input:G′,s

2Output:C,N

3G←G′,n←1

4whilei>0

5C(n)←maxClique(E(G));

6V(G)←{vi|vi∈V(G)∪vi∉C(n)}

7E(G)←{(vi,vj∈V(G))|i≠j};

8i←i-|C(n)|,n←n+1;

9endwhile

10forj←1:n

11if(|C(j)|=1)

12N(j)←C(j);

13else

14foreachk,l∈C(j),k≠1

16endfor

18N(j)←t;

19endif

20endfor

21return{C,N}

通过算法1将汇聚节点组合成团后，若团中包含多个目标汇聚节点，则计算每一个节点对之间M点的位置，取其中距离发送节点最近的一个最为目标位置.

在寻找到适合的中继中心之后，为确保有节点可以被选择到，以这个中心为圆心，节点传输距离为半径，将计算得到的中继中心扩展为一个中继区域.

节点R1经过计算发现，Sink1和Sink2可以共用相同的节点进行数据传输，Sink2和Sink3可以共用相同的路径进行数据传输.根据算法1，LMR将Sink1和Sink2划分为一个团，Sink3单独成团.对第一个团计算得到中继中心E2，数据包由R1传输到E2，E2将数据包进行多播；对第二个单节点团，直接进行机会转发.

5.2 面向多播中继区域的机会转发

转发节点分析数据包头中目标中继区域的位置信息，根据自身位置信息选择合适的下一跳节点进行数据包转发.

本文提出的无线传感器网络多播路由协议，采用链路相关性感知的机会路由进行数据包转发.定义发送节点s的邻居节点集为NS，目标位置为d，当前节点进行机会路由的候选节点集合为F.考虑F中只有两个候选节点的情况，转发节点的消耗为：

(14)

其中，α=f(s,f1,d)表示，使用F中链路质量较高的节点f1进行数据转发的传输次数估计，使用

(15)

β表示候选节点f1没有转发数据包的情况下，节点f2接收到数据包并转发的概率：

(16)

则E(s，F，d)表示源节点s发送一个数据包，通过候选节点集F传输到目标位置的理论传输次数.

5.3 多播发送节点选择

图3中，当源节点的数据包被传输到节点H1时，下一跳节点出现在中继区域内部.此时，节点H1需要在其邻居节点集合中选择合适的节点作为多播发送节点.

(17)

其中Ri∈NH1，且Ri在中继区域内.Ck表示当前目标团C中第k个汇聚节点的位置信息.取URi最大值对应的节点Ri作为多播节点进行数据分发.

节点H1选择节点R1作为多播节点进行数据包多播.节点R1接收到数据包，首先对目标汇聚节点进行分团操作.节点R1将汇聚节点Sink1和节点Sink2分在同一个新团中，中继区域为以E2为圆心的虚线圆圈.Sink3与另外两个节点不能进行组合，R1节点将Sink3单独作为一个团进行数据传输.

5.4 多播接收节点选择

确定了所有分团的目标位置后，需要选择合适的节点作为数据接收节点进行数据包多播.为了减少发送节点的重传次数，倾向于选择正相关链路对进行数据包的多播.多播节点的消耗为：

(18)

根据公式(3)，如果选取链路质量为κ的一对链路作为接收节点，则节点R1的传输次数可以用计算获得.

(19)

节点R1选择算法2计算得到的接收节点集合Na和Nb作为数据接收节点进行数据包的发送.

算法2.多播接收节点选择

1Input:F1,F2

2Output:Na,Nb

3ET←∞

4foreacha∈F1

5foreachb∈F2

6ifE(R1,a,b)

7Na←a;

8Nb←b;

9ET←E(R1，a，b)

10endif

11endfor

12endfor

6 实验与结果分析

本节通过MATLAB仿真实验对链路相关性感知的无线传感器网络多播路由协议进行性能分析，汇聚节点分布在感知节点的四周，采用100个数据采集节点进行实验.实验采用低功耗的802.11协议进行仿真，其参数设置如表1所示，实验与FCMN和BF进行比较.

表1 实验参数Table 1 Experimental parameters

6.1 参与转发节点数量

图5显示相比于FCMN和BF， LMR方案参与转发的节点较少.BF为每一个汇聚节点生成一条最短路径，n个汇聚节点对应n条相互独立的路径.这种方案从整个网络拓扑来看，更多的节点参与到数据转发过程中.FCMN使用跳数累加器进行路由选择，数据包转发到跳数累加器最小的节点处进行一次数据包的多播，但当汇聚节点分布情况不理想时，FCMN方案将会产生数据包回传现象.LMR方案对汇聚节点进行分团，对同一个团内的汇聚节点使用相同的路径进行数据传输，相较于BF参与转发的节点较少.当团中有节点不适合与其他节点一起组团时，将该节点单独进行路由，避免数据包回传现象的发生.

图5 转发节点数量Fig.5 Number of forwarding nodes

6.2 节点存活时间

图6(a)给出了不同方案下10%节点的平均存活时间，LMR节点的存活时间更长.这是因为LMR和FCMN对路径进行了合并，相比于BF，未参与转发节点的能量被节省了.由于数据包回传现象，FCMN协议不稳定.LMR在进行数据传输的时候使用了链路相关性感知的机会转发，尽量选择反相关链路对，提升候选节点集接收到数据包的概率，减少了发送节点的传输次数，节省了数据发送的能耗.

图6 节点存活时间Fig.6 Node survival time

图6(b)表示在一次模拟过程中，节点死亡率随时间的变化.BF中的节点最先出现死亡现象，LMR中的节点死亡最晚.这是由于BF中的节点参与转发更频繁，能量消耗更快.FCMN和LMR合并了一部分链路，节省了未转发节点的能量.LMR相较于FCMN加入了链路相关性，进一步减少发送节点重传次数，节省数据发送的能耗.

6.3 分布密度的影响

从图7中可以看出，随着节点密度的增加，三种协议的转发节点数量都有所下降，节点存活时间增加.随着节点密度的增加，可选择下一跳转发节点的数量增加，源节点能选择传输距离更远的节点进行传输，减少转发节点数量.同时，源节点可以选择能量充裕的节点进行转发，平衡节点的能耗，延长传感器网络的生命周期.

图7 节点密度的影响Fig.7 Impact of node density

BF使用暴力算法，以每一个汇聚节点为根生成最短路径，相较于其他的协议需要更多节点进行数据转发.LMR和FCMN均在BF的基础上对路径进行了合并，减少了路由中需要的节点数量.LMR在路由中对链路相关性加以利用，减少了转发次数和节点的能耗，延长了无线传感器网络的生命周期.

7 总 结

本文提出了链路相关性感知的无线传感器网络多播路由，将传感器网络多播路由中的节点分为多播节点和转发节点.多播节点对汇聚节点进行分团，对每一个分团的中继区域进行数据包多播；转发节点使用链路相关性感知的机会转发进行数据包传输.仿真实验结果表明，LMR减少了参与转发的节点数量，有效延长了无线传感器网络的生命周期.