基于多根多樹結(jié)構(gòu)的多播傳感器網(wǎng)絡(luò)編碼方法*

何杏宇，周亦敏，楊桂松

(1.上海理工大學 實驗室管理與服務(wù)中心，上海200093;2.上海理工大學 光電信息與計算機工程學院，上海200093)

0 引 言

隨著物聯(lián)網(wǎng)(IoT)的發(fā)展，無線傳感器網(wǎng)絡(luò)(WSNs)的應用得到進一步的推廣［1，2］。樹型路由由于它的簡單性成為無線傳感器網(wǎng)絡(luò)中一種較為基礎(chǔ)的路由策略，但是，其根節(jié)點附近能耗開銷較大，需要對此進行改進［3，4］。為了進一步實現(xiàn)能耗均衡，層次型簇樹協(xié)議相繼提出，LEACH［5］算法是較早提出的一種層次型簇樹算法。隨后，出現(xiàn)了各種LEACH 的改進算法，文獻［6，7］對一些LEACH 改進算法進行了比較分析，雖然它們對能耗均衡作出了不同程度的貢獻，但都是基于單一Sink 節(jié)點構(gòu)成網(wǎng)絡(luò)，數(shù)據(jù)流向單一。

除了上述改變組網(wǎng)方式外，Ahlswede A 等人提出的網(wǎng)絡(luò)編碼技術(shù)［8］也已經(jīng)被證明在提高網(wǎng)絡(luò)帶寬利用率和降低節(jié)點能耗等方面有顯著的優(yōu)勢。文獻［9］將帶有解碼反饋的Xor 編碼用于簇樹型網(wǎng)絡(luò)以提高帶寬，文獻［10］則通過編碼節(jié)點來緩解能耗瓶頸區(qū)的網(wǎng)絡(luò)擁塞和能耗緊張。上述算法都屬于單播網(wǎng)絡(luò)編碼，而傳統(tǒng)的多播網(wǎng)絡(luò)編碼傳輸路徑獲取過程較為復雜，不適合在能量有限的傳感器網(wǎng)絡(luò)中應用［11］。

為此，本文提出了一種低復雜度的基于多根多樹(multi－roots multi－trees，MRMT)結(jié)構(gòu)的多播網(wǎng)絡(luò)編碼方法。該方法根據(jù)MRMT 結(jié)構(gòu)中節(jié)點的多個樹地址計算源節(jié)點到目的節(jié)點之間的子圖，然后利用能量相關(guān)的MRMT 鏈接矩陣獲取源節(jié)點到目的節(jié)點的多條能量相關(guān)的分離路徑，以最終實現(xiàn)基于MRMT 結(jié)構(gòu)的K 冗余多播網(wǎng)絡(luò)編碼。

1 網(wǎng)絡(luò)模型

本文的網(wǎng)絡(luò)模型定義如下:1)傳感器節(jié)點在部署后位置固定，且具有獲知其位置信息的能力;2)網(wǎng)絡(luò)中的所有傳感器節(jié)點結(jié)構(gòu)相同，且能量不可補給;3)每個傳感器節(jié)點具有一個全網(wǎng)唯一的ID 號和多個Zig Bee 樹地址;4)本文采用文獻［12］中的無線通信能量模型。

2 MRMT 結(jié)構(gòu)的組網(wǎng)過程

2.1 基于位置和鏈接關(guān)系的父節(jié)點選擇算法

MRMT 結(jié)構(gòu)中的多個樹是依次形成的，每形成一個樹，節(jié)點就獲得一個對應的樹地址(按照Zig Bee 協(xié)議進行樹地址分配)。第一個樹是按照傳統(tǒng)的樹型組網(wǎng)方式形成，但為了給節(jié)點開辟更多不同的數(shù)據(jù)傳輸路徑，后續(xù)樹結(jié)構(gòu)將按照圖1 所示的父節(jié)點選擇算法形成:在第n 個樹結(jié)構(gòu)的形成過程中，當前節(jié)點優(yōu)先選擇那些在之前的n－1 個樹結(jié)構(gòu)都與本節(jié)點沒有鏈接關(guān)系的節(jié)點作為父節(jié)點，如果本節(jié)點具有多個鄰居節(jié)點在之前的n－1 個樹結(jié)構(gòu)都與本節(jié)點不存在鏈接關(guān)系，那么選這多個鄰居節(jié)點中與第n 個根節(jié)點距離最近的節(jié)點作為父節(jié)點;如果本節(jié)點的所有鄰居節(jié)點在之前的n－1 個樹結(jié)構(gòu)都與本節(jié)點具有鏈接關(guān)系，那么選這多個鄰居節(jié)點中與第n 根節(jié)點距離最近的節(jié)點作為父節(jié)點。

圖1 父節(jié)點選擇算法流程圖Fig 1 Flow chart of farther node selection algorithm

2.2 能量相關(guān)的MRMT 鏈接矩陣

