劉靜娜，邵 清

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海200093)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)在軍事、工業(yè)、智能交通、空間探索等領(lǐng)域有著廣闊的應(yīng)用前景，被認為是全球未來四大高技術(shù)產(chǎn)業(yè)之一［1，2］。尤其非常適合無法快速搭建基礎(chǔ)設(shè)施的情況，如戰(zhàn)場上部隊快速展開和推進、自然災(zāi)害后的搜索和營救、臨時會議等［3，4］。WSNs節(jié)點由自帶電池供給電能，因此，節(jié)省能源是設(shè)計任何協(xié)議的前提條件［5～7］，加上通信環(huán)境非常惡劣，終端規(guī)格各異，網(wǎng)絡(luò)性能易受天氣和地形的影響，導(dǎo)致網(wǎng)絡(luò)中單向鏈路普遍存在，使得網(wǎng)絡(luò)的無線通信性能也會經(jīng)常變化，甚至通信有可能中斷。因此，如何設(shè)計可靠的通信機制以滿足網(wǎng)絡(luò)通信的節(jié)能可靠性需求是WSNs 所面臨的一個重要問題［8，9］。

目前很多機構(gòu)和學(xué)者致力于解決單向鏈路故障問題，Marina M K，Das S R 等人在按需距離矢量(Ad Hoc on－demand distance vector，AODV)協(xié)議［10］的基礎(chǔ)上，提出了剔除單向鏈路故障的路由協(xié)議——AODV－LSA(AODV link－stateaware)［11］，該協(xié)議通過鄰居節(jié)點間的信息交互來發(fā)現(xiàn)單向鏈路故障并重新尋路。但這種方法會報文數(shù)據(jù)巨大，導(dǎo)致資源的不必要開銷。Sari R F，Syarif A 等人［12］在AODV 協(xié)議基礎(chǔ)上，提出了檢測單向鏈路故障的路由協(xié)議AODV－UU，這是一種按需距離矢量路由協(xié)議對單向鏈路狀態(tài)更新的方法來標(biāo)記單向鏈路并避免使用，盡管它有高的交付率，但該方法降低網(wǎng)絡(luò)的連通性，若拓撲結(jié)構(gòu)變化快，該協(xié)議的效率非常低。

針對傳統(tǒng)算法存在的能耗瓶頸問題，本文提出了一種基于Hello 報文結(jié)合苯環(huán)網(wǎng)絡(luò)模型的故障檢測(ALFD－H)算法。該算法巧妙地利用苯環(huán)網(wǎng)絡(luò)模型來完成故障檢測，盡量避免節(jié)點重新尋路，避免了洪范性發(fā)送Hello 報文，從而減少網(wǎng)絡(luò)開銷和負載。

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

ALFD－H 算法的網(wǎng)絡(luò)模型是將WSNs 分成若干個苯環(huán)結(jié)構(gòu)，以苯環(huán)為單位進行故障檢測，苯環(huán)中心節(jié)點負責(zé)對苯環(huán)內(nèi)成員節(jié)點之間的單向鏈路進行檢測并與其它中心節(jié)點共享故障信息。該思想是受到化學(xué)中的苯環(huán)結(jié)構(gòu)的啟發(fā)［13］。化學(xué)中，在一個苯環(huán)結(jié)構(gòu)上面可以衍生出很多種物質(zhì)，苯環(huán)結(jié)構(gòu)同樣可以很好地應(yīng)用于網(wǎng)絡(luò)中，提高網(wǎng)絡(luò)的可擴展性。

