李金寶，倪林雨,郭亞紅,任倩倩

(1.黑龍江大學(xué) a.計算機(jī)科學(xué)技術(shù)學(xué)院;b.信息科學(xué)技術(shù)學(xué)院，哈爾濱 150080；2．黑龍江省數(shù)據(jù)庫與并行計算重點(diǎn)實(shí)驗(yàn)室，哈爾濱 150080)

基于k元n立方體拓?fù)涞臒o線傳感器網(wǎng)絡(luò)廣播策略

李金寶1a,2，倪林雨1a,2,郭亞紅1b,任倩倩1a,2

(1.黑龍江大學(xué) a.計算機(jī)科學(xué)技術(shù)學(xué)院;b.信息科學(xué)技術(shù)學(xué)院，哈爾濱 150080；2．黑龍江省數(shù)據(jù)庫與并行計算重點(diǎn)實(shí)驗(yàn)室，哈爾濱 150080)

研究了無線傳感器網(wǎng)絡(luò)的廣播策略，提出一個沖突避免立方體廣播算法CACB(Collision Avoidance Cube Broadcast)。CACB基于對k元n立方體結(jié)構(gòu)的網(wǎng)絡(luò)研究廣播策略。CACB算法采用時鐘準(zhǔn)同步的方法，按照為序?qū)降姆绞?，確定每一個時間步應(yīng)該如何去路由信息。實(shí)驗(yàn)使用OPNET軟件進(jìn)行仿真，仿真結(jié)果表明基于k元n立方體的無線傳感器網(wǎng)絡(luò)的廣播算法CACB和傳統(tǒng)的廣播策略相比，能夠減少最大端到端的時延，降低網(wǎng)絡(luò)沖突，減少節(jié)點(diǎn)能量消耗，延長整個網(wǎng)絡(luò)壽命,提高了網(wǎng)絡(luò)的吞吐量。

無線傳感器網(wǎng)絡(luò)；廣播；k元n立方體；吞吐量；端到端時延

0 引 言

無線傳感器網(wǎng)絡(luò)目前已經(jīng)在國防軍事、智能家居、城市小區(qū)安全監(jiān)控、環(huán)境監(jiān)測和預(yù)報、醫(yī)療狀況監(jiān)控、深海監(jiān)控、目標(biāo)跟蹤和檢測、森林火災(zāi)監(jiān)控等眾多領(lǐng)域得到了廣泛應(yīng)用[1]。

廣播在無線傳感器網(wǎng)絡(luò)中是一種最基本的服務(wù)。泛洪法(FLOOD)是所有廣播中最簡單的方法[2]。這種方法實(shí)現(xiàn)簡單，當(dāng)節(jié)點(diǎn)收到數(shù)據(jù)信息就轉(zhuǎn)發(fā)給它的鄰居節(jié)點(diǎn)，并且可傳輸?shù)骄W(wǎng)絡(luò)中的全部節(jié)點(diǎn)，但是泛洪法會導(dǎo)致廣播風(fēng)暴[3]。當(dāng)節(jié)點(diǎn)電量用盡時，導(dǎo)致網(wǎng)絡(luò)不連通，影響了正常通信，因此節(jié)點(diǎn)能量的消耗情況決定整個網(wǎng)絡(luò)的壽命?，F(xiàn)有的廣播算法已經(jīng)有了一定的成果，研究出一種更加高效的廣播算法仍然具有研究的意義[4]。

泛洪法是所有節(jié)點(diǎn)在收到某一廣播時間信息后，都將再次轉(zhuǎn)發(fā)該數(shù)據(jù)信息，這種算法的缺點(diǎn)明顯，數(shù)據(jù)將冗余轉(zhuǎn)發(fā)，增加了節(jié)點(diǎn)的能量消耗和沖突碰撞的可能性。PB算法和泛洪廣播算法十分相似，它是基于概率的廣播算法，與泛洪法唯一不同的是節(jié)點(diǎn)在收到數(shù)據(jù)消息后以概率進(jìn)行轉(zhuǎn)發(fā)的數(shù)據(jù)信息。這種算法同樣較簡單，可以在一定程度上減少冗余轉(zhuǎn)發(fā)數(shù)據(jù)。

1 相關(guān)知識與網(wǎng)絡(luò)模型

1.1 相關(guān)知識

