基于融合判決的智能用電無線傳感器網(wǎng)絡(luò)擁塞避免路由算法

馮 森，唐良瑞，郝建紅

(1.華北電力大學新能源電力系統(tǒng)國家重點實驗室，北京 102206;2.華北電力大學電氣與電子工程學院，北京 102206)

0 引言

近年來，隨著智能電網(wǎng)技術(shù)的不斷發(fā)展，其在用電側(cè)的業(yè)務(wù)應(yīng)用系統(tǒng)也逐步完善，對智能用電通信網(wǎng)傳輸帶寬、時延和可靠性等方面提出了更高的要求［1，2］。因此，具有低成本、低功耗、自組織、靈活性、可靠性及可擴展性強等特點的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)便成為一種面向智能用電可以選擇的重要技術(shù)手段［3］。

在WSN 中，節(jié)點的能量、計算和通信能力極其有限，因此無線傳感器網(wǎng)絡(luò)面臨較大的能量和帶寬等資源壓力［4］，如何高效均衡地使用節(jié)點能量，延長網(wǎng)絡(luò)生命周期是路由算法設(shè)計的主要目標［5，6］。然而節(jié)點大規(guī)模密集部署的傳感器網(wǎng)絡(luò)具有多對一的流量模式，且其拓撲結(jié)構(gòu)和無線鏈路質(zhì)量動態(tài)變化，以及事件觸發(fā)導(dǎo)致流量突發(fā)性等，這些都容易引起網(wǎng)絡(luò)發(fā)生擁塞，從而導(dǎo)致丟包率和節(jié)點能耗增加，嚴重影響網(wǎng)絡(luò)的服務(wù)質(zhì)量和生命周期。因此，基于擁塞控制的路由算法成為WSN 的研究熱點［7］。在WSN 擁塞控制研究中速率控制被廣泛采用。CODA［8］研究了WSN中擁塞檢測及避免，同時采用了閉環(huán)源調(diào)節(jié)機制，但是這種基于緩存長度的擁塞檢測方法帶來了額外的開銷和網(wǎng)絡(luò)流量。此外還有ESRT［9］、UCC［10］等基于速率控制的擁塞路由算法?？傊?，速率限制機制需要節(jié)點不間斷地觀察它們父節(jié)點的發(fā)送行為以決定何時生成令牌，這一連續(xù)性監(jiān)控代價過高且耗能大。除了上述流量控制方法，還有一些研究探索了其他避免擁塞的機制，比如基于流量調(diào)度的路由算法。NCCAR［11］通過節(jié)點的區(qū)域擁塞度值選取路由，并結(jié)合網(wǎng)格編碼方法提高數(shù)據(jù)傳輸?shù)目煽啃?，合理地避免擁塞。TADR［12］通過由空閑或低負載的節(jié)點構(gòu)成的多路徑來分散過多的包，采用動態(tài)路由技術(shù)來減輕擁塞以便降低靜態(tài)多徑路由的額外開銷，然而其系數(shù)取值具有不確定性并且對路由的能效性考慮不周。同時TADR 在面臨擁塞時會有較大的端到端延時，并且每次當深度改變時計算深度開銷過大。

為了克服TADR 的上述缺陷，本文提出一種基于融合判決的擁塞避免路由算法。算法基于主動避免擁塞的設(shè)計思想，綜合考慮節(jié)點到Sink 距離，節(jié)點剩余能量和緩沖區(qū)隊列長度作為路由下一跳評價標準，建立隸屬度函數(shù)并進行融合判決，根據(jù)判決結(jié)果選取下一跳節(jié)點使數(shù)據(jù)包轉(zhuǎn)發(fā)避開擁塞節(jié)點最終到達Sink。實驗表明，算法有效地避免了節(jié)點擁塞，提升網(wǎng)絡(luò)的吞吐量同時均衡全網(wǎng)節(jié)點能耗，延長了網(wǎng)絡(luò)的生命周期。

本文后續(xù)部分安排如下:第一節(jié)詳細描述所提出的算法;第二節(jié)進行實驗仿真分析;第三節(jié)給出結(jié)論。

1 基于融合判決的擁塞避免路由算法

1.1 系統(tǒng)模型及問題描述