苯環(huán)的化學(xué)結(jié)構(gòu)中，如圖1 所示，每個C 原子上都含有一個雙鍵，C 原子的另外兩個共價鍵分別鏈接另一個C 原子和H 原子，構(gòu)成了一個穩(wěn)定的化學(xué)結(jié)構(gòu)。針對ALFD－H的網(wǎng)絡(luò)模型，一個苯環(huán)結(jié)構(gòu)內(nèi)的各節(jié)點之間構(gòu)成一個鄰居網(wǎng)絡(luò)，同時節(jié)點也可與其他苯環(huán)進行通信，多個這樣的苯環(huán)結(jié)構(gòu)定能組成一個較大規(guī)模的網(wǎng)絡(luò)。根據(jù)苯環(huán)的特性，節(jié)點之間的通信應(yīng)置為兩條，一條為單向鏈路故障的心跳檢測通道;另一條通道是正常數(shù)據(jù)信道。本文通過對苯環(huán)結(jié)構(gòu)進行改進，實現(xiàn)苯環(huán)中心節(jié)點管理苯環(huán)子節(jié)點從而減少了鄰居節(jié)點的數(shù)目和廣播通信次數(shù)從而降低了通信能耗。苯環(huán)中間加一個特別節(jié)點，即中心節(jié)點，數(shù)據(jù)處理能力和通信能力較強。圖1 所示，C，H 分別表示不同的元素，可表示具有不同能力的節(jié)點。C 原子的四個共價鍵可如圖2 進行分配:心跳檢測、正常通信、鄰居節(jié)點、中心節(jié)點或者其他網(wǎng)絡(luò)中的節(jié)點，這樣就可以構(gòu)成較大的網(wǎng)絡(luò)規(guī)模，保證了網(wǎng)絡(luò)的可擴展性。

在這種網(wǎng)絡(luò)模型中單向鏈路故障可以概括為三方面的原因:1)如圖3 所示，當(dāng)節(jié)點A 和節(jié)點B 相互覆蓋對方時，此時兩個節(jié)點的連通狀態(tài)是雙向的，即A?B;當(dāng)節(jié)點A 或者是節(jié)點B 背向?qū)Ψ揭苿樱琩AB大于了節(jié)點B(A)的最大傳輸半徑dmax時，就成了單向鏈路A→B。2)如圖4 所示，節(jié)點B 隨著自身能量的消耗不能覆蓋節(jié)點A，節(jié)點A 仍能覆蓋節(jié)點B 時，節(jié)點A，B 之間的鏈路就成了單向鏈路。3)如圖5所示，外界環(huán)境的干擾導(dǎo)致節(jié)點A 仍然能夠覆蓋節(jié)點B，但節(jié)點B 卻不可以覆蓋節(jié)點A，產(chǎn)生單向鏈路故障。

圖1 苯環(huán)結(jié)構(gòu)Fig 1 Benzene ring structure

圖2 苯環(huán)網(wǎng)絡(luò)模型Fig 2 Network model of benzene ring

圖3 節(jié)點移動導(dǎo)致單向鏈路Fig 3 Unidirectional link caused by node moving

圖4 能量消耗引起單向鏈路Fig 4 Unidirectional link caused by energy consumption

圖5 環(huán)境干擾導(dǎo)致單向鏈路Fig 5 Unidirectional link caused by environmental interference

2 ALFD－H 算法

2.1 ALFD－H 算法檢測過程分析

ALFD－H 算法充分利用苯環(huán)區(qū)域自治的特點進行故障檢測。苯環(huán)中心節(jié)點周期性地廣播Hello 報文，該苯環(huán)的子節(jié)點接收到Hello 報文后會檢測與鄰居節(jié)點的鏈路是否故障，如果沒有收到反饋消息就認為鄰居節(jié)點與自己可能發(fā)生了單向鏈路故障，子節(jié)點就會把可能發(fā)生鏈路故障的消息發(fā)送到苯環(huán)中心節(jié)點。苯環(huán)中心節(jié)點接收到子節(jié)點發(fā)送來的故障消息，這說明兩個子節(jié)點之間的鏈路一定存在問題，要么是鏈路不存在了，要么是錯誤地判斷了鏈路之間的狀態(tài)，要么是存在單向鏈路(這里假設(shè)無線傳感器網(wǎng)絡(luò)節(jié)點是完好的)。這里假設(shè)故障鏈路的兩節(jié)點是A，B。苯環(huán)中心節(jié)點接收到故障消息后發(fā)送Hello 報文給A 并攜帶這樣一條路經(jīng)指示A→B→苯環(huán)中心節(jié)點，若苯環(huán)中心節(jié)點收到了來自B 發(fā)送的Hello 報文，則說明這條鏈路是單向鏈路，苯環(huán)中心節(jié)點將標(biāo)記該鏈路并在通信質(zhì)量要求不高時加以使用，若苯環(huán)中心節(jié)點收不到來自B 的Hello 報文，則以同樣的方式檢測BA 之間的鏈路，發(fā)送Hello 報文給B 并攜帶這樣一條路經(jīng)指示B→A→苯環(huán)中心節(jié)點，若苯環(huán)中心節(jié)點收到了來自A 發(fā)送的Hello 報文，則標(biāo)記該鏈路為單向鏈路并加以利用;若同樣沒有收到Hello 報文，則表示A，B 間已經(jīng)沒有了鏈路，此時苯環(huán)中心節(jié)點檢測A，B 兩節(jié)點與苯環(huán)中心節(jié)點的鏈路關(guān)系，若可以構(gòu)成通路，則建立連接繼續(xù)使用，避免重新尋路浪費資源;若不存在鏈路關(guān)系，則丟棄該節(jié)點并通知其他節(jié)點以便及時組合到新的苯環(huán)中去。

