用于水聲傳感器網絡自組織的詢問式泛洪廣播算法?

肖東魏麗萍　陳庚　陳巖　馬力

（中國科學院水聲環境特性重點實驗室　北京　100190）

用于水聲傳感器網絡自組織的詢問式泛洪廣播算法?

肖東?魏麗萍陳庚陳巖馬力

（中國科學院水聲環境特性重點實驗室北京100190）

水聲傳感器網絡（Underwater acoustic sensor networks，UASN）通常由隨機散布的傳感器節點組成。需要通過自組織算法將這些節點組成具有一定功能的網絡。目前，已有較多成熟的用于陸地無線傳感器網絡（Wireless sensor networks，WSN）的自組織算法。但水聲通信中存在的嚴重的傳播損失、較高的背景噪聲、有限的通信帶寬、較長的傳播時延、復雜的多途信道等，使得大多數適用于WSN的自組織算法難以適用于UASN。本文提出了一種改進的自組織算法，在簡單泛洪廣播算法中附加一段詢問過程。通過OPNET仿真證明了在相同的條件下，相比于簡單泛洪與概率泛洪廣播算法，本算法可以在較短的時間內建立起有效路由，降低了水聲網絡在自組織階段的能量消耗。

水聲傳感器網絡，自組織算法，泛洪廣播

1　引言

UASN用途廣泛，例如：海洋環境及水文數據收集、水下災害多發區域監視和分布式水下預警等。1993年，由美國（Office of naval research，ONR）資助的（Autonomous ocean sampling networks，AOSNs）項目最早提出了水聲網絡應用的概念［1］。二十年來，國際上比較著名水聲網絡研究計劃有：美國的Seaweb海網計劃、沿海大陸架觀測計劃（The front-resolving observational network with telemetry，FRONT）沿海大陸架觀測計劃，歐共體的（Marine science and technology program，MAST）計劃等［1-3］。

組成水聲網絡的潛/浮標節點由船只或飛機隨機布放在感興趣的水域中，需要通過自組織算法才能構成具有一定功能的水聲網絡，可以說自組織算法是無線網絡的基石。目前，用于WSN的自組織算法的大體思路有以下兩種：（1）在各節點布放之后存在一個路由發現階段，在該階段每個節點按照一定規則形成自己的路由表，按照路由表發送數據包，并根據實際情況對路由表進行定期或者不定期的更新；（2）在各節點布放之后，每個節點不形成自己的路由表，只在有數據包需要發送的時候，根據用戶需要、網絡狀態以及節點分布情況尋找路由進行發送。考慮到工程實現時各方面因素的限制，UASN尚不適宜組建大規模層次化網絡，也暫時難以使用第2種思路進行網絡自組織。

全網范圍內的泛洪廣播算法是在設計平面化自組織網絡時常用的策略，但是直接泛洪廣播容易造成數據重復廣播，引發廣播風暴，造成信道擁塞［4］。針對泛洪廣播算法的改進算法也有很多，大致分為四類［5］：（1）簡單或盲泛洪（Simple or blind flooding）；（2）概率或聊天式泛洪（Probabilistic or gossip flooding）［6］；（3）地域式泛洪（Area based flooding）［7］；（4）鄰居知識式泛洪（Neighbor knowledge flooding）［8］。上述算法一般適用于移動性較強的無線傳感器網絡。其中，地域式泛洪通常需要每個節點可以較精確的獲得自身的地理位置信息，鄰居知識式泛洪一般需要本地拓撲結構及重復消息的統計信息［8］。而UASN的潛/浮標節點在布放后難以調整參數、幾乎沒有移動性，且潛標節點需要一定的輔助設施來獲得自身較精確的地理位置。因此，將地域式泛洪或鄰居知識式泛洪算法在UASN中工程實現，尚有難度。

