方格拓撲無線傳感器網絡源路由策略的能耗分析*

吳騰飛，熊慶國，李文翔,2，陳 騫

(1.武漢科技大學 信息科學與工程學院，湖北 武漢 430081；2.武漢科技大學 冶金工業過程系統科學湖北省重點實驗室，湖北 武漢 430081)

方格拓撲無線傳感器網絡源路由策略的能耗分析*

吳騰飛1，熊慶國1，李文翔1,2，陳 騫1

(1.武漢科技大學 信息科學與工程學院，湖北 武漢 430081；2.武漢科技大學 冶金工業過程系統科學湖北省重點實驗室，湖北 武漢 430081)

無線傳感器網絡(WSNs)中的匯聚傳輸模式使得靠近匯點的節點承擔了較多的數據轉發業務，導致這些節點能量很快耗盡，降低網絡的壽命。針對這種問題，結合規則拓撲結構的對稱性和預知性，對方格拓撲結構中多種典型源路由策略進行分析，分別計算各策略的瓶頸節點負載和數據傳輸時延，提出能耗的計算模型，并據此探討網絡節點的通信能耗、待機能耗和總能耗。數值分析結果表明：均衡轉發策略產生最小的總能耗。

無線傳感器網絡；方格拓撲；源路由策略；負載；能耗

0 引 言

在無線傳感器網絡(WSNs)中，采用規則拓撲結構能高效實現節點的連通和采集信號的感知覆蓋，提升網絡的運行效率和延長網絡壽命[1]。同時利用拓撲的預知性和對稱性，也能設計出源路由策略，避免按需路由策略的動態路由發生開銷和表驅動路由策略所帶來的路由表維護開銷，能顯著提升傳輸效率、降低傳輸能耗。

最初在方格拓撲結構中所探討的是隨機游走策略。文獻[2]指出應用隨機游走策略能夠節省能耗并達到均衡負載。文獻[3]提出方格拓撲中的4鄰節點、8鄰節點和12鄰節點共3種隨機游走方案，仿真指出,在能耗相當的情況下，8鄰節點方案在時延和路徑效率上優于4鄰節點方案。文獻[4]利用局部拓撲信息來降低網絡時延，分析了不同方向路徑的有效概率，給出隨機游走平均時延的精確表達。文獻[5,6]分析了隨機游走傳輸時延的上下限，并提出了在r-nearest cycle和torus Grid這2種拓撲結構中隨機游走路由的時延表達式。

為改進隨機游走路由策略傳輸效率較低的問題，文獻[2]在拓撲對稱性的基礎上，提出路由協議DSAP。該協議不需要路由表，為每個節點分配一個向量標識符，標識節點與各個邊界相隔的節點數目。文獻[7,8]提出了基于輪廓Contour的Optimal Spreading源路由研究方法，仿真實驗驗證了其能均衡利用各路徑并提升QoS。文獻[9]在一對一傳輸和多對一傳輸的基礎上，對比了對角線傳輸和直線傳輸2種源路由策略的負載分布。

以上研究側重于傳輸效率與負載均衡性，但是在傳感網數據采集過程中，各節點產生的數據集中匯聚到匯點，對匯點及其附近節點造成很大的運行開銷[10,11]。針對這種匯聚傳輸特性和問題的能耗及網絡壽命的研究還很少。

本文通過探討面向方格拓撲結構中向Sink節點匯聚傳輸的各種源路由策略，包括隨機等概率(random equal probability,REP)轉發、直線(line)轉發、源點對角(source-ZigZag,SZ)轉發、匯點對角(destination-ZigZag，DZ)轉發、均衡(balance)轉發，從瓶頸節點負載和數據傳輸時延的角度展開，提出了方格拓撲結構中的能耗分析模型，并對各路由策略的能耗特性進行了分析比較。

2 方格拓撲結構中瓶頸節點負載和傳輸時延

2.1 典型路由策略

給定直角坐標系中的方格拓撲如圖1所示，其中左下角為黑色的匯點，其它節點為源點，橫向上最大節點坐標為im，縱向上最大節點坐標為jm。設一個采集周期內，每個節點發送一個數據包，其可能向下鄰點轉發，也可能向左鄰點轉發，對應的源路由策略有5種：

圖1 源點對角轉發路徑Fig 1 Path of source point ZigZag forwarding

1)REP轉發

從數據包所在點以相同概率選擇下鄰點和左鄰點作為中轉節點，到達軸后沿軸向原點轉發。

2)直線(line)轉發

從數據包產生點先一直向橫軸或縱軸轉發，選擇2個方向的概率相同，到達軸后再向匯點轉發。

3)SZ轉發

從數據包產生點一直向左下方點轉發，選擇下鄰點和左鄰點作為中轉節點的概率相同，遇到軸則沿軸向原點轉發。圖1中采用此方式后，來自A(i,j)節點的數據包可能經歷的節點用斜紋標出。

4)DZ轉發

