一种基于能量均衡的地理路由协议设计

贾新春,张俊丽,池小波

(山西大学 数学科学学院,山西 太原 030006)

一种基于能量均衡的地理路由协议设计

贾新春,张俊丽,池小波

(山西大学 数学科学学院,山西 太原 030006)

针对无线传感器网络中无线链路不稳定与节点能耗不均衡等问题,提出一种基于能量均衡的地理路由协议。在路径构建阶段,为了避免传统地理路由中贪婪转发引起的某些节点过度使用,文章将簇作为数据传输的基本单元,并对节点设置能量阈值。在路由度量选择时,综合考虑簇内节点数目和簇中心到汇聚节点的距离,以便均衡簇间节点能量消耗。在数据传输阶段,利用协同通信与网络编码技术提高数据传输可靠性。最后,理论分析与数值实验同时表明:所提协议能够显著地提高数据包传输成功率,减少数据包重传次数。

无线传感器网络; 地理路由协议; 网络编码; 可靠性; 能量均衡

0 引言

无线传感器网络(WSNs)是由大量具有感知,计算和通信能力的微型传感器节点通过无线通信方式形成的一个多跳,自组织的网络系统[1]。通常被部署在长期无人值守的区域,恶劣复杂的工作环境对WSNs通信可靠性提出挑战,并且网络中节点能量消耗不均也导致部分节点过早死亡,降低网络生存时间。因此,如何设计一个可靠,高效的路由协议成为一个挑战性的问题[2-3]。

2000年Ahlswede等人首次提出网络编码的概念[4],改变了传统通信网络中节点只对收到的信息存储与转发的模式,允许中间节点对接收到的数据包进行编码处理,以少量数据包冗余避免数据包重传的同时降低网络因节点故障或失效对网络鲁棒性的影响[5]。许多研究者开始利用网络编码技术提高网络可靠性与鲁棒性。文献[6]研究了存在节点故障的无线传感器网络中基于随机网络编码的可靠协同通信,通过网络编码与协同通信技术提高网络抵御节点故障,链路失败的能力,但忽略路径与簇的构建过程。文献[7]研究了一种基于网络编码的簇级多路径路由,通过对传统多路径路由协议的改进,建立了以簇为单位的多路径路由,利用路径冗余和网络编码提高了数据包传输可靠性,但是以簇为单位的多路径路由要求网络具有较高的节点密度。文献[8]研究了多媒体无线传感器网络瓶颈区域的节能机制,结合占空比与网络编码技术降低瓶颈区域节点能量消耗,达到均衡网络中节点能量消耗的目的。文献[9]提出一种基于地理信息的能量均衡路由算法,通过约束下一跳节点的转发空间来控制不重要的数据包传输,并综合考虑四种度量因素选择下一跳转发节点,均衡候选转发空间中节点的能耗,但其没有考虑网络在数据传输方面的可靠性。

基于地理位置信息的路由协议广泛应用于WSNs,通常利用贪婪转发方法作为数据发送机制,节点总是选择其邻居节点中离汇聚节点最近的节点作为其下一跳节点。由于路由准则单一,某些节点可能被频繁选为中继节点转发数据包,导致节点间能量消耗不均衡,严重影响网络的性能[10]。为此,结合协同通信与网络编码技术,提出一种以簇为单位的路由协议,节点利用地理位置信息实现虚拟网格分簇[11]。簇内节点根据剩余能量与能量阈值选择簇头节点与参与数据传输的节点。考虑到簇中剩余能量大于能量阈值的节点数目不同可能会造成簇间节点能量消耗不均衡的现象,综合利用簇内剩余能量大于阈值的节点数目与到汇聚节点的距离构建代价函数,作为路由度量选择下一跳簇,改善贪婪转发因路由准则固定而导致网络中某些节点过早死亡的现象, 均衡网络中节点能量消耗。最后,提出两种网络性能的度量:数据包传输成功率(SDR)与标准化能量消耗(T)。并通过Matlab数值实验对比分析了所提协议与传统单路径及不相交多路径路由之间的性能差异。

1 网络模型与假设

Fig.1 Network model图1 网络模型

Source与Sink节点分别部署于编号为1和15的网格,Source负责收集数据,将数据包以组划分,并对每组数据包先随机网络编码再发送到下一跳节点。中继节点具有相同的计算与通信能力,且不执行数据采集,对其接收到的数据包重新随机编码后发送到下一跳节点,直到数据包传输到汇聚节点,Sink节点对收到的数据包进行解码,获得原始数据包。