2.2 ALFD-H 檢測算法

定義 B:一個苯環(huán)結(jié)構(gòu);C［i］:苯環(huán)中心節(jié)點;S［i］:與苯環(huán)相連的子節(jié)點;S［j］:苯環(huán)子節(jié)點。

1)節(jié)點初始化

2)苯環(huán)故障檢測

3 ALFD－H 算法性能測試和分析

本文采用NS2 平臺作為仿真工具。為了構(gòu)造單向鏈路，對拓撲結(jié)構(gòu)中的節(jié)點的發(fā)射功率和接收門限做了調(diào)整。仿真實驗的拓撲結(jié)構(gòu)為1 000 m×1 000 m 范圍，節(jié)點覆蓋范圍50 ～150 m，由于ALFD－H 算法主要工作是在路由建立階段，故仿真時間設(shè)定較短，為30s。實驗中每種網(wǎng)絡(luò)規(guī)模均仿真60 次，然后求平均值。將該算法與傳統(tǒng)算法做對比分析，從單向鏈路通告成功率、控制報文數(shù)和能量損耗三個方面進行比較。

1)單向鏈路通告成功率

單向鏈路通告成功率是指單向鏈路故障被恢復(fù)為雙向鏈路的數(shù)目占全部被發(fā)現(xiàn)的單向鏈路數(shù)目的比例。在AODV 協(xié)議中，單向鏈路節(jié)點的修復(fù)是靠各方面能力都比較強的源節(jié)點實現(xiàn)的，故而單向鏈路通告成功率會較高;在ALFD－H 算法中，單向鏈路的修復(fù)是靠苯環(huán)中心節(jié)點實現(xiàn)的，苯環(huán)中心節(jié)點配置需求就是通信能力和處理能力較強故而單向鏈路通告成功率次之;在AODV－UU 中不涉及到Hello 報文，故單向鏈路通告成功率較低。如圖6 所示，該圖表明各種算法的單向鏈路通告成功率隨網(wǎng)絡(luò)節(jié)點變化情況。

2)控制報文數(shù)

控制報文數(shù)指的是節(jié)點鏈路狀態(tài)通告報文和路由建立的消息報文的總數(shù)。AODV－UU 算法的控制報文數(shù)相對較少，主要是采用泛洪來解決單向鏈路;ALFD－H 算法在鏈路通告期間對控制報文的TTL 做了限制(TTL 最大為3)。而傳統(tǒng)的AODV 中的Hello 報文數(shù)目相對較多。圖7 顯示了各個算法在不同網(wǎng)絡(luò)節(jié)點的情況下，控制報文的數(shù)量的變化。

圖6 單向鏈路通告成功率Fig 6 Notice success rate of unidirectional links

圖7 報文控制數(shù)Fig 7 Number of packets control

3)能量消耗