本文將簡單泛洪及概率泛洪兩種算法移植到UASN中，經OPNET軟件仿真發現：大多數情況下，部分節點難以在一定時間內形成完整的路由表，增加泛洪廣播輪數對路由表形成的幫助有限。為改善上述情況，本文提出了一種詢問式泛洪廣播算法（下文簡稱為本算法），即在一輪泛洪廣播之后增加了鄰居詢問及路由更新過程。以簡單泛洪及概率泛洪算法為參考，在幾種典型的拓撲結構下針對本算法進行了OPNET軟件仿真。仿真中所有節點都在給定的時間內形成了完整的路由表，且節省了節點能量消耗。

2　算法設計

網絡路由一般分為三種方式：先驗式、反應式和混合式。水聲傳感器網絡以水聲通信作為物理層，資源極其有限。而反應式網絡路由，即引言中的第2種思路，通常占用資源較多，不適用于水聲傳感器網絡。隨機布放的潛標節點雖然基本不會移動，但是也不可能存在先驗性的路由表。所以，目前認為混合式路由比較適宜水聲網絡。即引言中的第1種思路，在潛標布放之后存在一個路由組織建立的階段，在該階段每一個節點建立自身路由表，并在之后的信息傳輸階段對該路由表進行維護。本文提出的詢問式泛洪廣播算法適用于路由組織建立階段。本算法在一輪簡單泛洪廣播之后增加了詢問過程，并根據算法需要設計了相應的幀格式與路由表結構。

2.1自組織流程

本算法的自組織流程如圖1所示。每個節點在初始化階段隨機地設置一個廣播時間，在初始狀態中等待該廣播中斷。在廣播中斷時發起一次泛洪廣播。廣播之后進入空閑狀態，該狀態下只通過詢問鄰居的方式對路由表進行更新。因此，采用本算法時整個網絡只存在一輪泛洪廣播。本算法認為水聲通信信道具有互易性，在收到所有正確的數據幀時，都會根據幀信息更新路由表。在鏈路層協議中，可以采用隨機退避重發的機制。多次重發失敗后，認為到達目的節點的鏈路斷開，清空路由表中對應項。將該數據幀留存到回收站，等待鏈路暢通后，再重新發送。

HXD3C型機車在濟南機務段實際應用過程中發現EBV故障主要表現為:085故障、限制開關打開、單閘側緩失效、列車管自動減壓及制動手柄失效等現象。

圖1　自組織算法流程圖Fig.1 Flow chart of self-organization algorithm

其中，路由完整的判定準則為本節點可以通過網絡路由訪問所有其他節點。詢問鄰居時，本節點向一跳以內的所有鄰居節點廣播一個詢問幀。每個詢問幀可以詢問一個其他節點的路由。接收到該詢問幀的鄰居節點在知情且空閑的情況下，發送一個回復幀給本節點。本節點收到回復幀之后，更新自身路由表。

2.2數據處理流程

圖1的處理數據流程中，需要針對不同數據進行不同方式的處理，具體處理方式參見接收端流程圖，見圖2。接收端首先對數據幀進行校驗，校驗正確的情況下，按照圖2進行數據處理。如果校驗出錯，則將該幀丟棄，不作任何處理。

圖2　數據處理流程圖Fig.2 Flow chart of data processing

2.3幀格式及其他

本算法所用的幀格式如圖3所示。幀同步為水聲通信物理層的時頻同步頭。幀信息包含了自組織算法所需要的所有信息。數據類型中應標明本幀為泛洪廣播幀、路由詢問幀還是路由回復幀。設置幀序號是為了區別同一節點先后發出的不同數據幀，以免錯漏以及重復。

另外，每個節點需要維護一個自己的路由表，路由表包含三項信息：（1）目的節點是否能夠訪問；（2）到達該目的節點需要經過的下跳節點地址；（3）到達該目的節點需要經過的跳數。

圖3　幀格式Fig.3 Frame format

3　軟件仿真及結果分析

