基于苯環結構的WSNs 單向鏈路故障檢測算法*

劉靜娜，邵 清

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

0 引 言

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

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

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

1 網絡模型

ALFD－H 算法的網絡模型是將WSNs 分成若干個苯環結構，以苯環為單位進行故障檢測，苯環中心節點負責對苯環內成員節點之間的單向鏈路進行檢測并與其它中心節點共享故障信息。該思想是受到化學中的苯環結構的啟發［13］。化學中，在一個苯環結構上面可以衍生出很多種物質，苯環結構同樣可以很好地應用于網絡中，提高網絡的可擴展性。

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

在這種網絡模型中單向鏈路故障可以概括為三方面的原因:1)如圖3 所示，當節點A 和節點B 相互覆蓋對方時，此時兩個節點的連通狀態是雙向的，即A?B;當節點A 或者是節點B 背向對方移動，dAB大于了節點B(A)的最大傳輸半徑dmax時，就成了單向鏈路A→B。2)如圖4 所示，節點B 隨著自身能量的消耗不能覆蓋節點A，節點A 仍能覆蓋節點B 時，節點A，B 之間的鏈路就成了單向鏈路。3)如圖5所示，外界環境的干擾導致節點A 仍然能夠覆蓋節點B，但節點B 卻不可以覆蓋節點A，產生單向鏈路故障。

圖1 苯環結構Fig 1 Benzene ring structure

圖2 苯環網絡模型Fig 2 Network model of benzene ring

圖3 節點移動導致單向鏈路Fig 3 Unidirectional link caused by node moving

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

圖5 環境干擾導致單向鏈路Fig 5 Unidirectional link caused by environmental interference

2 ALFD－H 算法

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

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

2.2 ALFD-H 檢測算法

定義 B:一個苯環結構;C［i］:苯環中心節點;S［i］:與苯環相連的子節點;S［j］:苯環子節點。

1)節點初始化

2)苯環故障檢測

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

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

1)單向鏈路通告成功率

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

2)控制報文數

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

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

圖7 報文控制數Fig 7 Number of packets control

3)能量消耗

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

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

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

4 結束語

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

［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］ 龍昭華，陳丹丹，蔣貴全.無線傳感器網絡分簇拓撲控制算法［J］.傳感器與微系統，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，Farines 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］馬甲林，邵 清.一種基于苯環結構的WSNs 故障檢測算法［J］.傳感器與微系統，2013，32(11):125－127.