AODV 鄰居單向鏈路檢測通過向鄰居廣播消息來查詢是否存在單向鏈路，廣播消息耗費能量較大;而ALFD－H 算法中是通過一組鄰居節(jié)點和中心節(jié)點協(xié)作完成的，故消耗的能量較小;在AODV－UU 中，沒有涉及到Hello 報文的廣播故而能量消耗是這三種算法中最少的。圖8 表明了各個算法隨著時間的延長，各自能量剩余的百分比變化情況。

圖8 能量消耗隨時間的變化Fig 8 Energy consumption vs time change

仿真結(jié)果表明:本文提出的ALFD－H 算法極大程度地降低了通信過程電能和資源的消耗。

4 結(jié)束語

本文基于苯環(huán)的對稱結(jié)構(gòu)與Hello 報文檢測機制，設(shè)計出了一種ALFD－H 算法。該算法具有能耗小、可擴展性高等優(yōu)點，能夠有效地在WSNs 中檢測單向鏈路。當(dāng)有單向鏈路存在時，ALFD－H 算法能夠盡量避免節(jié)點重新尋路，從而降低能量消耗，并提高了單向鏈路通告成功率。下一步的重點傾向于該實際應(yīng)用是否仍具有較低的能耗和探測準確度，在實現(xiàn)故障有效檢測的基礎(chǔ)上，對于單向鏈路利用的研究也是需要進一步考慮的。

［1］ Valera A，Tan H P.Analysis of Hello－based link failure detection in wireless Ad Hoc networks［C］∥2012 IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications(PIMRC)，IEEE，2012:669－674.

［2］ Jun T，Roy N，Julien C.Modeling delivery delay for flooding in mobile Ad Hoc networks［C］∥2010 IEEE International Conference on Communications(ICC)，2010.

［3］ Yamada K，Umebayashi K，Kamiya Y，et al.A study on routing protocol suitable for directional links［C］∥2010 IEEE Radio and Wireless Symposium(RWS)，IEEE，2010:328－331.

［4］ 龍昭華，陳丹丹，蔣貴全.無線傳感器網(wǎng)絡(luò)分簇拓撲控制算法［J］.傳感器與微系統(tǒng)，2014，33(3):143－145.

［5］ Tang Y，Li X，Yang M.Improvement of multicast routing supporting mobile Ad Hoc networks with unidirectional links［C］∥2011 6th International Conference on Pervasive Computing and Applications(ICPCA)，IEEE，2011:502－508.

［6］ Su Bo，Pei Changxing，Tang Jun.Improved capacity scaling of wireless Ad Hoc networks［J］.China Communications，2010，7(5):183－188.

［7］ Cambruzzi E，F(xiàn)arines J，Macedo R J，et al.An adaptive failure detection system for vehicular Ad Hoc networks［C］∥2010 IEEE Intelligent Vehicles(IV)Symposium，IEEE，2010:603－608.

［8］ Zuhairi M，Zafar H，Harle D.On－demand routing with unidirectional link using path loss estimation technique［C］∥2012 Wireless Telecommunications Symposium(WTS)，IEEE，2012:1－7.

［9］ Chaturvedi A，Tiwari D，Bhadoria R S，et al.Route discovery protocol for optimizing the power consumption in wireless Ad Hoc network［C］∥2013 International Conference on Communication Systems and Network Technologies(CSNT)，IEEE，2013:290－294.

［10］Ayash M，Mikki M，Yim K.Improved AODV routing protocol to cope with high overhead in high mobility MANETs［C］∥2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing(IMIS)，IEEE，2012:244－251.

［11］Yu X H，Ouyang Y U.A link－state－aware Ad Hoc on－demand distance vector(AODV)routing protocol for mobile Ad Hoc networks［C］∥2006 International Conference on Communication Technology，ICCT’06，IEEE，2006:1－4.

［12］Sari R F，Syarif A，Ramli K，et al.Performance evaluation AODV routing protocol on Ad Hoc hybrid network testbed using PDAs［C］∥2005 13th IEEE International Conference on Networks，2005 Jointly held with the 2005 IEEE 7th Malaysia International Conference on Communication:256－261.

［13］馬甲林，邵 清.一種基于苯環(huán)結(jié)構(gòu)的WSNs 故障檢測算法［J］.傳感器與微系統(tǒng)，2013，32(11):125－127.