基于苯環(huán)結(jié)構(gòu)的WSNs 單向鏈路故障檢測算法*

劉靜娜，邵 清

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

0 引 言

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

目前很多機(jī)構(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é)點(diǎn)間的信息交互來發(fā)現(xiàn)單向鏈路故障并重新尋路。但這種方法會(huì)報(bào)文數(shù)據(jù)巨大，導(dǎo)致資源的不必要開銷。Sari R F，Syarif A 等人［12］在AODV 協(xié)議基礎(chǔ)上，提出了檢測單向鏈路故障的路由協(xié)議AODV－UU，這是一種按需距離矢量路由協(xié)議對(duì)單向鏈路狀態(tài)更新的方法來標(biāo)記單向鏈路并避免使用，盡管它有高的交付率，但該方法降低網(wǎng)絡(luò)的連通性，若拓?fù)浣Y(jié)構(gòu)變化快，該協(xié)議的效率非常低。

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

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

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

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

在這種網(wǎng)絡(luò)模型中單向鏈路故障可以概括為三方面的原因:1)如圖3 所示，當(dāng)節(jié)點(diǎn)A 和節(jié)點(diǎn)B 相互覆蓋對(duì)方時(shí)，此時(shí)兩個(gè)節(jié)點(diǎn)的連通狀態(tài)是雙向的，即A?B;當(dāng)節(jié)點(diǎn)A 或者是節(jié)點(diǎn)B 背向?qū)Ψ揭苿?dòng)，dAB大于了節(jié)點(diǎn)B(A)的最大傳輸半徑dmax時(shí)，就成了單向鏈路A→B。2)如圖4 所示，節(jié)點(diǎn)B 隨著自身能量的消耗不能覆蓋節(jié)點(diǎn)A，節(jié)點(diǎn)A 仍能覆蓋節(jié)點(diǎn)B 時(shí)，節(jié)點(diǎn)A，B 之間的鏈路就成了單向鏈路。3)如圖5所示，外界環(huán)境的干擾導(dǎo)致節(jié)點(diǎn)A 仍然能夠覆蓋節(jié)點(diǎn)B，但節(jié)點(diǎn)B 卻不可以覆蓋節(jié)點(diǎn)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é)點(diǎn)移動(dòng)導(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ū)域自治的特點(diǎn)進(jìn)行故障檢測。苯環(huán)中心節(jié)點(diǎn)周期性地廣播Hello 報(bào)文，該苯環(huán)的子節(jié)點(diǎn)接收到Hello 報(bào)文后會(huì)檢測與鄰居節(jié)點(diǎn)的鏈路是否故障，如果沒有收到反饋消息就認(rèn)為鄰居節(jié)點(diǎn)與自己可能發(fā)生了單向鏈路故障，子節(jié)點(diǎn)就會(huì)把可能發(fā)生鏈路故障的消息發(fā)送到苯環(huán)中心節(jié)點(diǎn)。苯環(huán)中心節(jié)點(diǎn)接收到子節(jié)點(diǎn)發(fā)送來的故障消息，這說明兩個(gè)子節(jié)點(diǎn)之間的鏈路一定存在問題，要么是鏈路不存在了，要么是錯(cuò)誤地判斷了鏈路之間的狀態(tài)，要么是存在單向鏈路(這里假設(shè)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)是完好的)。這里假設(shè)故障鏈路的兩節(jié)點(diǎn)是A，B。苯環(huán)中心節(jié)點(diǎn)接收到故障消息后發(fā)送Hello 報(bào)文給A 并攜帶這樣一條路經(jīng)指示A→B→苯環(huán)中心節(jié)點(diǎn)，若苯環(huán)中心節(jié)點(diǎn)收到了來自B 發(fā)送的Hello 報(bào)文，則說明這條鏈路是單向鏈路，苯環(huán)中心節(jié)點(diǎn)將標(biāo)記該鏈路并在通信質(zhì)量要求不高時(shí)加以使用，若苯環(huán)中心節(jié)點(diǎn)收不到來自B 的Hello 報(bào)文，則以同樣的方式檢測BA 之間的鏈路，發(fā)送Hello 報(bào)文給B 并攜帶這樣一條路經(jīng)指示B→A→苯環(huán)中心節(jié)點(diǎn)，若苯環(huán)中心節(jié)點(diǎn)收到了來自A 發(fā)送的Hello 報(bào)文，則標(biāo)記該鏈路為單向鏈路并加以利用;若同樣沒有收到Hello 報(bào)文，則表示A，B 間已經(jīng)沒有了鏈路，此時(shí)苯環(huán)中心節(jié)點(diǎn)檢測A，B 兩節(jié)點(diǎn)與苯環(huán)中心節(jié)點(diǎn)的鏈路關(guān)系，若可以構(gòu)成通路，則建立連接繼續(xù)使用，避免重新尋路浪費(fèi)資源;若不存在鏈路關(guān)系，則丟棄該節(jié)點(diǎn)并通知其他節(jié)點(diǎn)以便及時(shí)組合到新的苯環(huán)中去。

2.2 ALFD-H 檢測算法

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

1)節(jié)點(diǎn)初始化

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

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

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

1)單向鏈路通告成功率

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

2)控制報(bào)文數(shù)

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

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

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

3)能量消耗

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

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

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

4 結(jié)束語

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

［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ò)分簇拓?fù)淇刂扑惴ǎ跩］.傳感器與微系統(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.