何杏宇，周亦敏，楊桂松

(1.上海理工大學(xué) 實(shí)驗(yàn)室管理與服務(wù)中心，上海200093;2.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法復(fù)雜度分析

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

5 仿真與實(shí)驗(yàn)

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

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

5.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

［2］ 程 磊，張 東，劉 波，等.基于無(wú)線傳感器網(wǎng)絡(luò)的氣體泄漏源定位機(jī)器人設(shè)計(jì)［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.