智能用電通信網(wǎng)承載了大量多元化業(yè)務(wù)，其中用電基本業(yè)務(wù)與用電擴展性業(yè)務(wù)這類業(yè)務(wù)數(shù)據(jù)對實時性要求雖然不高，但具有周期性質(zhì)，在整點上報時業(yè)務(wù)量突增。此外，在面向智能用電的WSN 拓撲結(jié)構(gòu)中，多個源節(jié)點采集業(yè)務(wù)數(shù)據(jù)并通過中繼節(jié)點中轉(zhuǎn)，以多跳的方式發(fā)送到集中器?？梢钥闯鲞@種基于事件驅(qū)動的WSN 中的數(shù)據(jù)傳輸存在“多對一”的特性。在流量突發(fā)的情況下，這種流量模式會引起網(wǎng)絡(luò)發(fā)生擁塞進而增加網(wǎng)絡(luò)延遲和丟包率，由此造成的數(shù)據(jù)包重傳還會極大地消耗節(jié)點的能量，縮短網(wǎng)絡(luò)生命周期。因此，節(jié)點的緩沖區(qū)占用情況作為一個可靠的擁塞檢測指標，在建立路由時考慮這一指標避開緩存隊列狀況不佳的節(jié)點將有效地轉(zhuǎn)移網(wǎng)絡(luò)流量至空閑或負載較輕的節(jié)點，從而減輕網(wǎng)絡(luò)擁塞。此外，由無線傳播能耗模型可知無線傳感器網(wǎng)絡(luò)節(jié)點在傳送數(shù)據(jù)時的能量消耗與傳播距離的平方或四次方呈正比，在源節(jié)點遠離Sink 的情況下，如何縮短數(shù)據(jù)傳輸路徑長度及均衡節(jié)點能量消耗成為延長無線傳感器網(wǎng)絡(luò)生命周期的關(guān)鍵，因此節(jié)點剩余能量及到基站距離仍是建立路由時需要考慮的關(guān)鍵因素。

為了解決以上問題，本文提出的算法采用主動的擁塞避免機制建立路由。首先依據(jù)前向傳播鄰居節(jié)點的緩存隊列長度、剩余能量和到基站距離3 個特征參量對路由下一跳節(jié)點選擇的不同影響，將其歸一化以建立合適的隸屬度函數(shù)，從而直觀地反映這些指標對選擇下一跳節(jié)點的決定作用。然后利用算子將隸屬度函數(shù)進行融合以得到最后的判決信度，根據(jù)最后的判決信度確定路由的下一跳節(jié)點。

1.2 算法描述

基于融合判決的擁塞避免路由算法共分為3個階段:(1)鄰居節(jié)點發(fā)現(xiàn)階段;(2)最優(yōu)路徑確定階段;(3)數(shù)據(jù)傳輸階段。

1.2.1 鄰居節(jié)點發(fā)現(xiàn)階段

無線傳感器網(wǎng)絡(luò)中任意節(jié)點i 都維護一個自身信息列表list(i)，其中包含節(jié)點i 在網(wǎng)絡(luò)中的標識id(i)，節(jié)點i 當前的剩余能量eres(i)，節(jié)點i 到基站的距離dbs(i)，節(jié)點當前的緩存隊列長度q(i)以及節(jié)點i 的下一跳鄰居節(jié)點列表nbr(i)。

由Sink 發(fā)起鄰居節(jié)點發(fā)現(xiàn)消息廣播，其中包含Sink 自身的id(s)和位置信息。任意節(jié)點a 收到Sink 的消息后，更新自身消息列表，并將Sink的id 加入到自己的下一跳鄰居節(jié)點列表中，繼續(xù)廣播包含自身id 的消息。任意節(jié)點j 收到來自非Sink 節(jié)點k 的消息后，若dbs(j)＞dbs(k)則更新自身消息列表，添加k 的消息到nbr(j)，即節(jié)點k 為j的前向傳播鄰居節(jié)點，繼續(xù)廣播直到所有節(jié)點接收到消息并更新，則鄰居發(fā)現(xiàn)階段結(jié)束。

1.2.2 最優(yōu)路徑確定階段

此階段根據(jù)融合判決結(jié)果由源節(jié)點起逐跳選取下一跳節(jié)點從而確定出最優(yōu)路徑。

