陳 軍, 張長(zhǎng)江

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

?

基于類二叉樹(shù)的圓錐型UWSNs的研究*

陳 軍1,2, 張長(zhǎng)江1

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

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

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

0 引 言

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

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

1 圓錐型UWSNs

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

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

1.1 圓錐形UWSNs模型

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

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

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

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

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

圖2 圓錐型UWSNs三維圖

圖3 圓錐型UWSNs二維俯視圖

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

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

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

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

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

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

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

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

1.4 UWSNs的路由信息

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

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

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

2 仿真與性能分析

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

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

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

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

圖8 DBR算法與本文算法的總能耗對(duì)比圖

3 結(jié)束語(yǔ)

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

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

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

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

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

[7] 夏 娜，鄭語(yǔ)晨，杜華爭(zhēng),等．剛性驅(qū)動(dòng)水下傳感器節(jié)點(diǎn)自組織布置[J]．計(jì)算機(jī)學(xué)報(bào),2013,36(3):494-505．

[8] 劉玉梁，潘仲明．水下無(wú)線傳感器網(wǎng)絡(luò)能量路由協(xié)議的仿真研究[J].傳感技術(shù)學(xué)報(bào),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-)，浙江金華人，副教授，研究方向?yàn)榫W(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é)基金資助項(xiàng)目(Y12E050087)；浙江省科技廳公益性應(yīng)用研究計(jì)劃資助項(xiàng)目(2012C23027);浙江省重中之重學(xué)科開(kāi)放基金資助項(xiàng)目(ZC323011014)

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

TP 393

A

1000—9787(2015)09—0035—03