基于類二叉樹的圓錐型UWSNs的研究*

陳 軍, 張長江

(1.浙江師范大學 數理與信息工程學院，浙江 金華 321004;2.浙江工業職業技術學院 設計與藝術學院，浙江 紹興 312000)

?

基于類二叉樹的圓錐型UWSNs的研究*

陳 軍1,2, 張長江1

(1.浙江師范大學 數理與信息工程學院，浙江 金華 321004;2.浙江工業職業技術學院 設計與藝術學院，浙江 紹興 312000)

針對水下無線傳感器網絡(UWSNs)能量損耗嚴重，節點分布不均勻無規律等現象，提出以各個水面浮標節點為頂點，構建一種圓錐型UWSNs信息網(傳感器節點能根據能量大小而移動)，并將其活躍節點與備選節點抽象成類二叉樹結構，簡化了拓撲控制與路由傳遞。傳感器節點采集信息后，能通過活躍節點沿著類二叉樹的右節點傳遞到浮標節點。通過Matlab實現了算法的性能仿真測試，探討了同樣水深的層數為4,6,8的類二叉樹數據包傳遞率，結果顯示:層數越多，傳遞率越高；將6層類二叉樹的圓錐型UWSNs算法和深層路由(DBR)算法進行比較，結果顯示，該算法數據包傳遞率高，能耗低。

水下無線傳感器網絡； 二叉樹結構； 活躍節點； 浮標節點

0 引 言

水下無線傳感器網絡[1](underwater wireless sensor networks,UWSNs)通常用來對水體環境監測、水下目標探測等應用，將收集的數據做處理，以聲波傳輸的方式傳送到匯水上浮標節點。UWSNs是由具有聲學通信與計算能力的傳感器節點構成的水下監測網絡系統，隨著無線傳感器技術的發展，當前UWSNs的研究已經引起了學術界的高度重視,針對UWSNs的系統結構水下定位水聲通信等研究領域已經開展了大量基礎研究，并取得了一定的成果。其對于保護水資源、開發利用海洋資源等提供有力的保障，因此,UWSNs的研究越來越熱，尤其UWSNs的拓撲控制[2](拓撲構建、維護更新等)和路由協議成為其中一個重要的研究方向[3～5]。

針對UWSNs能量損耗嚴重，節點分布不均勻無規律等現象[6,7]，本文提出利用水面浮標節點為頂點，構建一個圓錐型UWSNs，并按照節點能量為衡量標準，設置節點的沉浮，協調節點之間的遠近距離，形成各扇形區域，所有活躍節點、備選節點形成一個類二叉樹結構的拓撲控制和路由(所謂類二叉樹是指該樹第一層有3個子樹，其余節點均為二叉樹，為了表述方便簡稱之)。通過仿真模擬測試[8]，比較不同總層數的效果，并比較了總層數為6的算法與深層路由(depth-based routing,DBR)算法[9]，取得一定的效果。

1 圓錐型UWSNs

三維UWSNs定位系統一般如圖 1所示，由衛星、基站、測量船、水上浮標、UWSNs節點組成一個特殊的無線傳感器網絡。懸浮在水中的傳感器節點分布在不同深度，用于監測不同深度的數據信息，通過UWSNs的路由將信息傳遞到水上浮標網絡，然后在以無線電通信方式將信息發送至地面基站或者水面測量船，解算完畢后由衛星信號發送至用戶手中完成測量。本文的水中無線傳感器節點，以能量大小作為沉浮的標準，能量越大分布的越深;反之,則越淺，如果能量不足，漂浮水面退出UWSNs。

圖1 三維UWSNs定位系統

1.1 圓錐形UWSNs模型

文中提出基于圓錐型UWSNs的有效傳感器節點部署和路由算法。在整個過程中，水上浮標與地面基站及測量船構成一個UWSNs，而UWSNs以每一個浮標為基準構成一個圓錐型通信網絡。現任取一個浮標S，以其為中心，把該節點對應的UWSNs模型抽象成一個圓錐模型，如圖 2所示。S為水上浮標節點，A,B,C為第一層活躍的傳感器節點，A＇，B＇，C＇為第二層活躍的傳感器節點，依次類推……。為了表述方便，將其俯視成二維平面圖如圖 3所示。其中涉及的概念簡述如下：

活躍節點：指在扇形區域中能量最大的一個，用于收集該區域的其他傳感器節點的數據。以A＇為例，定時活動于所在扇形區域的中心線上，用于收集該扇形區域所有傳感器節點的數據，并處理轉發給上級節點。

