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

(1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081；2.武漢科技大學(xué) 冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081)

方格拓?fù)錈o線傳感器網(wǎng)絡(luò)源路由策略的能耗分析*

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

(1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081；2.武漢科技大學(xué) 冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081)

無線傳感器網(wǎng)絡(luò)(WSNs)中的匯聚傳輸模式使得靠近匯點(diǎn)的節(jié)點(diǎn)承擔(dān)了較多的數(shù)據(jù)轉(zhuǎn)發(fā)業(yè)務(wù)，導(dǎo)致這些節(jié)點(diǎn)能量很快耗盡，降低網(wǎng)絡(luò)的壽命。針對這種問題，結(jié)合規(guī)則拓?fù)浣Y(jié)構(gòu)的對稱性和預(yù)知性，對方格拓?fù)浣Y(jié)構(gòu)中多種典型源路由策略進(jìn)行分析，分別計(jì)算各策略的瓶頸節(jié)點(diǎn)負(fù)載和數(shù)據(jù)傳輸時延，提出能耗的計(jì)算模型，并據(jù)此探討網(wǎng)絡(luò)節(jié)點(diǎn)的通信能耗、待機(jī)能耗和總能耗。數(shù)值分析結(jié)果表明：均衡轉(zhuǎn)發(fā)策略產(chǎn)生最小的總能耗。

無線傳感器網(wǎng)絡(luò)；方格拓?fù)?；源路由策略；?fù)載；能耗

0 引 言

在無線傳感器網(wǎng)絡(luò)(WSNs)中，采用規(guī)則拓?fù)浣Y(jié)構(gòu)能高效實(shí)現(xiàn)節(jié)點(diǎn)的連通和采集信號的感知覆蓋，提升網(wǎng)絡(luò)的運(yùn)行效率和延長網(wǎng)絡(luò)壽命[1]。同時利用拓?fù)涞念A(yù)知性和對稱性，也能設(shè)計(jì)出源路由策略，避免按需路由策略的動態(tài)路由發(fā)生開銷和表驅(qū)動路由策略所帶來的路由表維護(hù)開銷，能顯著提升傳輸效率、降低傳輸能耗。

最初在方格拓?fù)浣Y(jié)構(gòu)中所探討的是隨機(jī)游走策略。文獻(xiàn)[2]指出應(yīng)用隨機(jī)游走策略能夠節(jié)省能耗并達(dá)到均衡負(fù)載。文獻(xiàn)[3]提出方格拓?fù)渲械?鄰節(jié)點(diǎn)、8鄰節(jié)點(diǎn)和12鄰節(jié)點(diǎn)共3種隨機(jī)游走方案，仿真指出,在能耗相當(dāng)?shù)那闆r下，8鄰節(jié)點(diǎn)方案在時延和路徑效率上優(yōu)于4鄰節(jié)點(diǎn)方案。文獻(xiàn)[4]利用局部拓?fù)湫畔斫档途W(wǎng)絡(luò)時延，分析了不同方向路徑的有效概率，給出隨機(jī)游走平均時延的精確表達(dá)。文獻(xiàn)[5,6]分析了隨機(jī)游走傳輸時延的上下限，并提出了在r-nearest cycle和torus Grid這2種拓?fù)浣Y(jié)構(gòu)中隨機(jī)游走路由的時延表達(dá)式。

為改進(jìn)隨機(jī)游走路由策略傳輸效率較低的問題，文獻(xiàn)[2]在拓?fù)鋵ΨQ性的基礎(chǔ)上，提出路由協(xié)議DSAP。該協(xié)議不需要路由表，為每個節(jié)點(diǎn)分配一個向量標(biāo)識符，標(biāo)識節(jié)點(diǎn)與各個邊界相隔的節(jié)點(diǎn)數(shù)目。文獻(xiàn)[7,8]提出了基于輪廓Contour的Optimal Spreading源路由研究方法，仿真實(shí)驗(yàn)驗(yàn)證了其能均衡利用各路徑并提升QoS。文獻(xiàn)[9]在一對一傳輸和多對一傳輸?shù)幕A(chǔ)上，對比了對角線傳輸和直線傳輸2種源路由策略的負(fù)載分布。