算法在選取下一跳節(jié)點時綜合考慮節(jié)點的剩余能量，節(jié)點到基站距離和節(jié)點緩存隊列長度這3點因素作為評價指標。在節(jié)點剩余能量相同的情況下，節(jié)點到基站的距離越小節(jié)點傳輸數(shù)據(jù)消耗的能量越小，所以在節(jié)點剩余能量相同的情況下，優(yōu)先選擇距離基站近的節(jié)點擔任轉(zhuǎn)發(fā)節(jié)點;在節(jié)點到基站距離相同的情況下，為了避免剩余能量小的節(jié)點率先失效，優(yōu)先選擇剩余能量多的節(jié)點作為下一跳;而在節(jié)點剩余能量、節(jié)點到基站距離均相同的情況下，緩存隊列長度小的節(jié)點負載輕，優(yōu)先選作下一跳節(jié)點可以有效避免發(fā)生擁塞。而現(xiàn)實情況下，同時考慮節(jié)點的3 個評價指標的情況較為復(fù)雜，為了消除3 種評價指標下判決結(jié)果的不一致性，CARF 算法為單個指標建立隸屬度函數(shù)，反映其對選擇下一跳的判決影響，然后將各個評價指標隸屬度函數(shù)進行融合判決，得到最終的判決信度，由此選出最合適的下一跳節(jié)點。

在下一跳節(jié)點選取中，節(jié)點緩存隊列長度越小對成為下一跳節(jié)點的貢獻就越大。qmax作為節(jié)點i 的最大緩存，q(i)為節(jié)點i 的當前緩存隊列長度，則歸一化后的節(jié)點i 的緩存占用率Fq(i)為

可見節(jié)點當前緩存隊列長度越小則緩存占用率越小，說明該節(jié)點流量負載較輕，不易發(fā)生擁塞，適合作為路由下一跳節(jié)點進行數(shù)據(jù)包轉(zhuǎn)發(fā)，因此本文采用高斯函數(shù)為其建立隸屬度函數(shù)，如式(2)所示

式中:σ，c 為調(diào)節(jié)隸屬度函數(shù)的常數(shù)參量，修改此常數(shù)可控制隸屬度函數(shù)曲線。本文中取σ = 0.5，c =－0.1 。μq(i)越大，說明該節(jié)點隸屬于下一跳節(jié)點的概率越大，否則隸屬于下一跳節(jié)點的概率越小。其曲線如圖1所示。

圖1 節(jié)點緩存占用率指標隸屬度函數(shù)曲線Fig.1 The membership function curve of node cache usage

由能量模型計算公式可知，為使全網(wǎng)節(jié)點減少消耗的能量，則在下一跳節(jié)點選取時距離基站越近的節(jié)點越優(yōu)。因此，節(jié)點距離基站越近則其成為下一跳節(jié)點的概率越大，將節(jié)點到基站的距離值歸一化后作為該節(jié)點成為下一跳可能性的判決信度，同樣可采用高斯函數(shù)為其建立隸屬度函數(shù):

式中:dbs(i)為節(jié)點i 到Sink 的距離;dmax為離Sink最遠節(jié)點的距離。

為了均衡全網(wǎng)節(jié)點的能耗，優(yōu)先選取剩余能量高的節(jié)點作為下一跳。將節(jié)點的剩余能量值歸一化后作為該節(jié)點成為下一跳可能性的判決信度，為了使其符合上述兩個評價指標對節(jié)點隸屬度的影響，令

式中:eres(i)為節(jié)點i 當前剩余能量;e0為節(jié)點初始能量。

由上述分析可知，三個評價指標進行歸一化后都變?yōu)槌杀拘蛯傩裕鶕?jù)其對路由下一跳選擇的判決影響，均采用高斯函數(shù)建立隸屬度函數(shù)。

為了較好地融合節(jié)點緩存隊列長度、節(jié)點到基站距離和節(jié)點剩余能量對該節(jié)點成為下一跳節(jié)點隸屬度的影響，本文采用下式對其進行融合:

不難發(fā)現(xiàn)，該式可實現(xiàn)3 個評價指標的加強性和調(diào)和性并滿足以下特性:

(1)是一個縮維映射F:[0，1]2→ [0，1]