睡眠節點：是指該節點的核心處理模塊處于睡眠狀態，只開啟信號采集模塊，采集附近水域信息，并按照能量大小分布于活躍節點附近，能量越大越吸引到活躍節點附近；否則，排斥到邊緣區域。

備選節點：是指該扇形區域所有睡眠節點中能量最大的節點，其比睡眠節點多一個額外的偵聽功能。以A＇為例，其備選節點最靠近節點A＇,以便A＇出現故障或者能量不足，及時喚醒并替換節點A＇。

圖3中空心圈表示處于睡眠的無線傳感器節點，圈中帶點表示活躍節點。

圖2 圓錐型UWSNs三維圖

圖3 圓錐型UWSNs二維俯視圖

以浮標S為中心的UWSNs中，無線傳感器節點根據能量大小能上下左右移動，傳感器節點之間采用超聲波通信，按照從下往上，向最近的上級節點傳遞信息。

1.2 圓錐型UWSNs拓撲構建的思想

1)從整體考慮(層與層之間角度)：以傳感器節點的能量作為判斷節點沉浮的判斷標準，如第一層的能量最低標準為N1,第二層的能量最低標準為N2(N2>N1),則如果第二層傳感器節點能量小于N2，則該傳感器節點上浮到第一層，并由第一層節點能量狀態來決定是活躍、備選還是睡眠；而第二層的傳感器節點則激活備用節點，成為新的第二層傳感器節點，而備選節點則從睡眠節點中選取；如果仍然小于N1則漂浮出水面退出網絡。

2)從局部考慮(扇形或者扇環立體區域角度)：區域內的無線傳感器節點以能量大小為標準，該區域中能量大的節點往區域中心靠攏，能量小的節點遠離區域中心。能量最大的節點,則被激活為該區域的活躍節點，倘若在第一層，該活躍節點則成為浮標S的子節點;否則,成為上層的右節點；而該區域的其他節點則按照能量大小形成分布于活躍節點附近，處于睡眠狀態，其中最靠近活躍節點的，選作備選節點，能量僅次于該區域的活躍節點，并把該節點鏈接到活躍傳感器節點的左節點，隨時待命。

1.3 UWSNs拓撲構建維護

以浮標為中心，從上到下，按照樹結構的思想，連接活躍節點。首先浮標先連接第一層的三個活躍節點，然后各層按照左節點連接該層的備用節點，右節點連接下層活躍節點的思想，水下圓錐通信網絡的活躍傳感器節點與備選節點，形成了一個類二叉樹結構，UWSNs類二叉樹型俯視圖如圖 4所示，簡化類二叉樹型如圖 5所示。其中，X備表示父節點的備份節點。

圖5 UWSNs節點的簡化樹型拓撲結構

若某層活躍節點能量不足，則發送信息給左節點，激活并啟用替代父節點；并選取新備用節點為左節點，啟用偵聽狀態；原父節點則上浮到上層節點，判斷是否小于該層最小能量，如果成立繼續上浮；否則，插入到該層的睡眠節點中。

1.4 UWSNs的路由信息

如圖6，在路由開始階段，浮標節點S查詢其路由鄰居信息表中存儲的發送鄰居節點所需的最小發送功率Pmin，選取合適的P，使其覆蓋第一層的三個活躍傳感器節點。浮標節點S組播路由鏈接請求(routing link request,RLR)信息，其包含有ID、層級信息等。鄰節點收到RLR信息，判斷是否應答，如果是，則反饋路由鏈接應答(routing link answer,RLA)信息，其包含ID、層級、剩余能量等信息，節點根據RLA信息更新路由表，依次類推，維護建立路由表信息。

圖6 路由發起示意圖

UWSNs節點采集到水下信息，由睡眠節點到活躍節點，然后沿著父節點依次逐級往上傳遞。水面浮標更新信息，則是首先判斷A,B,C區域，再沿右節點逐級更新。

2 仿真與性能分析

基于Matlab實現了所涉及的圓錐型UWSNs路由仿真。在實驗中，無線傳感器節點隨機分布在水下三維900 m×900 m×900 m環境中，分布后，按照能量大小進行由遠到近移動，上下浮動，形成以浮標為中心的圓錐型網絡，而樹節點的位置固定在各個扇形區域中心。活躍節點有最大傳送范圍，能輻射所在扇形區域的所有數據。