無線傳感器網(wǎng)絡(luò)的特點(diǎn)是無線傳感器節(jié)點(diǎn)能量有限，無線傳感器網(wǎng)絡(luò)使用多跳的傳輸方式傳遞信息，無線傳感器網(wǎng)絡(luò)傳輸能力有限。k元n立方體和超立方體由很多相似之處，具有對稱性、低傳輸時延、直徑短等性質(zhì)，相比二元超立方體在維數(shù)相同的情況下能夠容納更多的節(jié)點(diǎn)，更適用于部署大量無線傳感器節(jié)點(diǎn)的情況[5]。k元n立方體的無線傳感器網(wǎng)絡(luò)的廣播按照維序?qū)剑档蜔o線網(wǎng)絡(luò)傳播沖突，減少數(shù)據(jù)傳輸?shù)娜哂?，由于直徑短，傳輸?shù)據(jù)需要的跳數(shù)少，減少最大端到端的時延，減少節(jié)點(diǎn)能量消耗，延長整個網(wǎng)絡(luò)壽命[6]。

參數(shù)k是沿著每個方向的節(jié)點(diǎn)數(shù)，n是立方體的維數(shù)[7]。這兩個數(shù)與網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)N的關(guān)系為：N=kn。k元n立方體的每個節(jié)點(diǎn)可以用一個n位的序列來唯一標(biāo)識[2]。一個節(jié)點(diǎn)A的地址可以表示為v0v1v2…vn-1，其中vi代表第i維節(jié)點(diǎn)的位置，并且0 ≤vi≤k-1。2元3立方體見圖1。

圖1 2元3立方體Fig.1 2-ary 3-cube

定義漢明距離H(U，V)，對于二進(jìn)制編碼即節(jié)點(diǎn)編號相差的位數(shù)。例如V1=000，V2=001，H(V1，V2)=1，V1、V2這個兩個頂點(diǎn)編號只差一位，即漢明距離為1,V3=111，H(V1，V3)=3，V1，V3這個兩個頂點(diǎn)編號相差三位，即漢明距離為3。

定義Vi的鄰居集合NBi，即漢明距離H(U，V)=1的頂點(diǎn)集合。例如V1=000的鄰居是U1=001，U2=010，U3=100，NB1={U1，U2，U3}；V2=001的鄰居是U4=000，U5=002，U6=011，U7=101，NB2={U4，U5，U6，U7}。

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

圖G(V，E，C)，其中V={V1，V2，V3，…，Vn}是圖中的頂點(diǎn)集合，圖G中每個頂點(diǎn)代表無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)。C={C1，C2，C3，…，Cn}是可用的信道集合。E={e(i，j，k)|Vi∈V，Vj∈V，Ck∈C}是圖中的邊集，如果Vi、Vj在無線發(fā)射機(jī)的傳輸范圍內(nèi)，并且節(jié)點(diǎn)Vi、Vj使用相同的信道Ck,則Vi、Vj之間有邊相連。

沖突定義，兩個節(jié)點(diǎn)同時向同一節(jié)點(diǎn)發(fā)送數(shù)據(jù)時，數(shù)據(jù)傳輸時就會沖突碰撞。目的節(jié)點(diǎn)接收不到正確的數(shù)據(jù)信息,見圖2。

圖2 節(jié)點(diǎn)沖突Fig.2 Conflict

定義CS(Collision Set)為沖突集合，當(dāng)兩個節(jié)點(diǎn)同時發(fā)給另一個節(jié)點(diǎn)時，數(shù)據(jù)信息在傳輸過程中遇到了沖突，目的節(jié)點(diǎn)不會收到正確的信息。例如001發(fā)送數(shù)據(jù)給011，001加入CS集合。010要發(fā)送數(shù)據(jù)給011，首先查詢CS集合找到011節(jié)點(diǎn)，說明010這時發(fā)送給011時會遇到?jīng)_突碰撞，010需要等待下一個時間步再發(fā)送數(shù)據(jù)。假設(shè)拓?fù)浣Y(jié)構(gòu)中的每個節(jié)點(diǎn)已知自身的地址編碼。

2 基于k元n立方體的廣播算法

2.1 廣播算法

本文中的k元n立方體使用了多Radio多Channel，在立方體的頂點(diǎn)上使用單獨(dú)的具有遠(yuǎn)距離通信的信道C2，使其在立方體的頂點(diǎn)上一跳通信，其他除去立方體的頂點(diǎn)具有通信距離較近的信道C1，通過多跳的傳輸方式，節(jié)約能量，立方體的頂點(diǎn)上配有兩個Radio實(shí)現(xiàn)C1、C2信道。其他除去立方體的最外層頂點(diǎn)只使用單Radio,單Channel，并且Radio使用C1信道。