(2)F(0，0，0)= 0，F(xiàn)(1，1，1)= 1

(3)F(a，b，c)≤F(d，e，f)，a ≤d，b ≤e，c ≤f

(4)F(a，b，c)= F(b，a，c)= F(a，c，b)=F(c，b，a)

(5)F(a，b，c)≥max(a，b，c)，a ≥0.5，b ≥0.5，c≥0.5 或F(a，b，c)≤min(a，b，c)，a ≤0.5，b ≤0.5，c ≤0.5

(6)min(a，b，c)＜ F(a，b，c) ＜ max(a，b，c)，a ＞0.5 ＞b ＞c 或a ＞b ＞0.5 ＞c

其中a，b，c，d，e，f∈(0，1)。

因此將式(7)的融合結(jié)果作為最后的判決信度，確定隸屬度函數(shù)值μ(i)最大的節(jié)點為路由下一跳節(jié)點。

1.2.3 路由維護階段

最優(yōu)路徑確定以后，隨著數(shù)據(jù)傳輸輪數(shù)的增加，網(wǎng)絡(luò)中節(jié)點的擁塞情況和剩余能量發(fā)生變化，但頻繁執(zhí)行算法選取最優(yōu)路徑會產(chǎn)生過大的控制開銷，造成能量浪費。因此，本文為傳輸路徑上的節(jié)點設(shè)定擁塞閾值，若路徑上任意節(jié)點i 的緩存占用率超過這一閾值或者由于能量耗盡失效，則節(jié)點發(fā)送路由維護請求，算法立即重啟最優(yōu)路徑的選取過程。

2 仿真結(jié)果及分析

本文采用MATLAB 進行實驗仿真，選取經(jīng)典的路由算法DD［13］和TADR 作為基本對比算法。仿真中固定個數(shù)節(jié)點隨機均勻分布在邊長為100 m 的正方形區(qū)域中，匯聚節(jié)點位于(0，0)處，所有節(jié)點一旦放置就不再移動，每個節(jié)點的初始能量為0.5 J，具體仿真參數(shù)設(shè)置如表1所示。

本文使用的仿真場景中配置有1 個Sink 和4 個源節(jié)點，其中Sink 位于坐標軸原點，而源節(jié)點處于區(qū)域邊緣，遠離匯聚節(jié)點。這樣的設(shè)置使得路由算法選取的路徑需經(jīng)過WSN 中大面積區(qū)域。

表1 仿真環(huán)境參數(shù)Tab.1 Simulation environment parameters

在無線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)傳輸?shù)目煽啃允荳SN 的重要性能評價指標，吞吐率在一定程度上反應(yīng)了網(wǎng)絡(luò)可靠程度。傳感器節(jié)點因擁塞將會導(dǎo)致數(shù)據(jù)重傳，而多次重傳不成功時，數(shù)據(jù)包就有可能被丟棄。分別執(zhí)行DD、TADR 和CARF 協(xié)議，統(tǒng)計得到網(wǎng)絡(luò)吞吐率隨節(jié)點總數(shù)的變化關(guān)系，如圖2所示。由圖2 可知，當節(jié)點數(shù)量從100 到300 變化時，執(zhí)行CARF 算法的網(wǎng)絡(luò)吞吐率最高，而DD 算法由于沒有擁塞控制機制表現(xiàn)最差。CARF 算法建立了基于節(jié)點緩沖區(qū)包隊列長度的隸屬度函數(shù)，這一主動轉(zhuǎn)移流量的路由策略很大程度上避免了擁塞的發(fā)生，降低了網(wǎng)絡(luò)丟包率。雖然TADR算法考慮下一跳節(jié)點的擁塞狀態(tài)，即通過節(jié)點緩沖區(qū)隊列長度來檢測擁塞，然而由于采用線性加權(quán)的局限性及權(quán)重系數(shù)選擇的不確定性，其對網(wǎng)絡(luò)性能改有限。本文提出的CARF 算法采用融合判決方法獲得最終判決信度，實現(xiàn)擁塞避免路由機制，進一步提高了網(wǎng)絡(luò)吞吐率等性能。

圖2 網(wǎng)絡(luò)吞吐率與節(jié)點數(shù)量的關(guān)系Fig.2 The relationship between the network throughput and the number of nodes