为了便于研究,作如下合理假设:1)所有传感器节点部署后无法移动;2)节点当且仅当能量耗尽才会死亡;3)节点可通过GPS或定位算法获得自身地理坐标。

2 基于能量均衡的地理路由协议(EBGR)

路由协议负责将分组数据包从源节点通过网络转发到汇聚节点,它主要包括两方面功能:寻找源节点到目的节点的优化路径,将数据沿着优化路径正确转发[12]。EBGR协议的主要思想:为了均衡簇内与簇间节点能量消耗,在簇头选择与路径构建阶段,簇内节点综合考虑其剩余能量和到网格中心距离构建代价函数选择簇头,并以簇内活跃节点数目与相邻两跳节点前进距离作为路由度量选择最佳的下一跳簇。在数据传输阶段,簇内节点通过协同通信与网络编码技术降低网络因节点故障或链路失效引起的数据传输不可靠。

2.1 簇头选择

初始时刻,每个传感器节点都具有相同能量E,选择离网格中心位置最近的节点作为簇头。由于簇头节点负责数据传输的同时参与路径构建过程,能量消耗较快,每经过T轮数据传输,将重新选择簇头节点。

首先,节点根据自身剩余能量决定是否参与到簇头节点选择阶段,如果剩余能量大于阈值e,将参与竞争簇头与数据传输阶段。簇内节点以TDMA方式广播NODE-MSG报文并将其存储到Nei-LIST,报文包含本节点的节点编号(node-ID),位置信息(x,y),网格编号(C-ID)与节点剩余能量(Eres),当其余节点收到报文时,检验报文中包含的C-ID是否与自身网格编号相同,如果节点与收到的报文C-ID相同,表示节点属于同一簇,则将报文存储到Nei-LIST中,否则,直接丢弃。根据节点能耗公式[13],节点数据传输能量消耗随通信距离呈指数增长,为了避免相邻两跳簇头节点距离过远而造成节点能耗过多,簇头节点应分布趋于网格中心[14]。综合考虑节点剩余能量与其到网格中心距离选择簇头节点,节点i优先级度量为αi(见(1)),每个节点根据Nei-LIST对αi降序排序,排在首位的节点将充当簇头节点。显然,节点剩余能量越多,离网格中心位置距离越近,αi值越大,被选为簇头的优先级越高。节点获得度量值排序后,根据时槽大小确定是否参与发送数据及其发送数据的时槽队列,比如,时槽个数Nα为5,节点排序所得优先级为6,节点将不参与数据传输,只有优先级排序大于Nα的节点才参与数据传输。节点优先级度量αi计算公式如下:

(1)

2.2 路径构建

路由发现由汇聚节点发起,每个簇头节点广播CLU-MSG报文,报文中应包含本簇中能量大于阈值e的节点数目n,网格中心位置信息C(x,y),其通信范围内的每个簇头节点或汇聚节点把收到的报文信息存储在CLU-LIST中。在数据传输之前,每个簇头节点或汇聚节点先检验其CLU-LIST中,是否有源节点所在簇的信息,只有源节点不在簇头节点或汇聚节点的一跳范围内才进行度量值计算与选择最佳下一跳簇。

首先,汇聚节点广播路由包REED,REED包含当前节点(CurID),源节点所在簇(SCID),汇聚节点(DID)与下一跳簇(NexCID)的信息。贪婪转发是地理路由常用的数据包转发方法,选择离汇聚节点最近的节点作为下一跳,贪婪转发路由准则单一常导致部分节点因过度使用而能量耗尽,为了均衡网络中各簇间节点能量消耗,避免某些簇中节点因过度使用而过早死亡,综合考虑簇内剩余能量比e大的节点数目与到汇聚节点的距离作为度量值βi(见(2))。每个接收到REED的节点检验NexCID是否与自身CID相同,不一致的节点直接丢弃REED,其余节点将存储路由包。然后,簇头节点,根据收到REED中CLU-LIST信息计算下一跳节点,簇头更新REED中当前节点的信息CurID与所选择的下一跳簇的NexCID。依照以上方式广播路由包继续寻找最佳的下一跳簇,直到簇头节点CLU-LIST中包含源节点所在簇的信息,直接选定源节点为其下一跳,路径构建完成。

路径构建过程阶段,簇头节点或汇聚节点利用CLU-LIST中节点数目n与网格位置C(x,y)计算度量值βi,显然,n与C(x,y)值越大,被选为下一跳簇的优先级越高。选择具有最大值βi的簇作为下一跳簇。

(2)

其中,γ为权重因子,可根据具体应用需求来选择。ni,Di分别为簇i的度量值,簇内剩余能量比i大的节点数目,网格i中心到汇聚节点的距离。N为大于ni的常数。D表示源节点与汇聚节点之间的距离。