利用OPNET軟件，對水聲通信進行建模，并設計了半雙工方式的實現方法。針對幾種典型的拓撲結構，利用本算法進行軟件仿真，并以簡單泛洪廣播算法作為參考，對仿真結果進行了分析。

3.1水聲通信建模

OPNET中，將無線鏈路分為14個管道模型階段進行建模。需要在節點模型中設定發射機與接收機的中心頻率、帶寬、調制方式、傳輸速率、糾錯編碼。對于無線鏈路，OPNET中默認方式是全雙工，而目前大多數水聲通信只能采用半雙工方式［9-10］。

3.1.1管道模型階段

仿真中，以實驗室現有水聲Modem的參數作為參考，將水聲通信參數設置為：BPSK調制、半雙工方式、中心頻率6 kHz、帶寬4 kHz、通信速率1 kbps、有效距離約5 km。具體到水聲通信中，還需要注意的管道模型階段有如下幾點。

（1）第6階段傳播時延中，水下聲波傳播速度為1500 m/s，與OPNET中默認電磁波傳播速度不同，需要修改。

（2）第8階段接收功率中，需要根據水聲傳播衰減模型重新編寫代碼計算接收功率。本算法的仿真中采用了經典的Marsh-Schulkin模型［11］。

（3）實際水聲通信中，一旦多個接收信號之間發生碰撞，這些接收信號都無法正確接收。因此在第9階段的噪聲串擾中，應放大信號間噪聲串擾的影響。

（4）第10階段背景噪聲中，應計算海洋背景噪聲級，仿真中采用經典的經驗公式［12］將其分為四類進行計算。

（5）通過調整發射功率等參數，使得第11階段信噪比中，在沒有碰撞時的誤碼率在10-3左右，而發生碰撞時誤碼率在10-1量級，比較符合水聲通信的情況。

3.1.2半雙工設計

前已敘及，OPNET中使用的無線鏈路均為全雙工通信方式，不論同一節點的發射機與接收機是否設置為相同中心頻率以及帶寬。因此，需要自行設定半雙工通信方式。

OPNET仿真中設計的節點模型如圖4所示。圖中Source為數據來源，可以視為傳感器。Router為自組網算法模塊。Transmitter為發射換能器。Receiver為接收水聽器。實線表示數據幀流向。虛線為統計中斷線，一根為接收信號上升沿觸發中斷，標志接收信號起始，另一根為接收信號下降沿觸發中斷，標志接收信號結束。當發射換能器處于發射狀態時，忽略接收信號的上升沿及下降沿觸發中斷，并丟棄所有接收到的數據幀。反之，設置水聽器接收狀態標志，將待發射信號延遲到下降沿觸發中斷之后再發送。

圖4　節點模型Fig.4 Node model

需要補充的是：在無誤碼的情況下，數據幀成功接收時的流中斷（由Receiver指向Router的數據幀流向線產生）與接收信號下降沿中斷是同時產生的，取其一即可。但在因為誤碼而丟棄數據幀的情況下，不會產生流中斷，但還是會產生下降沿中斷。因此必須使用兩條統計中斷線來設置和清空接收水聽器的接收狀態標志位。

3.2仿真結果分析

對幾種拓撲結構分別進行了仿真，拓撲結構圖依次如圖5所示。以簡單泛洪廣播算法及概率泛洪廣播算法作為參考，考察了幾種拓撲結構下本算法的網絡自組織時間及能量消耗情況。對于概率泛洪算法，若其泛洪概率設置接近于1，則與簡單泛洪差別不大；反之，泛洪概率設置接近于0時，相當于水聲通信鏈路可靠性極低，網絡自組織難以正常進行。因此，將其泛洪概率設置為0.5，即當一個節點接收到來自其他節點的新的泛洪廣播數據時，50%的情況下會將該數據繼續泛洪廣播下去。另外，仿真中網絡自組織完畢的標志為建立起有效的水聲網絡，即所有節點都可以通過網絡路由訪問到其他任何節點，暫且不論是否為最佳路由路徑。因為不同的衡量標準下會產生不同的最佳路由標準。