此外，網(wǎng)絡(luò)生命周期和節(jié)點平均能耗也是衡量擁塞控制路由算法性能的重要指標。其中，WSN 網(wǎng)絡(luò)生命周期的精確定義是由具體應(yīng)用環(huán)境來決定的，有些應(yīng)用場景可以容許相當一部分的節(jié)點失效，而有的應(yīng)用中任一節(jié)點死亡都會對網(wǎng)絡(luò)產(chǎn)生至關(guān)重要的影響。本文選擇首個節(jié)點死亡時數(shù)據(jù)發(fā)送輪數(shù)定義為WSN 網(wǎng)絡(luò)生命周期。由圖3 可以看出，CARF 算法與DD、TADR 算法相比有效提高了網(wǎng)絡(luò)生命周期。CARF 算法在路由下一跳節(jié)點選擇時結(jié)合節(jié)點緩沖區(qū)隊列長度、節(jié)點到匯聚節(jié)點距離和剩余能量水平3 個評價指標，得到了避免擁塞及優(yōu)化網(wǎng)絡(luò)能耗和生命周期的實驗結(jié)果。并且不難看出隨著網(wǎng)絡(luò)規(guī)模的增大，CARF 算法的優(yōu)勢愈發(fā)明顯。這說明了CARF 算法在不同的網(wǎng)絡(luò)規(guī)模中性能表現(xiàn)都更為優(yōu)異。

圖3 網(wǎng)絡(luò)生命周期與節(jié)點數(shù)量的關(guān)系Fig.3 The relationship between the network lifetime and the number of nodes

實驗仿真結(jié)果與本文算法設(shè)計初衷相吻合，即全面考慮影響WSN 網(wǎng)絡(luò)擁塞及能耗的因素，將其通過隸屬度函數(shù)建立起與下一跳節(jié)點選擇的關(guān)系，并利用融合判決方法確定最優(yōu)路徑，優(yōu)化全網(wǎng)能量消耗，有效延長WSN 網(wǎng)絡(luò)的生命周期。

另一路由算法仿真評價參數(shù)為節(jié)點能量消耗，它衡量將一個數(shù)據(jù)包由源節(jié)點轉(zhuǎn)發(fā)至Sink 時節(jié)點的平均消耗能量，其反映了WSN 網(wǎng)絡(luò)的能量有效性水平。本文取各路由算法運行至最大生命周期輪數(shù)時每個節(jié)點每輪的平均能耗做出分析與比較。圖4 展示了不同拓撲設(shè)置場景下的節(jié)點能耗仿真結(jié)果?？梢钥闯霰疚牡腃ARF 算法相較DD、TADR 算法擁有最低的節(jié)點能耗水平。DD 算法下數(shù)據(jù)包的發(fā)送建立在Sink 發(fā)布查詢的基礎(chǔ)上，而Sink 還要在發(fā)布查詢的過程中建立梯度場，由于網(wǎng)絡(luò)通信狀態(tài)的動態(tài)性，無法保證按已建立的路徑在能耗方面最優(yōu)，此外隨著網(wǎng)絡(luò)負載提高丟包率大幅上升，重傳造成大量的能量消耗。TADR 算法能耗代價明顯優(yōu)于DD，其在WSN 區(qū)域根據(jù)普通節(jié)點到匯聚節(jié)點的通信距離將其分成逐跳增加的固定區(qū)域，并建立基于節(jié)點跳數(shù)的深度虛擬勢能場，但這種方法使得所建路由的勢能場值是離散的，并且每次當深度改變時計算深度開銷過大，而本文算法中根據(jù)節(jié)點到Sink 的距離建立隸屬度函數(shù)，更為精確直接地反映距離因素與能量消耗的關(guān)系，并且許多情況下跳數(shù)靈活變化的路由要優(yōu)于固定跳數(shù)路由。此外，TADR 算法只建立了基于跳數(shù)的深度勢能場和基于節(jié)點隊列長度的勢能場，造成算法只是單一的保證了最小跳數(shù)路由的建立并且可能產(chǎn)生節(jié)點回傳情況，從而忽略了網(wǎng)絡(luò)整體能耗的均衡性。CARF 算法中路由的建立使得數(shù)據(jù)包的發(fā)送為正向距離傳播，有效地避免了節(jié)點回傳和局部環(huán)傳遞等問題，從而降低了網(wǎng)絡(luò)節(jié)點整體能耗，使得網(wǎng)絡(luò)平均節(jié)點能耗穩(wěn)定地維持在一個較低的水平。同時，與其他路由算法相比其性能受到網(wǎng)絡(luò)規(guī)模變化的影響也最小。