為了方便后續(xù)計算多播網(wǎng)路編碼的分離路徑，在MRMT 結(jié)構(gòu)的形成后，每個節(jié)點將廣播自己的ID 號、位置信息和多個樹地址。然后，每個根節(jié)點將存儲網(wǎng)絡(luò)中所有節(jié)點的ID 和多個樹地址的對應關(guān)系，以及計算一個MRMT鏈接矩陣結(jié)構(gòu)A［i，j］，i 和j 表示節(jié)點的ID 號。另外，在MRMT 結(jié)構(gòu)形成之后，第一個樹節(jié)點將周期性地收集所有節(jié)點的剩余能量信息，并對其進行排序，選出剩余能量等級低于預設(shè)能量等級的節(jié)點，并將該節(jié)點ID 信息廣播出去。A［i，j］鏈接矩陣的計算公式為

其中，D［i，j］為節(jié)點i 和j 之間的距離，Ri和Rj為節(jié)點i 和j 在網(wǎng)絡(luò)中的剩余能量等級，Rthreshold為預設(shè)能量等級。當節(jié)點i 和j 之間有鏈接關(guān)系且節(jié)點i 和j 的剩余能量等級Ri和Rj均大于等于預設(shè)能量等級Rthreshold，則A［i，j］=D［i，j］;否則，A［i，j］=∞，從而使得剩余能量低的節(jié)點將暫時性不參與后續(xù)的分離路徑計算，以保持整個網(wǎng)絡(luò)的能耗均衡。

3 多播網(wǎng)絡(luò)編碼協(xié)議

3.1 K 冗余多播網(wǎng)絡(luò)

K 冗余多播網(wǎng)絡(luò)的兩個定義如下:

定義1 網(wǎng)絡(luò)中的所有節(jié)點的集合由三個不相交的子集{s}∪{r}∪g0gggggg組成，{s}為源節(jié)點集，滿足入度indgree(s)=0 和出度outdgree(s)＞0，{r}為中間節(jié)點集，滿足入度0≤indgree(s)≤k 和出度outdgree(s)＞0，g0gggggg為目的節(jié)點集，滿足入度indgree(s)=K 和出度outdgree(s)=0。

定義2 如果從源節(jié)點s 到目的節(jié)點d 的任意兩條路徑之間沒有任何共享鏈路，則稱兩條路徑為分離路徑。

根據(jù)文獻［13］可知K 冗余多播網(wǎng)絡(luò)可獲得的最大流為K，又由文獻［14］可知，對于單個信源和多個信宿的網(wǎng)絡(luò)，采用網(wǎng)絡(luò)編碼可以使其達到最大流，那么給定一個每一條鏈路的初帶寬為單位帶寬的K 冗余多播網(wǎng)絡(luò)，從源節(jié)點s 到目的節(jié)點d 有K 條分離路徑，就可以通過網(wǎng)絡(luò)編碼使其達到最大流K。

3.2 分離路徑構(gòu)建

本文提出的分離路徑構(gòu)建方法將從多根多樹結(jié)構(gòu)為源節(jié)點和目的節(jié)點之間提供的多條路徑中選出前K 條最短路徑(可能同時包含樹路徑和組合路徑)，具體算法流程圖如圖2 所示。

圖2 分離路徑構(gòu)建流程圖Fig 2 Flow chart of disjoint paths construction

2)根據(jù)多條樹路徑快速地產(chǎn)生源節(jié)點和目的節(jié)點之間的子圖G=(V，E)，V 為多條樹路徑的所有節(jié)點的集合，E 為V 中所有節(jié)點之間的鏈接集合，G 中i 節(jié)點和j 節(jié)點之間的邊的權(quán)重等于對應MRMT 鏈接矩陣值A(chǔ)［i，j］。

3)利用Dijkstra 算法計算出源節(jié)點到目的節(jié)點的最短路徑，由于已經(jīng)將能量級別較低的節(jié)點MRMT 鏈接矩陣值A(chǔ)［i，j］設(shè)為∞，計算出的最短路徑將能量較優(yōu)。

4)求出一條最短路徑后，將圖G 中當前最短路徑所有鏈接對應的A［i，j］值設(shè)為∞，使其與后續(xù)計算出來的最短路徑之間不存在共享鏈路，然后利用Dijkstra 算法和修改后的圖G 計算下一條最短路徑，直至求出K 條最短路徑。因此，上述方法計算出的K 條最短路徑為K 條分離路徑。

4 算法復雜度分析

傳統(tǒng)多播網(wǎng)絡(luò)編碼方法的復雜度依賴于多播路由算法的復雜度。這里以較為簡單的單純形法的最小費用多播路由算法為例，它的復雜度為O(|E|3|S|3)，E 為鏈路集，S為多播節(jié)點集。而在基于MRMT 結(jié)構(gòu)的多播網(wǎng)絡(luò)編碼方法中，利用Dijkstra 算法計算K 分離路徑的復雜度為O(m|D||N|)，D 為目的節(jié)點數(shù)，N 為總節(jié)點數(shù)。顯然，本文提出的方法復雜度較低。

5 仿真與實驗

本文使用NS2 平臺對LEACH 協(xié)議，文獻［9］所提出的CoZi 協(xié)議以及本文提出的方法分別進行了仿真，并對三種方法的仿真結(jié)果進行了對比分析。