2.3 数据传输

在传统网络中,中继节点负责向下游节点转发接收到的数据包,在EBGR协议中,中继节点需要对收到的数据包先随机网络编码产生新的数据包,再转发到下一簇。如图2所示,首先,Source对收集到的数据以组划分,每组包含K个数据包,并对分组后的K个数据包进行随机线性网络编码,为了提高数据传输成功率,编码生成K′个数据包(K′>K),并连续发送给下一簇节点。然后,簇中每个节点根据对收到的数据包进行随机网络编码后,以TDMA方式传输给下一簇中节点,直到数据包传输到Sink。最后,汇聚节点对收到的数据包进行解码。

Fig.2 Date transmission model of EBGR图2 EBGR数据传输模型

2.3.1 源节点编码

源节点将需要发送的同组K个数据包进行随机线性组合生成新的编码后的数据包:

(3)

其中,Pj,j∈(1,2,…,K)为原始数据包,aij为取自伽罗华域的随机系数,Ci为编码后的数据包,编码向量vi=(ai1,ai2,…,aiK)将被封装于数据包。为了增加数据传输可靠性,源节点增加数据包冗余,生成的K′(K′>K)个新的数据包,并连续发送到下一跳簇中。

2.3.2 转发簇节点再编码

中继节点收到多个来自上一簇中节点发送的数据包时,将对其进行再编码转发:

(4)

Cr，vr分别是相应的编码后新的数据包和编码向量,bri表示转发簇中节点在伽罗华域随机生成的编码系数,Ci为转发簇中某个节点收到的数据包。

为了避免簇内节点数据传输相互干扰与冲突,采用TDMA的方式进行数据传输。时槽个数为Nα,当ni≥Nα时,节点根据度量值β的优先级排序确定数据发送时槽,只有β排序在前Nα的节点参与数据转发,网络运行一段时间,可能出现类似情况:簇内能够参与到数据传输的节点数目nin时(TS表示时槽缩写),簇内节点对收到的数据包重新编码并按照度量值排序(如图3)依次传输新的数据包,直到满足所要求的Nα.例如ni=4,TS=5时,x=(TS modni)=1.x为节点度量值βi的排序值。

Fig.3 Time slot queue图3 时槽队列

2.3.3 汇聚节点解码

汇聚节点接受完数据包时,将根据收到的数据包和相应的编码向量将对其进行解码

(5)

是数据包相应的编码向量。

当且仅当rank(VS)≥K运用高斯消去方法,我们就可以用下式成功获得原始的数据包。

(6)

Cs=(C1,C2,…,CN)T为Sink节点收到的n个数据包。

3 性能分析

在无线传感器网络中,可靠数据传输,节约节点能量与延长网络生存周期是路由设计考虑的主要因素,在本节我们给出了所提协议数据传输可靠性与节点能量消耗高效性的度量并对其进行理论分析。

3.1 数据包传输成功率

为了描述无线传感器网络数据传输可靠性,我们定义了一种度量:传输K个数据包的成功传输率SDR.也就是在一轮数据传输过程中,汇聚节点能够解码出原始数据包的概率:

(7)

其中,pi表示第i跳数据包传输成功率,H表示源节点到汇聚节点的跳数。

在基于网络编码的数据包传输网络中,汇聚节点需要对收到的数据包进行解码,才能得到原始数据,只有收到不小于K个线性无关数据包时,Sink节点才能解码出原始数据包。文献[15]研究了收到数据包个数与汇聚节点解码率的关系,令p(n,k)表示收到n个数据包,能成功解码原始数据包的概率,即在伽罗华域随机生成n×k矩阵,其秩大于k的概率为:

(8)

其中,q为伽罗华域的大小,当伽罗华域足够大时,p(n,k)→1,即当q足够大,只要Sink接收到n≥k个数据包,可看作原始数据包被成功接收。因而,在研究数据包传输成功率时,我们忽略解码率对SDR的影响。

(9)

(10)

(11)

3.2 标准化能量消耗

由于节点能量消耗与其数据包传输次数成比例,为了便于不同协议之间的比较,我们把每传输K个数据包所需的传输次数与K个数据包传输成功率SDR比值作为标准化能量消耗的一种度量:

(12)

在一轮数据传输过程中,传输K个数据包所需的数据包传输次数包括源节点发送的编码数据包数目K′与转发簇中所需传输的数据包个数(H-1)Nα,显然,n与K′,H,Nα及n都有关,K′,H与Nα越大,n越大,n越小,n越大,即成功传输n数据包所需的传输次数越多,节点标准化能量消耗越多。

