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

陳 軍, 張長江

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

?

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

陳 軍1,2, 張長江1

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

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

水下無線傳感器網(wǎng)絡(luò)； 二叉樹結(jié)構(gòu)； 活躍節(jié)點； 浮標(biāo)節(jié)點

0 引 言

水下無線傳感器網(wǎng)絡(luò)[1](underwater wireless sensor networks,UWSNs)通常用來對水體環(huán)境監(jiān)測、水下目標(biāo)探測等應(yīng)用，將收集的數(shù)據(jù)做處理，以聲波傳輸?shù)姆绞絺魉偷絽R水上浮標(biāo)節(jié)點。UWSNs是由具有聲學(xué)通信與計算能力的傳感器節(jié)點構(gòu)成的水下監(jiān)測網(wǎng)絡(luò)系統(tǒng)，隨著無線傳感器技術(shù)的發(fā)展，當(dāng)前UWSNs的研究已經(jīng)引起了學(xué)術(shù)界的高度重視,針對UWSNs的系統(tǒng)結(jié)構(gòu)水下定位水聲通信等研究領(lǐng)域已經(jīng)開展了大量基礎(chǔ)研究，并取得了一定的成果。其對于保護(hù)水資源、開發(fā)利用海洋資源等提供有力的保障，因此,UWSNs的研究越來越熱，尤其UWSNs的拓?fù)淇刂芠2](拓?fù)錁?gòu)建、維護(hù)更新等)和路由協(xié)議成為其中一個重要的研究方向[3～5]。

針對UWSNs能量損耗嚴(yán)重，節(jié)點分布不均勻無規(guī)律等現(xiàn)象[6,7]，本文提出利用水面浮標(biāo)節(jié)點為頂點，構(gòu)建一個圓錐型UWSNs，并按照節(jié)點能量為衡量標(biāo)準(zhǔn)，設(shè)置節(jié)點的沉浮，協(xié)調(diào)節(jié)點之間的遠(yuǎn)近距離，形成各扇形區(qū)域，所有活躍節(jié)點、備選節(jié)點形成一個類二叉樹結(jié)構(gòu)的拓?fù)淇刂坪吐酚?所謂類二叉樹是指該樹第一層有3個子樹，其余節(jié)點均為二叉樹，為了表述方便簡稱之)。通過仿真模擬測試[8]，比較不同總層數(shù)的效果，并比較了總層數(shù)為6的算法與深層路由(depth-based routing,DBR)算法[9]，取得一定的效果。

1 圓錐型UWSNs

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

圖1 三維UWSNs定位系統(tǒng)

1.1 圓錐形UWSNs模型

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

活躍節(jié)點：指在扇形區(qū)域中能量最大的一個，用于收集該區(qū)域的其他傳感器節(jié)點的數(shù)據(jù)。以A＇為例，定時活動于所在扇形區(qū)域的中心線上，用于收集該扇形區(qū)域所有傳感器節(jié)點的數(shù)據(jù)，并處理轉(zhuǎn)發(fā)給上級節(jié)點。

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

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

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

圖2 圓錐型UWSNs三維圖

圖3 圓錐型UWSNs二維俯視圖

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

1.2 圓錐型UWSNs拓?fù)錁?gòu)建的思想

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

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

1.3 UWSNs拓?fù)錁?gòu)建維護(hù)

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

圖5 UWSNs節(jié)點的簡化樹型拓?fù)浣Y(jié)構(gòu)

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

1.4 UWSNs的路由信息

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

圖6 路由發(fā)起示意圖

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

2 仿真與性能分析

基于Matlab實現(xiàn)了所涉及的圓錐型UWSNs路由仿真。在實驗中，無線傳感器節(jié)點隨機(jī)分布在水下三維900 m×900 m×900 m環(huán)境中，分布后，按照能量大小進(jìn)行由遠(yuǎn)到近移動，上下浮動，形成以浮標(biāo)為中心的圓錐型網(wǎng)絡(luò)，而樹節(jié)點的位置固定在各個扇形區(qū)域中心。活躍節(jié)點有最大傳送范圍，能輻射所在扇形區(qū)域的所有數(shù)據(jù)。

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

圖7 傳輸半徑100 m時的數(shù)據(jù)包傳遞率對比

其次，本文的算法以6層類二叉樹為例，與DBR算法進(jìn)行能耗對比，能耗關(guān)系到UWSNs的生命周期，水下無線傳感器在水下很難更新電源，所以節(jié)能成為研究重點，能耗越小，則構(gòu)建拓?fù)浞€(wěn)定性就越好。具體仿真模擬效果如圖8所示。

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

3 結(jié)束語

本文根據(jù)UWSNs的特點，首先構(gòu)建以水面浮標(biāo)為中心的圓錐型UWSNs，接著分成三個扇形，各個扇形根據(jù)能量大小自動形成活躍節(jié)點、備選節(jié)點、睡眠節(jié)點等，然后按照類二叉樹思想，左節(jié)點連接同一個扇形區(qū)域的備選節(jié)點，右節(jié)點連接其所對應(yīng)的下層活躍節(jié)點，如果下層活躍節(jié)點因為能量消耗不足或者其他故障，則把該節(jié)點上浮到上層，由上層決定其狀態(tài)，而與此同時，左節(jié)點備選節(jié)點替換原父節(jié)點。仿真實驗表明:相同水深情況下，層數(shù)越多，傳輸包投遞率越高，與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] 劉愛平,劉 忠,羅亞松.一種水下無線傳感器網(wǎng)絡(luò)的連通性覆蓋算法[J].傳感技術(shù)學(xué)報,2009,22(1):116-120.

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

[4] 傅質(zhì)馨,徐志良,黃 成,等.無線傳感器網(wǎng)絡(luò)節(jié)點部署問題研究[J].傳感器與微系統(tǒng),2008,27(3):116-120.

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

[6] 仲元昌,陳 鋒,李發(fā)傳,等.大規(guī)模無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].傳感器與微系統(tǒng)，2014,33(11):117-120．

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

[8] 劉玉梁，潘仲明．水下無線傳感器網(wǎng)絡(luò)能量路由協(xié)議的仿真研究[J].傳感技術(shù)學(xué)報,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-)，浙江金華人，副教授，研究方向為網(wǎng)絡(luò)安全、系統(tǒng)仿真。

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

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

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

TP 393

A

1000—9787(2015)09—0035—03