首先，比較在圓錐型UWSNs中，相同水深，不同總層數的類二叉樹下，探討總層數為4層、6層、8層，而傳感器數量從200只遞增到800只時，三種總層數的數據包傳遞率情況。通過仿真模擬觀察(仿真40次)，相同的水深環境下，總層數越多，數據包傳遞率越大，隨著傳感器數量的增加，數據包傳遞率(PDR)不斷增加，對比圖如圖7所示。

圖7 傳輸半徑100 m時的數據包傳遞率對比

其次，本文的算法以6層類二叉樹為例，與DBR算法進行能耗對比，能耗關系到UWSNs的生命周期，水下無線傳感器在水下很難更新電源，所以節能成為研究重點，能耗越小，則構建拓撲穩定性就越好。具體仿真模擬效果如圖8所示。

圖8 DBR算法與本文算法的總能耗對比圖

3 結束語

本文根據UWSNs的特點，首先構建以水面浮標為中心的圓錐型UWSNs，接著分成三個扇形，各個扇形根據能量大小自動形成活躍節點、備選節點、睡眠節點等，然后按照類二叉樹思想，左節點連接同一個扇形區域的備選節點，右節點連接其所對應的下層活躍節點，如果下層活躍節點因為能量消耗不足或者其他故障，則把該節點上浮到上層，由上層決定其狀態，而與此同時，左節點備選節點替換原父節點。仿真實驗表明:相同水深情況下，層數越多，傳輸包投遞率越高，與DBR算法比較，能耗降低了。

[1] Ayaz M,Nubaig I,Abdullah A,et al.A survey on routing techniques in underwater wireless sensor networks[J].Journal of Network and Computer Application,2011,34(6):1908-1927.

[2] 劉愛平,劉 忠,羅亞松.一種水下無線傳感器網絡的連通性覆蓋算法[J].傳感技術學報,2009,22(1):116-120.

[3] 鐘永信，黃建國，韓 晶.基于空間喚醒的水聲傳感器網絡節能路由協議[J].電子與信息學報，2011,33(6):1326-1331.

[4] 傅質馨,徐志良,黃 成,等.無線傳感器網絡節點部署問題研究[J].傳感器與微系統,2008,27(3):116-120.

[5] 徐 明,劉廣鐘.三維水聲傳感器網絡中高效路由協議的研究[J].計算機科學,2012,39(10):90-124.

[6] 仲元昌,陳 鋒,李發傳,等.大規模無線傳感器網絡覆蓋優化算法[J].傳感器與微系統，2014,33(11):117-120．

[7] 夏 娜，鄭語晨，杜華爭,等．剛性驅動水下傳感器節點自組織布置[J]．計算機學報,2013,36(3):494-505．

[8] 劉玉梁，潘仲明．水下無線傳感器網絡能量路由協議的仿真研究[J].傳感技術學報,2011,24(6):905-908．

[9] Yan H，Shi Zhijie，Cui J H．DBR:Depth-based routing for underwater sensor networks[C]∥Proceedings of Networking,2008:72-86．

陳 軍(1980-)，浙江金華人，副教授，研究方向為網絡安全、系統仿真。

Study of cone type UWSNs based on special binary tree*

CHEN Jun1,2, ZHANG Chang-jiang1

(1.College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China; 2.School of Design and Arts,Zhejiang Industry Polytechnic College,Shaoxing 312000,China)

Aiming at problem of serious energy loss in underwater wireless sensor networks(UWSNs)and the phenomenon of irregular sensor node distribution,construct a new cone type UWSNs,setting each surface buoy nodes as the vertex,the sensor node can move according to energy,the active nodes and the backup node will be abstracted to binary tree structure, which simplifies topology control and routing transmission.Simulation test of algorithm is achieved by Matlab,and respectively discuss the different data packet delivery rate to 4 layers binary tree, 6 layers binary tree 4 and 8 layers binary tree.The results show that the greater the number of layers have, the high the transfer rate is;then compare the algorithm for UWSNs with depth-based routing(DBR)algorithm,it shows that this algorithm has high data packet transfer rate and low energy consumption.

underwater wireless sensor networks(UWSNs); binary tree structure; active node; buoy node

2015—02—08

浙江省自然科學基金資助項目(Y12E050087)；浙江省科技廳公益性應用研究計劃資助項目(2012C23027);浙江省重中之重學科開放基金資助項目(ZC323011014)

10.13873/J.1000—9787(2015)09—0035—03

TP 393

A

1000—9787(2015)09—0035—03