4 数值仿真实验

基于以上理论分析,针对基于能量均衡的地理路由(EBGR),传统单路径(TS),不相交多路径路由(DM)协议在数据包传输成功率(SDR),标准化能量消耗(T)两方面的性能进行仿真实验对比。分别研究了三种协议误码率(BitErrorRate),跳数H,簇内传输数据包数目Nα,源节点发送数据包数目K′对SDR与T的影响。首先作如下参数设置:L=1024bits,L-head=48bits,K=3,K′=5.

4.1 跳数,误码率对数据包传输成功率,标准化能量消耗的影响

为了比较跳数对三种不同协议可靠性的影响,分析比较在传输K=3个数据包情况下,H与BitErrorRate分别对SDR与T的影响。对于不相交多路径协议,路径数设置为Nα.NC(见图4,5)表示在数据传输阶段运用网络编码技术的EBGR协议。

Fig.4 Successful delivery rate图4 数据包传输成功率

Fig.5 Normalized energy consumption图5 标准化能量消耗

图4和图5描述了三种协议在SDR分别为3,6,9时,误码率与SDR,Ln(T)的关系。显然,随着误码率的递增,三种协议SDR与T分别呈现下降与上升趋势,这是由于误码率增加降低数据包传输成功率,从而导致满足相同SDR需要传输的数据包次数增多。当固定H,可以发现,EBGR比TS,DM具有更高的数据包传输成功率,更低的标准化能量消耗。从协议角度分析,TS与DM随着误码率的递增,SDR呈现较快的下降趋势,Ln(T)呈现较快的上升趋势。反之,随着误码率递增,EBGR中SDR与Ln(T)变化较平缓。并且,与其它两种路由相比,H的改变对EBGR的SDR与Ln(T)影响较小。因而,EBGR在较差网络环境,长距离的数据传输情况下具有较高可靠性,较低的标准化能量消耗。

4.2 簇内节点发送数据包数目对数据包传输成功率,标准化能量消耗的影响

簇内节点发送数据包数目与每跳数据包传输可靠性有直接关系。如图6,我们研究了H=6,误码率为1.5×10-3时,Nα与SDR的关系。随着Nα增加,数据包传输成功率呈现上升趋势,尤其当Nα≥7时,SDR接近于1,而Ln(T)呈现先下降后上升趋势。因而,可以根据实际需要的可靠性选择合适的Nα,满足可靠性要求情况下,尽量减少标准化能量消耗。

Fig.6 Number of K′图6 簇内发送数据包数目

Fig.7 Number of K′图7 源节点编码数据包数目

4.3 源节点发送数据包数目对数据包传输成功率,标准化能量消耗的影响

源节点发送编码数据包的数目直接影响第一跳数据包传输可靠性,图7研究了原始数据包K=3,源节点编码发送数据包数目K′与SDR,Ln(T)的关系。显然,当源节点发送K′=K=3个数据包时,具有最小的SDR值与最大的Ln(T)值,随着源节点发送数据包增多,其数据包传输成功率增大,标准化能量消耗减少,但是,当数据包冗余达到一定阈值时,SDR与Ln(T)都不会有明显变化。因而,通过在源节点发送冗余数据包可以在一定程度上增加数据包传输成功率,减少标准化能量消耗,但过多的数据包冗余对增加数据包传输成功率,减小标准化能量消耗影响较小。因此,可以根据具体网络参数来选择冗余数据包,满足可靠性的同时尽量减少标准化能量消耗。

5 结论

无线链路不稳定性与节点能量消耗不均匀,使得无线传感器网络的路由设计成为一个挑战性问题。基于现有文献的研究成果, 本文提出了一种基于能量均衡的地理路由协议。在簇头选择与路径构建阶段, 综合考虑节点剩余能量,地理位置信息与到汇聚节点距离来选择簇头节点与下一跳簇,均衡网络中节点能量消耗。在数据传输阶段,簇内节点通过协同通信与网络编码技术改善网络因节点故障,链路失效引起的数据传输失败问题, 提高数据包传输率。实验结果表明,基于能量均衡的地理位置路由比传统单路径,不相交多路径路由具有更高的数据包传输成功率, 更低的标准化能量消耗。

[1] Al-Karaki J N,Kamal A E.Routing Techniques in Wireless Sensor Networks:A Survey[J].IEEEWirelessCommunications,2004,11(6):6-28. DOI:10.1109/MWC.2004.1368893.

[2] Zonouz A E,Xing L,Vokkarane V M,etal.Reliability-oriented Single-path Routing Protocols in Wireless Sensor Networks[J].IEEESensorsJournal,2014,14(11):4059-4068.DOI:10.1109/JSEN.2014.2332296.

