无线传感器网络多路径传输时延优化调度算法研究
2018-07-24虞志刚
赵 晶,虞志刚,冯 旭,陆 洲
(中国电子科学研究院， 北京 100041)
0 引 言
无线通信技术具有低成本、易部署、灵活性高等特征，这些特征使得工业应用与无线传感器网络结合成为应用发展的必然趋势[1-3]。由于工业数据高质量传输的需求，以及恶劣的工业环境带来的挑战，工业无线标准WirelessHART ISA-100.11a、WIA-PA提出数据链路层采用TDMA协议结合信道跳频技术，网络层采用图路由技术，网络采用集中控制模式，集中控制器负责网络通信质量保证、链路层调度和网络层路由确定。采用TDMA协议可以保证端到端传输的确定性时延，其面临的问题是时隙和信道的有效分配。多跳传输网络中，资源调度不仅要考虑链路之间的干扰和冲突，还要考虑路径中链路的次序。
近年来，支持多跳传输的无线传感器网络资源调度算法已经被广泛研究。现有研究已经证明在Mesh网络中实现最短时延调度是NP难问题[4]。文献[5-7]研究的是基于原始数据的资源优化调度方案，文献[8-10]研究的是基于数据融合的资源优化调度方案。在许多工业应用中，由于原始数据的重要性以及数据间相关性差，中心需要接收到每个原始数据。因此，本文设计的调度方案不考虑数据融合。
上述的调度研究大多针对单路径传输，工业标准定义网络采用多路径传输提高网络可靠性，而数据包实际传输过程中仅采用一条路径，其余路径的通信资源将会被浪费。因此，多路径传输的调度方案需进行时延优化以提高资源利用率。文献[11-12]研究的是分布式网络的多路径调度方案，调度算法主要通过节点的信息交互获取可用时隙信道，从而确定调度方案。这种调度方案获取的网络信息是有限的，而集中式控制的网络可以根据网络的全局信息进行优化的资源调度[13-15]。文献[13]将通信过程中多条路径包含的链路罗列，然后为每条链路分配相应的通信资源，这种方案没有进行时延优化，需要大量的通信资源；文献[14]提出了采用时隙重复利用技术以提高资源调度的效率，但是该方案只适用于狭窄的网络结构；文献[15]为每个节点选择冗余下一跳以保证多路径传输，然后通过将数据流分流为不同的下一跳节点分配资源，从而减少调度所需的时隙资源，然而这种调度方案并没有考虑数据重传的情况，链路失效会造成带宽的下降。
本文研究多路径传输时延优化调度算法，主要内容如下：第二章介绍了本文的研究背景，包括采用的通信协议，方案需要考虑的跨层调度原则和两种路由容错机制；第三章给出了网络模型，介绍了文中涉及的变量；第四章简单介绍了之前论文提出的图路由生成算法，基于确定的网络拓扑分别设计了复制机制和重传机制下的资源调度算法；第五章通过仿真说明两种调度算法各自的优劣性；第六章对本文进行了总结。
1 研究背景
WirelessHART作为商用的工业无线标准，定义了工业无线传感器网络的主要组成：集中控制器、无线接入点和现场设备。标准定义数据链路层采用TDMA协议，该协议将时间划分为若干个超帧，超帧进一步划分为若干个时隙，每个时隙可以完成数据包的发送和ACK的接收。工业无线传感器网络中的现场设备为半双工通信，因此，设备不能同时进行数据包的收发。为了避免不同链路之间的干扰，WirelessHART网络不采用空分复用接入(Space Division Multiple Access，SDMA)协议，一个信道在一个时隙内只允许一对通信节点进行数据传输。网络层，工业无线标准提出了图路由协议，每个路由图由图号标识，节点查询图号确定下一跳。图路由协议可以减少数据包开销且支持多路径传输。集中控制器负责网络维护、拓扑信息收集、数据链路层调度和网络层路由图生成以及信息下发。
1.1 跨层调度
在多跳传输中采用TDMA协议，时隙调度需要考虑网络层的路径选择和传输次序，否则会影响数据包传输的时效性，以图1为例，基于跳数的路由度量标准，路径(S→A→B→D)和路径(S→E→F→D)在网络层都是最优的。但是在数据链路层，如果时隙调度没有考虑网络层的路径选择和传输次序，选择路径(S→E→F→D)的数据包经过3个超帧才能到达目的节点，严重影响了传输时延，而路径(S→A→B→D)由于其时隙调度顺序和链路次序相同，使用1个超帧就可以完成数据传输，传输时延小。
图1 资源的跨层调度
1.2 路由的容错机制
无线网络开放的传输介质，以及能力受限的节点不可避免地出现数据包无法成功传输的情况。因此，工业无线标准采用的图路由协议支持多路径传输技术。多路径传输的容错主要有两种机制：复制机制(replication mechanism)和重传机制(retransmission mechanism)[16]。复制机制是将数据包复制多份，通过不同的路径进行传输，从而提高数据的冗余性。这种容错方式实现简单，但是会加大网络负载，造成资源浪费。重传机制基于不同的丢包检测方式可分为逐跳重传(Hop-by-Hop，HbH)和端到端(End-to-End，E2E)重传两种[17]。逐跳重传是指节点发送数据包后一定时间内没有收到下一跳返回的ACK回复则进行数据重传。端到端重传是目的节点负责检测丢包，如果源节点在一定时间内没有收到目的节点的ACK回复则进行数据重传。无线传感器网络中，上层协议相对简单，重传的等待时延不好确定。尤其是支持多跳传输的网络中，端到端的数据包和控制包需要经历多个节点，在无线网络中同样面临很高的丢包风险。而无线网络中单跳的丢包容易确定，重传机制大都采用逐跳重传。
数据链路层的资源调度直接决定了节点的通信行为，不仅要考虑传输路径的选择，还要考虑在数据包发送失败的情况下，数据包的重传方式。基于上述问题的考虑，本文首先给出了路由图的生成算法，然后基于确定的路由图和重传机制，提出了相应的资源调度算法。
2 问题描述
2.1 网络模型
本文研究的是多跳的mesh网络，网络拓扑由G=(V，E)表示，其中V={v0,v1,…,vn}代表现场设备，E代表通信链路。链路ei,j∈E代表节点vi可以给节点vj发送数据包。网络节点vi有多个下一跳节点，由vj1,vj2,…vjn表示。集中控制器生成的路由图由Gg=(Vg，Eg)表示。
2.2 链路度量
路径选择的过程就是节点选择邻居节点的过程，每个节点具有邻居节点集合Mi,vj1,vj2,…vjn∈Mi。qi为邻居节点vj作为vi的转发节点的通信度量值，取决于节点vj的数据传输成功率和能量消耗。节点vj将数据包成功传输到目的节点的传输成功概率为Rj，节点vj的剩余能量为Cj，链路ei,j通信所消耗的能量为Ci,j。
路由容错采用复制机制的情况下，任意数据包到达目的节点即为传输成功，因此，节点的传输成功概率Ri为：
Ri=1-(1-P(i,j1)Rj1)(1-P(i,j2)Rj2)…
(1-P(i,jn)Rjn)
(1)
其中，P(i,j)是链路ei,j成功发送数据包的概率，Rjn为选择邻居节点vjn为转发节点的传输成功概率。
路由容错采用逐跳重传机制的情况下，节点首先向最优下一跳节点发送数据包，如果传输失败，节点选择冗余下一跳进行重传。如果所有的下一跳都没有成功接收数据包，则数据包发送失败。因此，节点的传输成功概率Ri为：
(2)
路由算法选择下一跳，链路度量考虑能耗和传输成功率，具体过程如下：
(3)
(4)
其中，ρ1,ρ2>0。上述的路径度量方式在选择下一跳节点时主要考虑传输成功率和节点剩余能量。同时，参数γ受链路能耗Ci,j影响，节点倾向于选择链路能耗小的节点发送数据包。新的下一跳集合是从邻居节点集合Mi中选出，选择最大化链路度量：
(5)
3 多路径传输资源调度方案
数据链路层的资源调度方案依赖于网络层的路径选择，本节首先介绍了作者之前论文提出的一种路由图生成算法。基于该路由图的生成算法，论文讨论了两种路由容错模式下的多路径传输调度方案，进行了分析对比。
3.1 路由图的生成
算法1路由图生成算法1: G(V,E)为网络图,构建路由图Gg=(Vg,Eg)2: 初始化Vg←vD,fD=1,f=13: Si为节点vi的可用邻居节点集合,SiVg4:∀vj∈Si,vj为节点vi的邻居节点5: 确定Pti,Pti为节点vi的下一跳节点集合, Pti=⌀ 6: whilevi∉Vgdo 7: 寻找集合Si8: if all vi,∀vi∈V-Vg,Si=⌀ then9: 网络不是全联通的10: return FAIL;11: else12: for all vi, vi∈V-Vgdo13: for all vj ,vj∈Sido14: Sort 通信质量qj,考虑已有父节点Pti15: 选择最大化通信质量qi的节点vj为父节点,vj∈Pti16: ifPti=⌀ then17: ri=rj+118: end if19: ifRi≥rridthen20: vi∈Vin,Vin为可靠节点集合 break;21: else ifSi-vj=⌀ then22: vi∈Ven,Ven为不可靠节点集合break;23: else24: Si=Si-vj25: end if26: end for27: end for28: end if29: ifVin≠⌀ then30: 选择节点vi,vi∈Vin,网络等级值ri最小,fi=f+131: 将节点vi加入到Vg,将链路ei,j加入到Eg32: else33: 选择节点vi,vi∈Ven,可靠性Ri最大,fi=f+134: 将节点vi加入到Vg,将链路ei,j加入到Eg
35: end if36: end while37: return SUCCESS;
3.2 多路径传输调度方案
根据算法1，集中控制器可以为一对通信节点选定传输路径生成路由图，然后根据路由图及容错机制为通信过程分配相应的网络资源。以一次通信过程为例，节点S向节点D发送一个数据包，图2(a)所示为节点S到节点D的网络拓扑结构，通过路由图生成算法可得图2(b)中数据包的传输路径。针对多路径传输模式，路由可以采取两种容错机制——复制机制和逐跳重传机制。
图2 通信示例
3.2.1 基于复制机制的多路径传输调度方案
复制机制中，路径中的节点在收到数据包时，如果已经收到过该数据包，则将数据包丢弃；如果没有收到过该数据包，则将数据包以广播的形式发送给多个下一跳节点。因此，数据包传输过程中，路径包含的每个节点只需要一次发送数据包的机会，节点的传输时隙必须早于其下一跳节点的传输时隙，以避免传输次序的紊乱。
以图2中所示通信过程为例，源节点S将数据包同时发送给节点B和节点E；节点B和E收到数据包之后再进行转发，直到目的节点D，过程如图3(a)所示。数据传输过程中，节点多次收到数据包时，仅进行一次转发，如节点F同时收到节点B和节点E发来的数据包，但仅转发一次该数据包。在数据传输过程中，多条路径中的每个节点都可能接收并转发数据包。由于WirelessHART标准定义同一时隙同一信道内仅允许一对通信节点进行数据传输，因此，复制模式下，节点采用广播模式，同一时隙同一信道内仅调度一个节点作为发送节点，如图3(b)所示。
图3 复制模式下资源调度过程
复制机制下，算法2提出了基于节点的资源调度方案。节点调度的次序需要考虑多条路径的传输次序,节点的调度次序取决于路由图的生成算法，先加入路由图的节点不会发送数据包给后加入路由图的节点，因此，先加入路由图的节点的发送时隙也较晚。
算法2基于复制机制的调度算法1: 路由图Gg(Vg,Eg),调度集合为S={vS}2: lev=1;3: while S≠{vD}, do 4: Sort fi, 其中∀vi∈S,5: 选择节点vi , fi最大6: 将时隙k*lF+ASN+lev分配给ST->vi和SR->childi7: 其中lF为超帧长度,ASN为偏移量,childi为节点vi的下一跳节点集合,ST为发送状态,SR为接收状态8: 将集合childi中的节点加入到调度集合S9 end while10:return SUCCESS;
3.2.2 基于重传机制的多路径传输调度方案
重传机制中，节点在数据包发送失败的情况下进行重传，将数据包发送给冗余下一跳节点。如果节点向所有下一跳节点发送数据包失败，则数据包丢弃。由于多条路径中数据包最终仅通过一条路径进行数据传输，链路的使用情况取决于数据包发送成功与否。因此通过不同路径中链路的虚拟共享实现网络资源的优化调度[19]。
以图2中所示通信过程为例，源节点S将数据包首先发送给节点B，如果节点B成功接收数据包，则数据包将被发送给节点C；如果节点B收到数据包失败，则节点S将数据包重新发送给节点E，如图4(a)所示。在第二个时隙内，链路B→C和S→E是在两种条件下发生，因此，这两条链路共享同一时隙信道资源并不会产生冲突，从而减少调度所需的资源。同时，链路F→D在两条路径中出现，一次出现于S→B成功、B→C失败、B→F成功的情况下，另一次出现于S→B失败、S→E成功、E→F成功的情况下。数据包最多可能经过链路F→D一次，因此，这两次链路调度可以合并为一条，从而减少链路的调度次数，延长节点的休眠时间，如图4(b)所示。
重传模式下，算法3给出了基于链路的资源调度方案。算法首先以源节点为根节点，节点指向所有下一跳节点生成路径树，然后基于传输状况遍历路径树，确定链路的传输次序，最后计算路径树的等级数，确定链路调度对应的时隙。由于同一链路在实际传输中最多被使用一次，算法将链路进行了合并优化，最后给出了时隙调度。调度算法分为以下几步：
算法3基于重传机制的调度算法1: 路由图Gg(Vg,Eg),根节点为vD2: ASN=0; //记录调度的时隙数3: 建立传输的调度方案4: CreateTree(vD, Gg, T) ; //基于路由图Gg生成路径树 5: TraverseTree(T) ; //遍历路径树6: lev=1;7: CalculateLevel(T, lev) ; //计算等级数8: OptimalTree(T) ; //优化路径树9: lev=1;10: ScheduleLink(T, lev, F) ; //时隙调度11: return SUCCESS;
图4 重传模式下资源调度过程
(1)生成路径树：基于路由图Gg，以源节点为根节点，记录节点的下一跳节点(有顺序)。路径树的节点为条目t
子算法1 CreateTree(v, Gg, T)1: T=&v;2: CreateTree(T->Ldata, Gg,T);3: CreateTree(T->Rdata, Gg, T);4: return SUCCESS;
(2)遍历路径树：从根节点开始遍历下一跳节点，节点遍历自己的第一个下一跳节点，直到到达目的节点。在遍历过程中，如果树干上还有其他下一跳节点，则将其指向指针改为当前树干节点的下一跳节点。
子算法2 TraverseTree(T)1: 对于任一节点vi,下一跳节点集合为{vj1,vj2,…},下一跳个数为Ni2: TraverseTree(T)3: if T-> vj1, then4: TraverseTree(T-> vj1,)5: end if6: if T->vjn,n≠1 then7: for all n from 2 to Ni do8: T->Lchild->Rchild=T->vjn;9: T->Lchild->Rchild->Rdata = T-> ldata;10: if n≠Nithen11: T->Rchild=vi;12: else13: T->Rchild = NULL;14: end if15: TraverseTree(T->vjn)16: end for17: end if18:return SUCCESS;
(3)计算等级数：遍历路径树，为节点计算并存储等级数。
子算法3CalculateLevel(T, lev)1: lev = 1;2: CalculateLevel(T, lev)3: T->level=lev; 4: level(T->Lchlid, lev+1);//在左子树中查找5: level(T->Rchild, lev+1);//在右子树中查找6: return SUCCESS;
(4)优化路径树：从最高等级开始，遍历路径树，如果等级低的条目的Ldata和Rdata与等级高的条目相同，则等级低的条目可以合并到等级高的条目中去。
子算法4 OptimalTree(T)1: for all lev from L to 0 d2: for all ti , ti
(5)时隙调度：根据优化路径树，为数据传输的链路分配相应的时隙，等级相同的条目可以共享同一时隙。其中，超帧长度为lF，Si记录节点的调度信息。
子算法5ScheduleLink(T, lev, F)1: lev=1;2: ScheduleLink(T, lev, F)3: if T->Lchild != NULL then4: 将时隙k*lF+ASN+lev分配给ST->Ldata和SR->Lchild->Ldata//ASN为该传输在超帧中的偏移量5: end if6: ifT->Rchild != NULL then7: 将时隙k*lF+ASN+lev分配给ST->Rdata和SR->Rchild->Rdata8: end if9: ScheduleLink(T->Lchild, lev+1, F) //遍历左子树10: ScheduleLink(T->Rchild, lev+1, F) //遍历右子树11: return SUCCESS;
4 仿真结果
本节通过MATLAB仿真平台实现多路径传输调度算法，并通过NS-2仿真平台完成网络通信性能的仿真，仿真对比了重传模式和复制模式下多路径资源调度方案的可靠性、实时性和通信开销。实验选择了由100个节点组成的工业无线传感器网络，网络深度为8(网络深度为所有节点中最大的网络等级值)，节点的网络等级值平均为3.94。实验过程为网络中的100个节点都产生一个数据包，然后将数据包发送给集中控制器，路由图由算法1生成，传输成功率参数rd设为0.96，复制模式和重传模式下链路度量的计算方式不同，实验结果为1000次实验的平均值。
图5显示了链路传输成功率从50%增加到90%的情况下，两种调度方案数据包成功到达集中控制器的概率。在采用同样的传输成功率参数rd的情况下，复制模式的数据传输成功率高于重传机制，尤其是在链路传输成功率低的情况下，复制模式的数据传输成功率大大高于重传机制。复制模式以其数据的冗余性，提高了数据包到达集中控制器的概率。
图5 不同路由容错机制的数据传输成功率
图6显示了链路传输成功率从50%增加到90%的情况下，两种调度方案所需要的时隙数目，复制模式所需要的时隙数也小于重传机制。这一方面是由于广播通信模式下资源的共享效率更高，从而减少调度所需的时隙数目；另一方面是由于相同的传输成功率参数，复制模式需要更少的下一跳，从而减少了需要调度的链路数目。
图6 不同路由容错机制的调度时隙数
对比数据传输成功率和调度时隙数这两个参数，复制模式都优于重传模式。然而，数据包传输过程中采用广播模式会造成网络中数据的大量冗余。图7对比了两种模式一次数据汇聚过程的链路通信次数，其中复制模式的链路通信次数大大高于重传模式。大量的通信次数造成节点的计算量增大，节点缓存数据包的增多，节点能量消耗的增加，从而影响网络性能。两种路由容错制机制在不同的性能方面各有优劣，因此，在网络实际部署时，集中控制器可以根据不同的网络需求采用不同的容错机制。
图7 不同路由容错机制的链路通信次数
5 结 语
本文讨论了无线传感器网络中多路径传输时延优化的重要性，考虑了跨层调度的必要性，描述了两种路由容错机制的区别，并针对不同的容错机制提出了两种不同的调度方案。两种方案均通过链路共享时隙资源的方式提高资源的利用率，减少调度所需的时隙数目，从而降低数据包传输的时延。实验结果证明，采用相同的传输成功率参数复制模式的数据传输成功率较高且调度所需的时隙数目较少，但是增大了链路通信次数，从而带来了冗余的数据包，增加了网络负载。因此，在实际部署情况下，可以根据网络的实际需求和应用场景[20]采用不同的路由容错机制。
