基于k元n立方體拓撲的無線傳感器網絡廣播策略

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

(1.黑龍江大學 a.計算機科學技術學院;b.信息科學技術學院，哈爾濱 150080；2．黑龍江省數據庫與并行計算重點實驗室，哈爾濱 150080)

基于k元n立方體拓撲的無線傳感器網絡廣播策略

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

(1.黑龍江大學 a.計算機科學技術學院;b.信息科學技術學院，哈爾濱 150080；2．黑龍江省數據庫與并行計算重點實驗室，哈爾濱 150080)

研究了無線傳感器網絡的廣播策略，提出一個沖突避免立方體廣播算法CACB(Collision Avoidance Cube Broadcast)。CACB基于對k元n立方體結構的網絡研究廣播策略。CACB算法采用時鐘準同步的方法，按照為序尋徑的方式，確定每一個時間步應該如何去路由信息。實驗使用OPNET軟件進行仿真，仿真結果表明基于k元n立方體的無線傳感器網絡的廣播算法CACB和傳統的廣播策略相比，能夠減少最大端到端的時延，降低網絡沖突，減少節點能量消耗，延長整個網絡壽命,提高了網絡的吞吐量。

無線傳感器網絡；廣播；k元n立方體；吞吐量；端到端時延

0 引 言

無線傳感器網絡目前已經在國防軍事、智能家居、城市小區安全監控、環境監測和預報、醫療狀況監控、深海監控、目標跟蹤和檢測、森林火災監控等眾多領域得到了廣泛應用[1]。

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

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

1 相關知識與網絡模型

1.1 相關知識

無線傳感器網絡的特點是無線傳感器節點能量有限，無線傳感器網絡使用多跳的傳輸方式傳遞信息，無線傳感器網絡傳輸能力有限。k元n立方體和超立方體由很多相似之處，具有對稱性、低傳輸時延、直徑短等性質，相比二元超立方體在維數相同的情況下能夠容納更多的節點，更適用于部署大量無線傳感器節點的情況[5]。k元n立方體的無線傳感器網絡的廣播按照維序尋徑，降低無線網絡傳播沖突，減少數據傳輸的冗余，由于直徑短，傳輸數據需要的跳數少，減少最大端到端的時延，減少節點能量消耗，延長整個網絡壽命[6]。

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

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

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

定義Vi的鄰居集合NBi，即漢明距離H(U，V)=1的頂點集合。例如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 網絡模型

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

沖突定義，兩個節點同時向同一節點發送數據時，數據傳輸時就會沖突碰撞。目的節點接收不到正確的數據信息,見圖2。

圖2 節點沖突Fig.2 Conflict

定義CS(Collision Set)為沖突集合，當兩個節點同時發給另一個節點時，數據信息在傳輸過程中遇到了沖突，目的節點不會收到正確的信息。例如001發送數據給011，001加入CS集合。010要發送數據給011，首先查詢CS集合找到011節點，說明010這時發送給011時會遇到沖突碰撞，010需要等待下一個時間步再發送數據。假設拓撲結構中的每個節點已知自身的地址編碼。

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

2.1 廣播算法

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

算法使用的參數定義見表1。

表1 算法參數定義

計算鄰居算法見表2，該算法用于計算鄰居節點的集合。通過計算得到鄰居節點集合可為CACB算法使用。有了鄰居節點集合就可以計算CS沖突集合。CS用來限制每一步數據信息怎樣傳輸，使得傳輸數據時不會遇到沖突，重傳數據。

表2 算法1 鄰居算法NA

算法2 CACB沖突避免立方體廣播算法集中計算全網絡的節點應該在每個時間步進行如何接收數據、轉發數據，而不需要數據傳輸或者數據信息接收時，傳感器節點可以進入休眠狀態來節約節點的能量，在需要數據傳輸或者數據信息接收時，提前喚醒即可。算法采用時鐘同步，每個節點使用CACB算法得到的VTS，得到自身在哪個時間步接收數據、哪個時間步發送數據不會沖突。在確定的時間步，接收發送數據,算法2見表3。

表3 算法2 沖突避免算法

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

例如圖3中2元3立方體的廣播過程。線上的數字代表第多少時間步轉發了數據信息。圖4用樹形圖描繪出節點發送信息的過程，樹的高度即為廣播過程需要的時間步數。

圖3 2元3立方體節點在每個時間步發送過程Fig.3 Broadcast process of 2-ary 3-cube

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

3 仿真實驗與性能評估

仿真實驗使用OPNET軟件進行模擬[8]。泛洪的節點是在200 m×200 m的區域內。本文使用的k元3立方體，其中k=2、3、4、5、6、7分別對應8、27、64、125、216、343個節點進行仿真實驗[9]。

首先對比CACB與傳統的FLOOD算法、PB算法的最大端到端時延，即傳輸跳數的比較。其中PB算法采用P=0.8的概率轉發數據信息，見圖5。CACB與傳統的算法相比，在相同節點數量的情況下，最大傳輸跳數明顯減少，即最大端到端時延明顯降低。因為采用CACB算法使用的是k元n立方體網絡拓撲結構，k元n立方體網絡有其自身的優勢，按照本文提出的算法，廣播時不存在沖突碰撞的可能，并且由于網絡的直徑短，即傳輸的跳數減少了。

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

其次對比CACB與傳統的FLOOD算法、PB算法的能量消耗。其中PB算法采用P=0.8的概率轉發數據信息，見圖6。CACB與傳統的算法相比，在相同節點數量的情況下，節點發送總次數明顯減少，即節點能量消耗明顯降低。因為CACB算法，按時間步發送數據，形成廣播樹，每個節點只發送一次數據，所有節點的總發送次數要明顯比FLOOD和PB算法要少。

圖6 節點能量消耗Fig.6 Energy consumption

最后對比CACB與傳統的FLOOD算法、PB算法的吞吐量。其中PB算法采用P=0.8的概率轉發數據信息,見圖7。CACB與傳統的算法相比，在相同節點數量的情況下，廣播一次的時間步數少，即節點每個時間步的傳輸數據分組多。

圖7 吞吐量Fig.7 Throughput

4 結 語

本文提出的算法CACB是在k元n立方體的網絡拓撲結構來進行廣播。CACB算法采用時鐘準同步的方法，確定每一個時間步中每個節點應該如何去路由信息，避免了傳輸數據時遇到的沖突碰撞，最終路由到網絡中所有節點，完成廣播。實驗使用OPNET軟件進行仿真，仿真結果表明基于k元n立方體的無線傳感器網絡的廣播算法CACB和傳統的廣播策略相比，能夠減少最大端到端的時延，降低網絡沖突，減少節點能量消耗，延長整個網絡壽命，提高了網絡的吞吐量。

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

[2]Kai H. 高等計算機系統結構 并行性 可擴展性 可編程性[M]. 北京:清華大學出版社,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

國家自然科學基金項目(61370222，61300225)；黑龍江省自然科學基金項目(F201324);黑龍江省教育廳科學技術研究項目(12521404)；黑龍江省高校科技創新團隊建設計劃項目(2013TD12)

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

TP393

A

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