[3] Wang L,Yang Y,Zhao W.Network Coding-based Multipath Routing for Energy Efficiency in Wireless Sensor Networks[J].EURASIPJournalonWirelessCommunicationsandNetworking,2012,2012(1):1-15.DOI:10.1186/1687-1499-2012-115.

[4] Ahlswede R,Cai N,Li S Y R,etal.Network Information Flow[J].IEEETransactionsonInformationTheory,2000,46(4):1204-1216.DOI:10.1109/18.850663.

[5] Guo Z,Wang B,Xie P,etal.Efficient Error Recovery with Network Coding in UnderWater Sensor Networks[J].AdHocNetworks,2009,7(4):791-802.DOI:10.1016/j.adhoc.2008.07.011.

[6] Liu X,Gong X,Zheng Y.Reliable Cooperative Communications Based on Random Network Coding in Multi-hop Relay WSNs[J].IEEESensorsJournal,2014,14(8):2514-2523.DOI:10.1109/JSEN.2014.2310899.

[7] Ding X,Sun X,Huang C,etal.Cluster-level Based Link Redundancy with Network Coding in Duty Cycled Relay Wireless Sensor Networks[J].ComputerNetworks,2016,99:15-36.DOI:10.1016/j.comnet.2016.02.003.

[8] Lee K H,Kim J H,Cho S.Power Saving Mechanism with Network Coding in the Bottleneck Zone of Multimedia Sensor Networks[J].ComputerNetworks,2016,96:58-68.DOI:10.1016/j.comnet.2015.07.005.

[9] Kumar V,Kumar S.Energy Balanced Position-based Routing for Lifetime Maximization of Wireless Sensor Networks[J].AdHocNetworks,2016.DOI:10.1016/j.adhoc.2016.08.006.

[10] Cadger F,Curran K,Santos J,etal.A Survey of Geographical Routing in Wireless Ad-Hoc Networks[J].IEEECommunicationsSurveys&Tutorials,2013,15(2):621-653.DOI:10.1109/SURV.2012.062612.00109.

[11] Khan A W,Abdullah A H,Razzaque M A,etal.VGDRA:A Virtual Grid-based Dynamic Routes Adjustment Scheme for Mobile Sink-based Wireless Sensor Networks[J].IEEESensorsJournal,2015,15(1):526-534.DOI:10.1109/JSEN.2014.2347137.

[12] 孙利民.无线传感器网络[M].北京：清华大学出版社,2005.

[13] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEETransactionsonWirelessCommunications,2002,1(4):660-670.DOI:10.1109/TWC.2002.804190.

[14] 王行甫,侯成龙,熊焰.一种基于虚拟网格位置的分簇算法① [J].计算机系统应用,2013(9):195-198.DOI:10.3969/j.issn.1003-3254.2013.09.038.

[15] Trullols-Cruces O,Barcelo-Ordinas J M,Fiore M.Exact Decoding Probability Under Random Linear Network Coding[J].IEEECommunicationsLetters,2011,15(1):67-69.DOI:10.1109/LCOMM.2010.110310.101480.

Design of A Geographic Routing Protocol based on Energy-balanced Strategy

JIA Xinchun,ZHANG Junli,CHI Xiaobo

(SchoolofMathematicalSciences,ShanxiUniversity,Taiyuan030006,China)

For the unreliability of wireless links and unbalanced energy consumption of sensor nodes in wireless sensor networks (WSNs), a geographic routing protocol based on energy-balanced strategy is proposed. In order to avoid the excessive reuse of some nodes caused by greedy forwarding in traditional geographic routing in the routing establishing stage, a cluster is regarded as a basic unit of data transmission, and an energy threshold is set for the sensors of the cluster. Meanwhile, both the number of nodes in each cluster and the distance from the cluster’s center to the sink are comprehensively considered as a routing metric, which can balance the energy consumption among the clusters. In the data transmission stage, the cooperative communication and network coding technologies are used to improve the reliability of data transmission. The theoretical analysis and numerical experimental results simultaneously show that the proposed protocol can significantly improve the successful delivery rate of data and reduce the number of packets retransmission.

wireless sensor networks; geographic routing protocol; network coding; reliability; energy balance

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.01.007

2016-07-24；

2016-10-20

国家自然科学基金(61374059;61403240)

贾新春(1964-),男,山西大同人,博士,教授,研究领域为网络化控制系统,E-mail:xchjia@sxu.edu.cn

TP13

A

0253-2395(2017)01-0044-07