從數據包所在點向匯點所在45°線沿水平或垂直方向傳輸，到達此線后則向左下方點轉發，直到匯點，選擇下鄰點和左鄰點作為中轉節點的概率相同。圖2中采用此方式后，來自A(i,j)節點的數據包可能經歷的節點用斜紋標出。

圖2 DZ轉發路徑Fig 2 Path of DZ forwarding

5)均衡(balance)轉發

圖3 均衡轉發路徑Fig 3 Path of balanced forwarding

2.2 各路由策略的瓶頸節點負載

由于匯聚轉發特性，在Sink節點附近會產生負載集中現象，這種負載最大的節點稱為負載瓶頸點。采用轉發指數分析作為負載的評價指標，其定義為某坐標節點接收來自它四周相鄰節點發出的數據包數量。各節點可能從上鄰點和右鄰點收到包，向下鄰點和左鄰點轉發包，考慮im>jm的情況，瓶頸節點位于坐標(1,0)。

(1)

圖4 REP轉發策略中的節點累積轉發概率Fig 4 Cumulative forwarding probability of node in REP forwarding strategy

其它轉發策略的瓶頸節點轉發指數如下

F(1,0)Line=im·(1+jm/2),

(2)

F(1,0)SZ=(2jm·im+2im-jm·jm)/2,

(3)

F(1,0)DZ=im·jm/2+im,

(4)

F(1,0)Balance=(im·jm+im+jm)/2.

(5)

2.3 各路由策略的傳輸時延

給定路徑有效概率p，文獻[4]中指出在拓撲中，邊界節點向Sink節點僅有1條轉發路徑(1-choice)，兩點間傳輸的平均等效跳數為1/p，而內部節點有2條轉發路徑(2-choice)，兩點間傳輸的平均等效跳數為1/[1-(1-p)2]。對應得到采用不同路由協議將數據包從最遠點(im,jm)傳到Sink節點的時延即最大時延如下：

對REP,SZ,DZ轉發，最遠數據采集點平均經過2-choice節點2jm個，經過1-choice節點(im-jm)個，最大跳數為

(6)

對Line轉發，最遠數據采集點平均經過2-choice節點0個，經過1-choice節點im+jm個，最大跳數為

(7)

(8)

3 能耗模型

網絡運行能耗由兩部分組成，包括取決于負載的傳輸能耗和取決于運行時間的待機能耗[12,13]。

3.1 瓶頸節點傳輸能耗

文獻[14～16]給出了一個傳輸能耗模型，其中節點發送kbit數據至距離dm處的能耗為

et(k,d)=k·(ete+εad2).

(9)

節點接收kbit數據的能耗為

er(k)=k·ere.

(10)

其中，ete為發射電路單位能耗，εa為功率放大電路單位能耗，ere為接收電路單位能耗。

完成一次數據傳輸包括接收DATA包(DATA-R)、發送對應的ACK包(ACK-S)、轉發DATA包(DATA-S)、接收對應的ACK包(ACK-R)4個步驟。假定DATA包和ACK包的長度均為Lenbyte，成功接收DATA包后則一定能成功發送ACK包，且成功發送DATA包后則一定能成功接收ACK包，考慮轉發DATA包的路徑失效的可能性，發送一個DATA包的傳輸次數實際為1/p，基于以上能耗模型得出瓶頸節點處理一個采集周期內的數據包的能耗為

ETr=EDATA-R+EACK-S+EDATA-S+EACK-S

=L(1,0)Len((1+1/p)(ete+εad2)+2ere).

(11)

3.2 待機能耗

最大待機能耗取決于節點待機能耗和待機時間，而待機時間又取決于傳輸跳數和單跳時延(4個步驟的數據包長度Len/鏈路帶寬BW)，則有

EON=PON·TON≈4PON·H·Len/BW.

(12)

4 數值分析

基于IEEE 802.15.4協議，取BW=250 kbit/s，Len=125 byte，依據式(12)取PON=40 mW，εa=100 pJ/bit，ete=ere=50 nJ/bit。在im=50，jm=30的方格拓撲中，得到p從0.8變化至1時的傳輸能耗、待機能耗和總能耗，如圖5～圖7所示。

從圖5看出:在相同條件下，SZ轉發的傳輸能耗最大，其次是REP轉發，Line,DZ,Balance 3種路由策略的傳輸能耗則小很多，體現了這3種策略的瓶頸節點具有較小的負載。

圖5 各路由策略的最大傳輸能耗Fig 5 The maximum energy consumption for transmission of different routing strategies

圖6 各路由策略的最大待機能耗Fig 6 The maximum energy consumption for standing-by of different routing strategies

圖7 各路由策略的總能耗Fig 7 The overall energy consumption of different routing strategies

由圖6看出:Line轉發策略跟隨路徑有效概率p的變化比較明顯，Balance策略跟隨p有微小的變化，其它3種策略基本不隨p變化。在p較小時，Line策略的待機時延和能耗較大。

在總能耗方面,看出SZ策略最大，其次是REP策略，而Balance策略總能耗最低。隨路徑有效概率p增大，除Line策略外的各策略的總能耗值略微下降。瓶頸節點承擔很重的數據轉發任務，故其傳輸能耗略大于待機能耗。