5.1 實驗參數(shù)設(shè)置

本文的仿真場景為200 個傳感器節(jié)點和10 個根節(jié)點隨機部署在一個200 m×200 m 的正方形區(qū)域內(nèi)。參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)Tab 1 Simulation parameters

5.2 實驗結(jié)果分析

由圖3 可知，CoZi 協(xié)議和LEACH 協(xié)議因數(shù)據(jù)傳流向單一，均呈現(xiàn)較高的能耗方差且波動較大，反映出較大的網(wǎng)絡(luò)能耗不均衡性。相較之下，本文提出的方法有效地降低了方差，呈現(xiàn)出較好的能耗均衡狀況。

圖3 節(jié)點能量消耗方差Fig 3 Energy consumption variance of nodes

由圖4 可知，雖然CoZi 協(xié)議利用網(wǎng)絡(luò)編碼減少能量消耗，在一開始時呈現(xiàn)的節(jié)點死亡數(shù)量低，但LEACH 協(xié)議具有簇頭輪換機制，后期節(jié)點死亡數(shù)量反而較低。而本文提出的方法中MRMT 結(jié)構(gòu)均衡了網(wǎng)絡(luò)能耗，多播網(wǎng)絡(luò)編碼減少了網(wǎng)絡(luò)的整體能耗開支，節(jié)點開始死亡的時間點最遲，且網(wǎng)絡(luò)運行持續(xù)時間最長。

圖4 節(jié)點存活的個數(shù)Fig 4 Number of alive nodes

由圖5 可知，CoZi 協(xié)議因利用了網(wǎng)絡(luò)編碼，其平均吞吐量優(yōu)于LEACH 協(xié)議，而本文提出的方法采用基于MRMT結(jié)構(gòu)的多播編碼方法，在平均吞吐量上明顯優(yōu)于前兩者。

圖5 網(wǎng)絡(luò)平均吞吐量Fig 5 Average throughput of networks

6 結(jié)束語

本文提出的多播網(wǎng)絡(luò)編碼方法基于MRMT 結(jié)構(gòu)，為每個節(jié)點提供了多個數(shù)據(jù)流向，促進了能耗均衡，利用了Zig Bee 樹地址的規(guī)律快速地獲取分離路徑，極大降低了算法復雜度，簡便地實現(xiàn)了K 冗余多播網(wǎng)絡(luò)編碼。實驗結(jié)果證明:該方法不僅降低了能耗且提高了網(wǎng)絡(luò)帶寬。

［1］ 萬喬喬，張俊然，趙 斌.無線傳感器網(wǎng)絡(luò)通信協(xié)議及其在醫(yī)學領(lǐng)域的研究進展［J］.傳感器與微系統(tǒng)，2015，34(7):11－13.

［2］ 程 磊，張 東，劉 波，等.基于無線傳感器網(wǎng)絡(luò)的氣體泄漏源定位機器人設(shè)計［J］.傳感器與微系統(tǒng)，2015，34(2):85－87.

［3］ Qiu W，Skafidas E，Hao P.Enhanced tree routing for wireless sensor networks［J］.Ad Hoc Networks，2009，7(3):638－650.

［4］ Han Z，Wu J.A general self－organized tree－based energy－balance routing protocol for wireless sensor networks［J］.IEEE Transactions on Nuclear Science，2014，61(2):732－740.

［5］ Heinzelman W R，Chandrakasan A.An application－specific protocol architecture for wireless micro sensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［6］ Li Y，Zhang A，Liang Y.Improvement of leach protocol for wireless sensor networks［C］∥The Third International Conference on Instrumentation，Measurement，Computer，Communication and Control，Shenyang:IEEE，2013:322 －326.

［7］ Keert N，Anand G.Improved cluster routing protocol for wireless sensor networks through simplification［C］∥The 18th Annual International Conference on Advanced Computing and Communications，Bangalore:IEEE，2012:1－3.

［8］ A1hlwede R，Cai N，Li S，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204－1216.

［9］ Salhi I，Ghamri－Doudane Y，Lohier S，et al.Reliable network coding for Zig Bee wireless sensor networks［C］∥The 8th International Conference on Mobile Ad Hoc and Sensor Systems(MASS)，Valencia:IEEE，2011:136 －137.

［10］Rout R.Enhancement of lifetime using duty cycle and network coding in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2013，12(2):656－666.

［11］Lun D S，Ratnakar N，Medard M，et al.Minimum－cost multicast over coded packet networks［J］.IEEE Transactions on Information Theory，2006，52(6):2608－2623.

［12］Su I，Tsai C，Sung W.Area temperature system monitoring and computing based on adaptive fuzzy logic in wireless sensor networks［J］.Applied Soft Computing，2012，12:1532－1541.

［13］Zhu Y，Li B，Guo J.Multicast with network coding in applicationlayer overlay networks［J］.IEEE Journal on Selected Areas in Communications，2004，22(1):107－120.

［14］Koetter R，Medard R.An algebraic approach to network coding［J］.IEEE/ACM Transactions on Networking，2003，11(5):782－795.