圖4 網(wǎng)絡(luò)平均節(jié)點能耗與節(jié)點數(shù)量的關(guān)系Fig.4 The relationship between the average energy consumption and the number of nodes

3 結(jié)論

結(jié)合智能用電通信業(yè)務(wù)的流量特點，針對已有擁塞控制路由算法的不足，本文提出一種無線傳感器網(wǎng)絡(luò)中的基于融合判決的擁塞避免路由算法。該算法考慮節(jié)點緩存隊列長度、節(jié)點到基站距離和節(jié)點剩余能量三個影響WSN 網(wǎng)絡(luò)性能的重要因素，建立隸屬度函數(shù)并通過融合算子得到最終判決信度來確定路由下一跳節(jié)點選擇。實驗仿真結(jié)果表明，CARF 算法相比DD、TADR 算法更有效地提升了網(wǎng)絡(luò)吞吐率，并且具有更高的節(jié)點能效性和均衡性，使無線傳感器網(wǎng)絡(luò)獲得了更長的生命周期。

［1］Aggarwal A，Kunta S，Verma P K.A proposed communications infrastructure for the Smart Grid［C］.Innovative Smart Grid Technologies (ISGT)，Gaithersburg，MD，USA，19－21 Jan.，2010:1－5.

［2］郭云鵬，劉偉佳，文福拴.智能配電系統(tǒng)的發(fā)展現(xiàn)狀與展望［J］.華北電力大學學報，2014，41(5):74－81.

［3］Gungor V C，Lu B，Hancke G P.Opportunities and challenges of wireless sensor networks in smart grid［J］.IEEE Transactions on Industrial Electronics，2010，57 (10):3557－3564.

［4］Sergiou C，Vassiliou V.Estimating maximum traffic volume in wireless sensor networks using fluid dynamics principles［J］.IEEE Communications Letters，2013，17 (2):257－260.

［5］Uster H，Lin H.Integrated topology control and routing in wireless sensor networks for prolonged network lifetime［J］.Ad Hoc Networks，2011，9 (5):835－851.

［6］Padilla P，Camacho J，MaciáFernández G，et al.On the influence of the propagation channel in the performance of energy-efficient geographic routing algorithms for wireless sensor networks［J］.Wireless Personal Communications，2013，70 (1):15－38.

［7］孫利民，李波，周新運.無線傳感器網(wǎng)絡(luò)的擁塞控制技術(shù)［J］.計算機研究與發(fā)展，2008，45 (1):63－72.

［8］Wan C Y，Eisenman S B，Campbell A T.CODA:Congestion Detection and Avoidance in Sensor Networks［C］.Proceedings of the First International Conference on Embedded Networked Sensor Systems (SenSys ’03)，Los Angeles，CA，US，5－7 November，2003:266－279.

［9］Hull B，Jamieson K，Balakrishnan H.Mitigating Congestion in Wireless Sensor Networks［C］.Proc.Int’l Conf.Embedded Networked Sensor Systems (SenSys ’04)，Baltimore，MA，US，3－ 5 November，2004:134－147.

［10］張玉鵬，劉凱，王廣學.基于無線傳感器網(wǎng)絡(luò)的跨層擁塞控制協(xié)議［J］.電子學報，2011，39 (10):2258－2262.

［11］付彬，李仁發(fā)，劉彩蘋，等.無線傳感器網(wǎng)絡(luò)中一種基于網(wǎng)絡(luò)編碼的擁塞感知路由協(xié)議［J］.計算機研究與發(fā)展，2011，48 (6):991－999.

［12］Ren F Y，He T，Das S K，et al.Traffic-Aware Dynamic Routing to Alleviate Congestion in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22 (9):1585－1599.

［13］Intanagonwiwat C，Govindan R，Estrin D，et al.Directed diffusion for wireless sensor networking［J］.IEEE/ACM Transactions on Networking，2003，11(1):2－16.