5 結束語

本文分析了多種源路由策略的瓶頸節點負載和最大待機時延，設計了方格拓撲中傳輸的能耗模型，數值分析比較了各策略的傳輸能耗、待機能耗及總能耗，指出負載均衡轉發策略具有最小的總能耗、而直線轉發和隨機等概率轉發策略的能耗較大。

[1] Zhang Xue,Lu Sanglu,Chen Guihai,et al.Topology control for wireless sensor networks[J].Journal of Software,2007,18(4):943-954.

[2] Salhieh Ayad,Weinmann Jennifer,Kochhal Manish,et al.Power efficient topologies for wireless sensor networks[C]∥Proc of International Conference on Parallel Processing，Valencia,Spain,2001：156-163.

[3] Hui Tian,Hong Shen,Teruo Matsuzawa.Random walk routing in WSNs with regular topologies[J].Journal of Computer Science and Technology,2006,21(4):496-502.

[4] Prithwish Basu,Saikat Guha.Effect of limited topology knowledge on opportunistic forwarding in Ad Hoc wireless networks[C]∥Proc of 8th International Symposium on Modeling and Optimiza-tion in Mobile,Ad Hoc,and Wireless Networks,Avignon,France,2010:71-80.

[5] Basu Prithwish,Chau Chi-Kin.Latency of opportunistic forwarding in finite regular wireless networks[C]∥Proc of 5th International Workshop on Foundations of Mobile Computing，Toronto,Canada,2008:55-63.

[6] Chau Chi-Kin,Basu Prithwish.Exact analysis of latency of stateless opportunistic forwarding[C]∥Proc of IEEE INFOCOM，Rio de Janeiro,Brazil,2009:828-836.

[7] Mamidisetty K K.Generalizing contour guided dissemination in mesh topologies[D].Akron,USA:University of Akron,2008.

[8] Mamidisetty Kranthi K,Duan Minlan,Sastry Shivakumar,et al.Multipath dissemination in regular mesh topologies[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(8):1188-1201.

[9] Liu Xiaowen.Performance analysis and topology control of large wireless networks with fading[D].Notre Dame,USA:University of Notre Dame,2007.

[10] 候忠偉.基于拓撲控制的無線傳感器網絡節點負載均衡策略[J].信息通信,2011,116(6):111-112.

[11] Yin An,Wang Bingwen,Hu Xiaoya,et al.Wireless sensor networks routing protocol for load balancing[J].Huazhong University of Science & Technology :Natural Science Edition,2010,38(1):88-91.

[12] Wang Xue,Ding Liang,Wang Sheng,et al.Multi-step optimized measurement in hierarchically clustered wireless sensor network-s[J].Journal of Mechanical Engineering,2009,45(4):1-7.

[13] Wei Yonghong,Li Kejie.Energy model for wireless sensor networks based on hierarchical topology[J].Journal of Computer Applications,2010,30(7):1731-1735.

[14] Niu Xing,Li Jie,Zhou Xinyun,et al.Measurement and analysis to wireless sensor networks node energy consumption[J].Computer Science,2012,39(2):84-87.

[15] Zhou Haiying ,Luo Danyan,Gao Yan,et al.Modeling of node energy consumption for wireless sensor networks[J].Wireless Sensor Networks,2011,3:18-23.

[16] Chen Yongjun,Yuan Shenfang.Minimum energy consumption topology control for wireless sensor networks[J].Journal of University of Electronic Science and Technology of China,2012,41(4):569-573.

Analysis on energy consumption for source routing strategy in WSNs of square lattice topology*

WU Teng-fei1, XIONG Qing-guo1, LI Wen-xiang1,2, CHEN Qian1

(1.School of Information Science and Engineering,Wuhan University of Science and Technology,Wuhan 430081,China; 2.Key Laboratory of Metallurgical Industry Process Systems of Hubei Province,Wuhan University of Science and Technology,Wuhan 430081,China)

Concentration transmission mode poses larger burden on the nodes near sink node in wireless sensor networks,so these nodes are prone to running out of energy early with decreased network lifetime.To deal with the problem,analyze the typical source routing strategies in square lattice topology structure based on symmetry and predictability of regular topological structure,calculate load of bottleneck node and data transmission delay of each strategy,propose calculation model for energy consumption,and discuss energy consumption for communication,standing-by and totality of network node.Numerical analysis shows that balance forwarding strategy leads to minimal overall energy consumption.

wireless sensor networks(WSNs); square lattice topology; source routing strategy; load; energy consumption

10.13873/J.1000—9787(2014)10—0036—04

2014—03—10

國家自然科學基金資助項目(61174106)；湖北省教育廳科學研究計劃資助項目(Q20141110)；冶金工業過程系統科學湖北省重點實驗室(武漢科技大學)開放基金資助項目(Y201322)；武漢科技大學大學生創新基金資助項目(12ZRC115)

TP 393

A

1000—9787(2014)10—0036—04

吳騰飛(1984-)，男，碩士研究生，主要研究領域為無線傳感器網絡。