以上研究側(cè)重于傳輸效率與負(fù)載均衡性，但是在傳感網(wǎng)數(shù)據(jù)采集過程中，各節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)集中匯聚到匯點(diǎn)，對匯點(diǎn)及其附近節(jié)點(diǎn)造成很大的運(yùn)行開銷[10,11]。針對這種匯聚傳輸特性和問題的能耗及網(wǎng)絡(luò)壽命的研究還很少。

本文通過探討面向方格拓?fù)浣Y(jié)構(gòu)中向Sink節(jié)點(diǎn)匯聚傳輸?shù)母鞣N源路由策略，包括隨機(jī)等概率(random equal probability,REP)轉(zhuǎn)發(fā)、直線(line)轉(zhuǎn)發(fā)、源點(diǎn)對角(source-ZigZag,SZ)轉(zhuǎn)發(fā)、匯點(diǎn)對角(destination-ZigZag，DZ)轉(zhuǎn)發(fā)、均衡(balance)轉(zhuǎn)發(fā)，從瓶頸節(jié)點(diǎn)負(fù)載和數(shù)據(jù)傳輸時延的角度展開，提出了方格拓?fù)浣Y(jié)構(gòu)中的能耗分析模型，并對各路由策略的能耗特性進(jìn)行了分析比較。

2 方格拓?fù)浣Y(jié)構(gòu)中瓶頸節(jié)點(diǎn)負(fù)載和傳輸時延

2.1 典型路由策略

給定直角坐標(biāo)系中的方格拓?fù)淙鐖D1所示，其中左下角為黑色的匯點(diǎn)，其它節(jié)點(diǎn)為源點(diǎn)，橫向上最大節(jié)點(diǎn)坐標(biāo)為im，縱向上最大節(jié)點(diǎn)坐標(biāo)為jm。設(shè)一個采集周期內(nèi)，每個節(jié)點(diǎn)發(fā)送一個數(shù)據(jù)包，其可能向下鄰點(diǎn)轉(zhuǎn)發(fā)，也可能向左鄰點(diǎn)轉(zhuǎn)發(fā)，對應(yīng)的源路由策略有5種：

圖1 源點(diǎn)對角轉(zhuǎn)發(fā)路徑Fig 1 Path of source point ZigZag forwarding

1)REP轉(zhuǎn)發(fā)

從數(shù)據(jù)包所在點(diǎn)以相同概率選擇下鄰點(diǎn)和左鄰點(diǎn)作為中轉(zhuǎn)節(jié)點(diǎn)，到達(dá)軸后沿軸向原點(diǎn)轉(zhuǎn)發(fā)。

2)直線(line)轉(zhuǎn)發(fā)

從數(shù)據(jù)包產(chǎn)生點(diǎn)先一直向橫軸或縱軸轉(zhuǎn)發(fā)，選擇2個方向的概率相同，到達(dá)軸后再向匯點(diǎn)轉(zhuǎn)發(fā)。

3)SZ轉(zhuǎn)發(fā)

從數(shù)據(jù)包產(chǎn)生點(diǎn)一直向左下方點(diǎn)轉(zhuǎn)發(fā)，選擇下鄰點(diǎn)和左鄰點(diǎn)作為中轉(zhuǎn)節(jié)點(diǎn)的概率相同，遇到軸則沿軸向原點(diǎn)轉(zhuǎn)發(fā)。圖1中采用此方式后，來自A(i,j)節(jié)點(diǎn)的數(shù)據(jù)包可能經(jīng)歷的節(jié)點(diǎn)用斜紋標(biāo)出。

4)DZ轉(zhuǎn)發(fā)

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

圖2 DZ轉(zhuǎn)發(fā)路徑Fig 2 Path of DZ forwarding

5)均衡(balance)轉(zhuǎn)發(fā)

圖3 均衡轉(zhuǎn)發(fā)路徑Fig 3 Path of balanced forwarding

2.2 各路由策略的瓶頸節(jié)點(diǎn)負(fù)載

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

(1)

圖4 REP轉(zhuǎn)發(fā)策略中的節(jié)點(diǎn)累積轉(zhuǎn)發(fā)概率Fig 4 Cumulative forwarding probability of node in REP forwarding strategy