算法使用的參數(shù)定義見表1。

表1 算法參數(shù)定義

計算鄰居算法見表2，該算法用于計算鄰居節(jié)點(diǎn)的集合。通過計算得到鄰居節(jié)點(diǎn)集合可為CACB算法使用。有了鄰居節(jié)點(diǎn)集合就可以計算CS沖突集合。CS用來限制每一步數(shù)據(jù)信息怎樣傳輸，使得傳輸數(shù)據(jù)時不會遇到?jīng)_突，重傳數(shù)據(jù)。

表2 算法1 鄰居算法NA

算法2 CACB沖突避免立方體廣播算法集中計算全網(wǎng)絡(luò)的節(jié)點(diǎn)應(yīng)該在每個時間步進(jìn)行如何接收數(shù)據(jù)、轉(zhuǎn)發(fā)數(shù)據(jù)，而不需要數(shù)據(jù)傳輸或者數(shù)據(jù)信息接收時，傳感器節(jié)點(diǎn)可以進(jìn)入休眠狀態(tài)來節(jié)約節(jié)點(diǎn)的能量，在需要數(shù)據(jù)傳輸或者數(shù)據(jù)信息接收時，提前喚醒即可。算法采用時鐘同步，每個節(jié)點(diǎn)使用CACB算法得到的VTS，得到自身在哪個時間步接收數(shù)據(jù)、哪個時間步發(fā)送數(shù)據(jù)不會沖突。在確定的時間步，接收發(fā)送數(shù)據(jù),算法2見表3。

表3 算法2 沖突避免算法

2.2 基于k元n立方體廣播算法CACB實(shí)例

例如圖3中2元3立方體的廣播過程。線上的數(shù)字代表第多少時間步轉(zhuǎn)發(fā)了數(shù)據(jù)信息。圖4用樹形圖描繪出節(jié)點(diǎn)發(fā)送信息的過程，樹的高度即為廣播過程需要的時間步數(shù)。

圖3 2元3立方體節(jié)點(diǎn)在每個時間步發(fā)送過程Fig.3 Broadcast process of 2-ary 3-cube

圖4 2元3立方體樹形圖描繪廣播過程Fig.4 Broadcast tree of 2-ary 3-cube.

3 仿真實(shí)驗(yàn)與性能評估

仿真實(shí)驗(yàn)使用OPNET軟件進(jìn)行模擬[8]。泛洪的節(jié)點(diǎn)是在200 m×200 m的區(qū)域內(nèi)。本文使用的k元3立方體，其中k=2、3、4、5、6、7分別對應(yīng)8、27、64、125、216、343個節(jié)點(diǎn)進(jìn)行仿真實(shí)驗(yàn)[9]。

首先對比CACB與傳統(tǒng)的FLOOD算法、PB算法的最大端到端時延，即傳輸跳數(shù)的比較。其中PB算法采用P=0.8的概率轉(zhuǎn)發(fā)數(shù)據(jù)信息，見圖5。CACB與傳統(tǒng)的算法相比，在相同節(jié)點(diǎn)數(shù)量的情況下，最大傳輸跳數(shù)明顯減少，即最大端到端時延明顯降低。因?yàn)椴捎肅ACB算法使用的是k元n立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，k元n立方體網(wǎng)絡(luò)有其自身的優(yōu)勢，按照本文提出的算法，廣播時不存在沖突碰撞的可能，并且由于網(wǎng)絡(luò)的直徑短，即傳輸?shù)奶鴶?shù)減少了。

圖5 端到端時延Fig.5 End-to-end delay

其次對比CACB與傳統(tǒng)的FLOOD算法、PB算法的能量消耗。其中PB算法采用P=0.8的概率轉(zhuǎn)發(fā)數(shù)據(jù)信息，見圖6。CACB與傳統(tǒng)的算法相比，在相同節(jié)點(diǎn)數(shù)量的情況下，節(jié)點(diǎn)發(fā)送總次數(shù)明顯減少，即節(jié)點(diǎn)能量消耗明顯降低。因?yàn)镃ACB算法，按時間步發(fā)送數(shù)據(jù)，形成廣播樹，每個節(jié)點(diǎn)只發(fā)送一次數(shù)據(jù)，所有節(jié)點(diǎn)的總發(fā)送次數(shù)要明顯比FLOOD和PB算法要少。

圖6 節(jié)點(diǎn)能量消耗Fig.6 Energy consumption