圖5　仿真所采用的拓撲結構Fig.5 Topologies in the simulation

仿真結果如表1所示。表中4種拓撲結構依次與圖5中的4幅子圖一一對應。圖5（a）星型拓撲結構以一個節點作為中心節點，其他節點分布在其周圍，且通信范圍內僅存在中心節點；圖5（b）環型拓撲結構，每一個節點的通信范圍內都只存在兩個其他節點；圖5（c）蜂窩式拓撲結構可以實現對布放海域的最佳覆蓋；圖5（d）分布式拓撲結構是隨機布放的一個示例。

仿真中假設所有節點布放完畢后再開始自組織。設定網絡自組織的時間界限為1800 s，即1800 s以后放棄自組織。表中廣播次數與詢問次數的計算方法為每當有一個節點發起泛洪廣播或者詢問時，便計算一次。

由表1可見，幾種拓撲結構下，簡單泛洪及概率泛洪廣播算法均未能夠在1800 s內建立起有效網絡。而本算法最長的自組織時間未超過1000 s。

首節點建立時刻、次節點建立時刻分別是指整個網絡中有一個節點或兩個節點建立起自身完整路由表的時刻。幾種拓撲結構下，本算法與簡單泛洪算法的首個節點的完成時刻相同，且均在300 s之內。不難推斷，這兩種算法中，首個節點均是在第一輪泛洪廣播階段建立起自身路由表的。而對于概率泛洪算法，由于其泛洪廣播存在一定的概率性，首節點建立時刻稍晚于另外兩種算法。

表1　仿真結果比較表Table 1 Simulation results comparison

從次節點建立時刻分析可見，簡單泛洪算法的網絡自組織效率較低，同時結合其完成情況來看，簡單泛洪算法在后續的多輪泛洪廣播中能夠建立起完整路由的節點數量也極少。說明簡單泛洪算法僅在一輪泛洪廣播內比較有效，多輪泛洪廣播對建立有效路由的幫助不大。而概率泛洪算法可以在一定程度上避免沖突，網絡自組織效率稍高于簡單泛洪算法。但是，與本算法相比，仍略遜一籌。

與陸地無線傳感器節點不同的是：分布式水聲網絡節點的能量主要消耗在換能器發射聲信號上，接收信號與信號處理的能量消耗相對較小甚至可以忽略。所以信號發射次數基本上就可以反映水聲網絡整體的能量消耗情況。以圖5（a）中5節點星型拓撲結構為例，參考實驗室現有水聲Modem的參數，其中信號發射電功率10 W，接收及待機電功率0.05 W，對水聲網絡單個節點的平均能量消耗進行了仿真。仿真結果如圖6所示。

圖6　三種算法的能量消耗比較Fig.6 Comparison of used energy

圖6中，橫軸為時間，縱軸為單位時間內消耗電能量的焦耳數。點線為本算法的能量消耗，虛線和實線則分別對應概率泛洪算法和簡單泛洪算法的能量消耗。通過比較容易發現，相比于簡單泛洪和概率泛洪，本算法有效降低了網絡自組織過程中的能量消耗。

4　結論

本文提出了一種適用于小規模水聲傳感器自組織網絡的詢問式泛洪廣播算法。本算法在一輪簡單泛洪廣播算法之后增加了針對路由表空缺項詢問鄰居的流程。通過OPNET仿真證明了本算法可以在相對較短的時間內，建立起有效路由。且相比于簡單泛洪廣播算法，降低了水聲網絡的在自組織階段的能量消耗。

［1］吳松偉.水聲自組網節能路由協議研究［D］.哈爾濱：哈爾濱工程大學碩士學位論文，2010.