其它轉(zhuǎn)發(fā)策略的瓶頸節(jié)點(diǎn)轉(zhuǎn)發(fā)指數(shù)如下

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，文獻(xiàn)[4]中指出在拓?fù)渲?，邊界?jié)點(diǎn)向Sink節(jié)點(diǎn)僅有1條轉(zhuǎn)發(fā)路徑(1-choice)，兩點(diǎn)間傳輸?shù)钠骄刃鴶?shù)為1/p，而內(nèi)部節(jié)點(diǎn)有2條轉(zhuǎn)發(fā)路徑(2-choice)，兩點(diǎn)間傳輸?shù)钠骄刃鴶?shù)為1/[1-(1-p)2]。對應(yīng)得到采用不同路由協(xié)議將數(shù)據(jù)包從最遠(yuǎn)點(diǎn)(im,jm)傳到Sink節(jié)點(diǎn)的時延即最大時延如下：

對REP,SZ,DZ轉(zhuǎn)發(fā)，最遠(yuǎn)數(shù)據(jù)采集點(diǎn)平均經(jīng)過2-choice節(jié)點(diǎn)2jm個，經(jīng)過1-choice節(jié)點(diǎn)(im-jm)個，最大跳數(shù)為

(6)

對Line轉(zhuǎn)發(fā)，最遠(yuǎn)數(shù)據(jù)采集點(diǎn)平均經(jīng)過2-choice節(jié)點(diǎn)0個，經(jīng)過1-choice節(jié)點(diǎn)im+jm個，最大跳數(shù)為

(7)

(8)

3 能耗模型

網(wǎng)絡(luò)運(yùn)行能耗由兩部分組成，包括取決于負(fù)載的傳輸能耗和取決于運(yùn)行時間的待機(jī)能耗[12,13]。

3.1 瓶頸節(jié)點(diǎn)傳輸能耗

文獻(xiàn)[14～16]給出了一個傳輸能耗模型，其中節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)至距離dm處的能耗為

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

(9)

節(jié)點(diǎn)接收kbit數(shù)據(jù)的能耗為

er(k)=k·ere.

(10)

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

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

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

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

(11)

3.2 待機(jī)能耗

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

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

(12)

4 數(shù)值分析

基于IEEE 802.15.4協(xié)議，取BW=250 kbit/s，Len=125 byte，依據(jù)式(12)取PON=40 mW，εa=100 pJ/bit，ete=ere=50 nJ/bit。在im=50，jm=30的方格拓?fù)渲校玫絧從0.8變化至1時的傳輸能耗、待機(jī)能耗和總能耗，如圖5～圖7所示。

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

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

圖6 各路由策略的最大待機(jī)能耗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轉(zhuǎn)發(fā)策略跟隨路徑有效概率p的變化比較明顯，Balance策略跟隨p有微小的變化，其它3種策略基本不隨p變化。在p較小時，Line策略的待機(jī)時延和能耗較大。

在總能耗方面,看出SZ策略最大，其次是REP策略，而Balance策略總能耗最低。隨路徑有效概率p增大，除Line策略外的各策略的總能耗值略微下降。瓶頸節(jié)點(diǎn)承擔(dān)很重的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，故其傳輸能耗略大于待機(jī)能耗。

5 結(jié)束語

本文分析了多種源路由策略的瓶頸節(jié)點(diǎn)負(fù)載和最大待機(jī)時延，設(shè)計(jì)了方格拓?fù)渲袀鬏數(shù)哪芎哪Ｐ?，?shù)值分析比較了各策略的傳輸能耗、待機(jī)能耗及總能耗，指出負(fù)載均衡轉(zhuǎn)發(fā)策略具有最小的總能耗、而直線轉(zhuǎn)發(fā)和隨機(jī)等概率轉(zhuǎn)發(fā)策略的能耗較大。

[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] 候忠偉.基于拓?fù)淇刂频臒o線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)負(fù)載均衡策略[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

國家自然科學(xué)基金資助項(xiàng)目(61174106)；湖北省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(Q20141110)；冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室(武漢科技大學(xué))開放基金資助項(xiàng)目(Y201322)；武漢科技大學(xué)大學(xué)生創(chuàng)新基金資助項(xiàng)目(12ZRC115)

TP 393

A

1000—9787(2014)10—0036—04

吳騰飛(1984-)，男，碩士研究生，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)。