最后對比CACB與傳統(tǒng)的FLOOD算法、PB算法的吞吐量。其中PB算法采用P=0.8的概率轉(zhuǎn)發(fā)數(shù)據(jù)信息,見圖7。CACB與傳統(tǒng)的算法相比，在相同節(jié)點(diǎn)數(shù)量的情況下，廣播一次的時間步數(shù)少，即節(jié)點(diǎn)每個時間步的傳輸數(shù)據(jù)分組多。

圖7 吞吐量Fig.7 Throughput

4 結(jié) 語

本文提出的算法CACB是在k元n立方體的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來進(jìn)行廣播。CACB算法采用時鐘準(zhǔn)同步的方法，確定每一個時間步中每個節(jié)點(diǎn)應(yīng)該如何去路由信息，避免了傳輸數(shù)據(jù)時遇到的沖突碰撞，最終路由到網(wǎng)絡(luò)中所有節(jié)點(diǎn)，完成廣播。實(shí)驗(yàn)使用OPNET軟件進(jìn)行仿真，仿真結(jié)果表明基于k元n立方體的無線傳感器網(wǎng)絡(luò)的廣播算法CACB和傳統(tǒng)的廣播策略相比，能夠減少最大端到端的時延，降低網(wǎng)絡(luò)沖突，減少節(jié)點(diǎn)能量消耗，延長整個網(wǎng)絡(luò)壽命，提高了網(wǎng)絡(luò)的吞吐量。

[1]李建中, 李金寶, 石勝飛. 傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展 [J]. 軟件學(xué)報, 2003，14(10):1 717-1 727.

[2]Kai H. 高等計算機(jī)系統(tǒng)結(jié)構(gòu) 并行性 可擴(kuò)展性 可編程性[M]. 北京:清華大學(xué)出版社,1995: 67-70.

[3]Ni S, Tseng Y, Sheu J.The broadcast storm problem in a mobile ad hoc network[J].2002,8:153-167.

[4]Wei Y, John H, Deborah E.An energy-effcient MAC protocol for wireless sensor networks[C].Proc. INFOCOM, 2002:1 567-1 576.

[5] Chang C T,Chang C Y,Sheu J P.Bluecube: constructing a hypercube parallel computing and communication environment over bluetooth radio system[C].Proc. International Conference on Parallel Processing (ICPP), 2003:447-454.

[6]Manoharan R, Thambidurai P.Hypercube based team multicast routing protocol for mobile ad hoc networks[C].Proc. International Conference on Information Technology (ICIT). 2006.

[7]Wu J,Wang Y S.Social feature-based multi-path routing in delay tolerant networks[C].Proc. INFOCOM, 2012:1 368-1 376.

[8]Habib S, Marimuthu P.Optimized capacity planning and performance measurement through OPNET Modele[C].Proc. Computer Applications and Industrial Electronics (ICCAIE), 2010:43-48.

[9]Emad A.Network Simulation Experiments Manual[M].Beijing:China Mechine Press,2011:1-20.

A broadcast strategy based on K-ary N-cube topology in wireless sensor networks

LI Jin-Bao1a,2, NI Lin-Yu1a,2,GUO Ya-Hong1b,REN Qian-Qian1a,2

(1.Heilongjiang University, a.School of Computer Science and Technology;b.School of Information Management, Harbin 150080, China; 2.Key Laboratory of Database and Parallel Computing of Heilongjiang Province, Harbin 150080, China)

The wireless sensor network broadcast strategy is mainly researched, it proposes a collision avoidance cube broadcast algorithm CACB. The CACB algorithm uses quasi-synchronous clock and the dimension order routing to determine each time step which should be to routing information and each time step select the determine nodes forward data. The experiment uses the OPNET simulation software, simulation results show broadcast strategy for wireless sensor networks based onk-aryn-cube compared to traditional broadcast strategy that can reduce the maximum end-to-end delay, reduce network conflicts, reduce node energy consumption, prolong the life of the entire network and improve the throughput.

wireless sensor networks; broadcast;k-aryn-cube; throughput; end-to-end delay

10.13524/j.2095-008x.2014.01.014

2014-01-19

國家自然科學(xué)基金項目(61370222，61300225)；黑龍江省自然科學(xué)基金項目(F201324);黑龍江省教育廳科學(xué)技術(shù)研究項目(12521404)；黑龍江省高?？萍紕?chuàng)新團(tuán)隊建設(shè)計劃項目(2013TD12)

李金寶(1969-)，男，黑龍江慶安人，教授，博士，研究方向:無線傳感器網(wǎng)絡(luò)、數(shù)據(jù)庫、并行計算等。

TP393

A

2095-008X(2014)01-0064-05