［2］鄧婕.淺海水聲自組網MAC協議的設計與實現［D］.廈門：廈門大學碩士學位論文，2009.

［3］李立.多水下自治機器人水聲自組網的研究［D］.青島：中國海洋大學碩士學位論文，2006.

［4］施韋，李善平，楊朝暉.移動自組織網絡中一種基于多點中繼策略的優化泛洪廣播算法［J］.計算機研究與發展，2007，44（6）：924-931. SHI Wei，LI Shanping，YANG Zhaohui.An optimized floodingalgorithmbasedonmultipointrelayingfor mobile ad hoc networks［J］.Journal of Computer Research and Development，2007，44（6）：924-931.

［5］REINA D G，TORAL S L，JONHSON P，et al.Hybrid flooding scheme for mobile ad hoc networks［J］.IEEE communication letters，2013，17（3）：592-595.

［6］HAAS Z J，HALPERN J Y，LI L.Gossip-based ad hoc routing［J］.IEEE/ACM Trans.Networking.2006，14（3）：479-491.

［7］PARK S，LEE E，PAKR H，et al.Mobile geocasting to support mobile sink groups in wireless sensor networks［L］. IEEE Commun.Lett.，2010，14（10）：939-941.

［8］PENGW，LUX.Onthereductionofbroadcast redundancy in mobile ad hoc networks［C］.First Annual Workshop on Mobile and Ad hoc Networking and Computing，2000：129-130.

［9］馮菲，高翔，李霞.水聲通信網MAC層協議仿真與分析［J］.聲學與電子工程，2007，（1）：26-30. FENG Fei，GAO Xiang，LI Xia.Simulation and analysis of MAC protocol in underwater acoustic communication networks［J］.Acoustics and electronics engineering，2007，（1）：26-30.

［10］林碧蘭，程恩，袁飛.基于OPNET的水聲通信網MAC層協議的研究［J］.電子設計工程，2010，2（18）：1-3. LIN Bilan，CHENG En，YUAN Fei.Research of the MAC protocol for underwater acoustic communication networks based on OPNET［J］.Electronic Design Engneering，2010，2（18）：1-3.

［11］SCHULKIN M，MARSH H W.Absorption of sound in sea-water［J］.Journal of the Acoustical Society of America，1977，62（3）：558-564.

［12］COATES R F W.Underwater acoustic systems［M］. London：Macmillan Education LTD，1990.

Inquiring flooding broadcast algorithm for underwater acoustic sensor self-organization networks?

XIAO Dong?WEI LipingCHEN GengCHEN YanMA Li
（Key Laboratory of Underwater Acoustic Environment，Institute of Acoustics，Chinese Academy of Sciences，Beijing 100190，China）

Usually,underwater acoustic sensor networks（UASN）is constructed by randomly deployed sensor nodes.In order to construct network of certain functions with these nodes,self-organization algorithm is needed.There are many self-organization algorithms for wireless sensor networks（WSN）onshore.But in underwater acoustic communication,the phenomena,such as：severe attenuation,high background noise, limited bandwidth,long time delay,complicated multi-path,etc.,most self-organized algorithms for WSN are hard to apply to UASN.An improved self-organization algorithm is proposed,which appends an inquiry process to flooding self-organization algorithm.It is proved by OPNET simulation that under the same conditions the network could be successfully established by the improved self-organization algorithm in a shorter time compared with simple flooding and probabilistic flooding algorithms,and the energy consumed in organization period is decreased.

Underwater acoustic sensor networks,Self-organization algorithm,Flooding broadcast

TN929.3

A

1000-310X（2015）01-0058-07

10.11684/j.issn.1000-310X.2015.01.009

2014-02-12收稿；2014-04-19定稿

?國家自然科學基金項目（61302109）

肖東（1984-），男，安徽蚌埠人，博士研究生，研究方向：信號與信息處理。

E-mail：xiaodong@mail.ioa.ac.cn