基于CDS的水下聲音無線傳感器網(wǎng)絡(luò)節(jié)點部署方案研究

龔健虎

(澳門城市大學 管理學院,澳門 999078)

基于CDS的水下聲音無線傳感器網(wǎng)絡(luò)節(jié)點部署方案研究

龔健虎

(澳門城市大學 管理學院,澳門 999078)

由于難以訪問三維水下環(huán)境,所以要實現(xiàn)水下聲音無線傳感器網(wǎng)絡(luò)(UAWSNs)最大覆蓋且傳感器自主部署,難度很大。如果還要保證最終網(wǎng)絡(luò)的連通性,則問題更為復雜。提出一種只需把傳感器隨機部署到水面上的UWASNs完全分布式節(jié)點部署算法,目的是使初始網(wǎng)絡(luò)成為可和水面基站進行通信的三維網(wǎng)絡(luò)同時實現(xiàn)最大覆蓋。具體思路是確定初始網(wǎng)絡(luò)的連通支配集,然后調(diào)整具體支配節(jié)點所有相鄰支配節(jié)點和被支配節(jié)點的深度,以盡量降低節(jié)點覆蓋重疊現(xiàn)象,同時保證與支配節(jié)點的連通性。仿真結(jié)果表明：無論傳輸和傳感范圍比如何,網(wǎng)絡(luò)連通性均可保證,且覆蓋范圍性能與覆蓋感知部署算法相近。

水下聲音無線傳感器網(wǎng)絡(luò)； 連通支配集； 深度； 覆蓋； 連通性

0 引 言

水下聲音無線傳感器網(wǎng)絡(luò)(UAWSNs)[1]由通過聲音鏈路進行通信的大量水上和水下傳感器組成。與地面無線傳感器網(wǎng)絡(luò)類似,這些網(wǎng)絡(luò)在覆蓋質(zhì)量、人力、成本和部署方面相對傳統(tǒng)的水下傳感器網(wǎng)絡(luò)有許多優(yōu)勢。人們對UAWSNs環(huán)境下傳感器可能由于環(huán)境特點發(fā)生漂移條件下的節(jié)點部署和移動性建模問題展開研究[2,3]。這些研究的主要目標是在滿足覆蓋、精度、通信質(zhì)量目標函數(shù)前提下,如何降低部署時間和成本,尤其對需要快速遠程部署的應用場景來說,節(jié)點部署更具有重要作用。

文獻[4]提出了一種水下傳感器網(wǎng)絡(luò)單跳覆蓋保持路由(single-hop coverage-preserving routing,SCPR)算法,首先定義了覆蓋冗余度(CR),然后根據(jù)該度量來選舉簇首,最終以單跳方式直接將數(shù)據(jù)傳送至Sink節(jié)點。文獻[5]針對三維水下傳感器網(wǎng)絡(luò)模型,對水下傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化問題進行了描述,提出利用虛擬勢場算法CAT調(diào)整水下傳感器節(jié)點與浮標節(jié)點間纜繩的距離,逐漸消除網(wǎng)絡(luò)中的感知重疊區(qū)域和覆蓋盲區(qū),進而實現(xiàn)整個水下傳感器網(wǎng)絡(luò)覆蓋增強。文獻[6,7]對覆蓋范圍的提升進行了深入研究,提出一種分布式策略,主要根據(jù)深度調(diào)整來解決相關(guān)問題。其中,文獻[6]假設(shè)傳感器在開始時隨機部署于水底,且只知道水深,節(jié)點根據(jù)它們與相鄰節(jié)點的重疊情況來調(diào)整它們的深度。

本文在已有研究工作的基礎(chǔ)上,提出了一種改進的節(jié)點部署方案,并通過仿真實驗驗證了本文方法的有效性。

1 問題建模

1.1 假設(shè)

假設(shè)從直升機上拋下大量傳感器,或者大量傳感器隨機漂浮于水面或水底。每只傳感器有一個聲音解調(diào)器,且可以根據(jù)各種機制調(diào)節(jié)其深度。部署于海洋時,把傳感器拋到水面可能更為高效,因為海水可能很深。部署于湖泊時,傳感器可以沉入水底。無論哪種情況,均假設(shè)傳感器可以通過文獻[8,9]中的各種方法來調(diào)整其深度。另外,假設(shè)這些傳感器通過水下定位技術(shù)確定了自身三維位置,拋下的傳感器形成二維連通網(wǎng)絡(luò)(在水下或水面),每個連通網(wǎng)絡(luò)在水面有一個單獨基站,該基站通過802.11n或者WiMAX鏈路與岸上基站通信。

圖1給出了本文的網(wǎng)絡(luò)模型。在該模型中,各三維傳感器通過聲音信道進行通信,并確定到達水面基站的多跳路徑。假設(shè)UAWSNs網(wǎng)絡(luò)可以模擬為帶有n個節(jié)點的單位球形,所有網(wǎng)絡(luò)節(jié)點的聲音傳輸范圍r相同,如果節(jié)點u和v的三維歐幾里德距離|uv|小于聲音傳輸范圍r,則u和v間存在邊緣,在評估時將相對r來改變傳感范圍s。

圖1 本文網(wǎng)絡(luò)模型Fig 1 Network model in this paper

1.2 問題定義

根據(jù)上述假設(shè),本文研究的問題可以表述為：已知一個n節(jié)點連通網(wǎng)絡(luò),每個節(jié)點的傳輸和感知范圍分別為r和s,節(jié)點部署于邊界確定的水面上,目標是計算每只傳感器的深度,以實現(xiàn)整個三維網(wǎng)絡(luò)覆蓋最大化,同時保證新的網(wǎng)絡(luò)可與和岸上基站通信的水面基站連通。為了實現(xiàn)目標,希望研究一種不需要外界干涉的分布式方法。傳感器只在本地互相通信,除了單跳相鄰節(jié)點信息外不需要其他信息。

2 基于的深度計算

2.1 算法概述

本文基于連通支配集(CDS)的深度計算算法實現(xiàn)網(wǎng)絡(luò)覆蓋最大化,通過調(diào)節(jié)傳感器深度并把深度發(fā)送給水中的三維位置,以盡量降低傳感器感知范圍重疊。如果傳感器存在二維感知重疊,則通過將其移動到不同深度(z軸)可以去除重疊。然而,如果傳感器移出傳輸范圍r,則2只傳感器可能會斷開。因此,本文提出在一定約束條件下調(diào)整深度,以保證連通性。例如：對于具有k個單跳相鄰節(jié)點的節(jié)點,在調(diào)整深度時,即使傳感器充分向上或向下移動,所有k個相鄰節(jié)點仍然可以保證連通性?；谝陨系乃悸?確定網(wǎng)絡(luò)的骨干,并將節(jié)點的移動這一任務分配給骨干網(wǎng)上的節(jié)點。為此,需要使用連通支配集CDS。CDS集合中成為支配節(jié)點的每個成員計算屬于它的被支配節(jié)點(不屬于骨干的節(jié)點)的深度。此外,它還需要計算與它相鄰的支配節(jié)點的深度。因此,從支配節(jié)點中選擇一個領(lǐng)袖節(jié)點來啟動該深度計算過程。支配節(jié)點深度計算完成后,將會命令一個相鄰節(jié)點執(zhí)行相同的計算過程,依次迭代。這一迭代計算會覆蓋所有支配節(jié)點。于是,本文方法分為2步： 1)形成骨干網(wǎng)絡(luò); 2)支配節(jié)點和被支配節(jié)點計算深度。

2.2 形成二維骨干網(wǎng)絡(luò)

為了實現(xiàn)覆蓋最大化,在確定節(jié)點深度時還必須要確定保持哪些鏈路,此時就需要用到CDS集合。CDS提供了一個連通骨干網(wǎng)絡(luò),網(wǎng)絡(luò)中的每個節(jié)點通過單跳路徑可以到達骨干網(wǎng)。骨干網(wǎng)的每個元素稱為支配節(jié)點,其他節(jié)點稱為被支配節(jié)點,如圖2所示。本文使用文獻[9]中的啟發(fā)式策略,通過每個節(jié)點交換4條信息來確定CDS集合。確定完支配節(jié)點后,網(wǎng)絡(luò)其他節(jié)點選擇與單跳相鄰支配節(jié)點連接。因為一條鏈路便足夠,所以,需要確定保留哪些鏈路。

在本文方法中,利用覆蓋范圍作為選擇標準。具體來說,把每個被支配節(jié)點分配給感知覆蓋重疊率在各種分配方案中最小的支配節(jié)點。通過這種方法,可以防止被支配節(jié)點到達新的深度時發(fā)生覆蓋范圍重疊現(xiàn)象。例如:在圖2(b)中,選擇S6作為S5的支配節(jié)點而不是S4,因為S4和S5間存在重疊。本文選擇傳感覆蓋重疊最小的節(jié)點作為支配節(jié)點。

確定完支配節(jié)點后,通過預先指定ID最小的節(jié)點作為領(lǐng)袖節(jié)點,以啟動深度調(diào)整過程。如果運行完深度計算算法后ID最小節(jié)點不是支配節(jié)點,則選擇其對應的支配節(jié)點作為領(lǐng)袖節(jié)點。

圖2 骨干網(wǎng)絡(luò)Fig 2 Backbone network

2.3 支配節(jié)點和被支配節(jié)點的深度計算

本文深度計算算法基于信標策略。擁有信標的支配節(jié)點計算其被支配節(jié)點和還未接收到信標的相鄰支配節(jié)點的深度。已經(jīng)計算完畢的節(jié)點可以忽略該信息;其他節(jié)點需要執(zhí)行計算過程,再把信標廣播給其他相鄰節(jié)點,以此類推。最后,CDS集合的所有元素將接收到信標,執(zhí)行深度計算過程。深度計算完畢的節(jié)點并不會立刻移動到新的深度,相反,它們需要等待其他節(jié)點完成深度調(diào)整過程。當所有節(jié)點的深度計算完畢,節(jié)點開始下降到各自深度。

網(wǎng)絡(luò)CDS集合計算完后,領(lǐng)袖節(jié)點擁有信標,將自己的深度設(shè)置為預先設(shè)定值,然后啟動深度調(diào)整過程。如上文所述,為了保證確定深度時的連接性,必須要保證支配節(jié)點—被支配節(jié)點和被支配節(jié)點—支配節(jié)點間的邊緣。因此,深度計算過程的思路就是在保證與支配節(jié)點的通信鏈路不中斷的前提下使相鄰節(jié)點盡量遠,具體見下文。

設(shè)u表示擁有信標的支配節(jié)點(開始時是領(lǐng)袖節(jié)點), 的被支配節(jié)點集合是Vu={w1,…,wi},u的相鄰支配節(jié)點集合是Du={wi+1,…,wn}。假設(shè)節(jié)點的二維坐標(即x和y的坐標)和傳輸范圍r已知,U可以利用如下三維勾股定理,結(jié)合wj∈Vn∪Du條件,計算wj的相對深度

(1)

式(1)中,將wj稱為u的目標節(jié)點,u稱為wj的基本節(jié)點。該式表明,如果要保證u和wj間的通信鏈路暢通,則wj的最遠位置是以u為中心、以r為半徑的球體表面。如果u和v間的距離小于x和y軸感知范圍的2倍,則把u和v定位在同一深度會導致覆蓋重疊。因此,確定目標節(jié)點的位置是實現(xiàn)覆蓋重疊最小化的關(guān)鍵步驟。

為了處理這一問題,每個支配節(jié)點保留一個可能位置列表。保存該列表的目的是檢查目標節(jié)點的所有可能深度,選擇最合適的深度。深度列表的元素為{節(jié)點,符號}二元組。在該二元組元素中,“節(jié)點”表示基本節(jié)點,且目標節(jié)點的深度相對該節(jié)點進行計算?！胺枴北硎灸繕斯?jié)點垂直放置在基本節(jié)點的上面還是下面。如果符號為正,表示目標節(jié)點放在基本節(jié)點的上面；否則,在下面。

本文深度調(diào)整算法如下：開始時,支配節(jié)點u的位置列表包括2個元素{{u,+},{u,-}}。u開始迭代其被支配節(jié)點列表Vu。在首次迭代時,算法選擇w1∈Vu,計算2個深度d1和d2(每個列表元素一個深度)

(2)

對目標節(jié)點w1,如果節(jié)點w1相對其他節(jié)點在深度d1的覆蓋重疊低于在深度d2時,則算法設(shè)置w1.z=d1;否則,w1.z=d2。深度設(shè)置后,u向列表添加兩個元素,添加后列表為{{u,+},{u,-},{w1,+},{w1,-}}。在第二次迭代時,對節(jié)點w2∈Vu,u計算4個深度,選擇可以實現(xiàn)范圍重疊最低的最優(yōu)節(jié)點。持續(xù)這一過程,直到基本節(jié)點的所有支配和被支配節(jié)點深度處理完畢。

圖3給出了深度計算過程。圖3(a)給出了深度計算前的節(jié)點二維投影。該圖表明,w1,w2,w3∈Vu互相之間非常接近,二維覆蓋重疊度較大。因此,為了最小化重疊度,這些節(jié)點必須處于不同深度,同時保持與基站u的連接性。本文算法把首個節(jié)點w1放在u的上方。下次迭代時,w2不得再次放在u上方,因為它將與w1重疊。因此,算法把w2放在u下方。在第三次迭代時,w3既不能放在u上方,也不能放在u下方。于是,下一合適位置選為w1上方。支配節(jié)點u持續(xù)迭代過程,直到所有相鄰節(jié)點的深度設(shè)置完畢。如果相鄰支配節(jié)點wj∈Du的深度先前被另一支配節(jié)點設(shè)置過,則算法跳過該節(jié)點。

支配節(jié)點為其被支配節(jié)點和相鄰支配節(jié)點分配好深度后,把信標和被該支配節(jié)點部署的節(jié)點列表,遞交給相鄰的支配節(jié)點,命令這些支配節(jié)點對它們的相鄰節(jié)點做相同處理。通過使用被u部署的節(jié)點列表,相鄰支配節(jié)點可以避免與自身目標節(jié)點和先前被部署節(jié)點的覆蓋重疊。

圖3 深度計算過程Fig 3 Depth computation process

2.4 偽代碼

深度計算過程的偽代碼見算法1。本文假設(shè)支配節(jié)點 運行算法(開始時領(lǐng)袖節(jié)點將運行算法)。算法首先初始化被支配節(jié)點和相鄰支配節(jié)點集合(第1,2行)。第3行創(chuàng)建空列表Ldeployed,于是每當計算各個節(jié)點的深度時,算法把被部署節(jié)點加入該列表。在第4行,算法初始化元素為{u,+}和{u,-}的位置列表G。從第5～20行,u開始迭代其被支配節(jié)點和相鄰支配節(jié)點。如果在第j次迭代時選擇的節(jié)點wj的深度已經(jīng)計算出來,則算法跳過該節(jié)點,繼續(xù)下一次迭代(第6,7行)。然后,根據(jù)圖G中的每個相對位置,算法計算wj的深度(第12,13,14行),接著計算wj與d深處Ldeploved∪Lprevious集合中節(jié)點的覆蓋重疊(第15行)。如果重疊小于迄今最小重疊,算法用新值替換當前最優(yōu)深度值(第18行)。當計算完wj的最優(yōu)深度值后,算法將wj的深度設(shè)為d(第21行),把wj添加到被部署節(jié)點列表Ldepolyed中(第22行),同時用新的相對位置更新圖G(第23行)。在迭代結(jié)束時,算法也就完成了深度計算,將向其深度已經(jīng)計算好的被支配節(jié)點和相鄰支配節(jié)點廣播消息(第25行)。

算法1：深度計算算法(CDA)

輸入：

u：起始節(jié)點(開始時是網(wǎng)絡(luò)的領(lǐng)袖節(jié)點)

Lprevlous：上一支配節(jié)點部署的節(jié)點列表(開始時領(lǐng)袖節(jié)點的列表為空)

輸出：可以保證最大覆蓋與連通性的被支配節(jié)點和相鄰支配節(jié)點的深度

1:Vu←dominatees Of(u)

2:Du←neighborDominators Of(u)

3:Lprevious←Φ

4:G←{{u,+},{u,-}}

5:forallwj∈Vu∪Dudo

6:ifwj.z已經(jīng)設(shè)置過then

7: 繼續(xù)下次迭代

8:endif

9: minOverlap←MAXAL

10: depth←nil

11:forallg∈Gdo

12: n←g.node,s←g.sign

14: d←n.z+s.Δd

15: p←overlap(wj,Lprevious∪Ldeployed,d)

16:ifp

17: minOverlap←p

18: depth←d

19:endif

20:endfor

21: wj.z←depth

22: Ldeployed←Ldeployed∪{wj}

23: G←G∪{{wj,+},{wj,-}}

24:endfor

25:broadcast(wj∈(Ldeployed∩(Vu∪Du)),Ldeployed)

2.5 算法分析

本節(jié)給出了本文CDA的消息和運行時間復雜度。

定理1 假設(shè)領(lǐng)袖節(jié)點事先確定(即無消息成本),則本文CDA每個節(jié)點的最差消息復雜度和整個網(wǎng)絡(luò)的運行時間復雜度分別為O(1)和O(2),其中,n是節(jié)點數(shù)量。

證明：本文方法有2個主要階段:1)骨干網(wǎng)絡(luò)的確定(即CDS的計算);2)深度計算。在網(wǎng)絡(luò)確定階段,算法確定所有節(jié)點的支配節(jié)點和被支配節(jié)點。為了確定一個節(jié)點是支配節(jié)點還是被支配節(jié)點,每個節(jié)點發(fā)送4個消息。在第二階段,從領(lǐng)袖節(jié)點開始,每個支配節(jié)點計算其被支配節(jié)點和支配節(jié)點的深度,通過廣播消息來向相鄰節(jié)點宣布計算出來的深度,并把信標傳遞給相鄰支配節(jié)點。因此,一個節(jié)點的消息復雜度為O(1)。因為網(wǎng)絡(luò)有n個節(jié)點,所以,總體消息復雜度為O(n)。

定理2 深度計算過程的最差時間復雜度為O(d2),其中d為網(wǎng)絡(luò)CDS圖的最大節(jié)點度(即相鄰節(jié)點數(shù)量)。

證明：算法1有2個嵌套for循環(huán)(第5～24行和第11～20行)。設(shè)Vu∪Du的基數(shù)為d。外層for循環(huán)迭代d次。內(nèi)層for循環(huán)迭代次數(shù)是被部署節(jié)點數(shù)量的2倍,最大為2 d。因此,總體最差時間復雜度為O(d2)。

3 性能評估

3.1 仿真設(shè)置和比較對象

本文采用Matlab2012軟件進行仿真實驗。仿真時改變2個參數(shù),即傳輸范圍和感知范圍(表示為α)之比和節(jié)點數(shù)量。在第1組仿真中,設(shè)置感知范圍s為10m,節(jié)點數(shù)量為700。通過r=s·α計算傳輸范圍r。把700個節(jié)點均勻隨機部署于目標區(qū)域(100m×100m,最大深度500m),在進行仿真時改變α值且0.5≤α≤3。在第2組仿真中,把s和r分別設(shè)置為10，1.8m(即α為1.8),節(jié)點數(shù)量范圍為500～900。

3.2 性能結(jié)果

本節(jié)給出性能結(jié)果。每次仿真包括100種不同拓撲,取均值作為最終結(jié)果。本文結(jié)果以95%的置信區(qū)間保持在樣本均值的5 %～10 %范圍內(nèi)。

1)改變α的實驗

首先把α從0.5變化至3展開實驗。實驗結(jié)果如圖4所示。可以看到所有方法的覆蓋率隨r/s的增加而增加。原因是當r/s增加時傳輸范圍也增加。如果傳輸范圍增加,節(jié)點間距也將增加,降低了覆蓋重疊,實現(xiàn)覆蓋最大化。

圖4 n=700且s=10時改變α =r/s獲得的覆蓋率比較情況Fig 4 Coverage percentage comparison for varying α=r/s where n=700 and s=10

圖4也表明,本文CDS算法的覆蓋性能非常接近于CGCA。當α≥2時,二者算法的性能差距基本恒定在10 %左右。當r<2s時,如果要保持節(jié)點u和v間的通信鏈路,則2個節(jié)點間會出現(xiàn)覆蓋重疊。然而,當α大于2時,即使保持鏈路通信,節(jié)點也不會有嚴重重疊。因此,對α≥2,所有算法的性能比較穩(wěn)定。

在圖5給出了所有算法生成的拓撲圖的連接性。可以看到:無論α取值如何,CDA始終只形成1個連通組件;然而,CGCA情況有所不同,直到α=2.5時,網(wǎng)絡(luò)仍未連通。這是因為CGCA算法試圖維持較高的覆蓋率,導致節(jié)點鏈路中斷。最終節(jié)點間無路徑到達水面基站。然而,CGCA算法的連通組件數(shù)量隨α增加而下降。當α=2.5時,網(wǎng)絡(luò)連通。

圖5 改變α時連通組件的數(shù)量Fig 5 Number of connected components by varying α

圖5的結(jié)果還表明:覆蓋范圍和連接性間存在折中關(guān)系。因為數(shù)據(jù)采集必須要求網(wǎng)絡(luò)連通,所以，只要α<2.5,就應該首選CDA；否則,首選CGCA。

2)改變節(jié)點數(shù)量時的實驗，將節(jié)點數(shù)量從500變?yōu)?00,評估CDA在覆蓋方面的性能。圖6表明,當節(jié)點數(shù)量增加時,二種方法均出現(xiàn)性能下降。這一現(xiàn)象看似矛盾,但可解釋如下：當增加節(jié)點數(shù)量時,式(2)定義的理論上界上升。根據(jù)式(3),Vmax增加,覆蓋率下降。當節(jié)點數(shù)量增加時能夠?qū)崿F(xiàn)的覆蓋率增加,同時重疊現(xiàn)象增加,以補償可能增加的覆蓋率，于是,覆蓋率下降。鑒于連通性約束,重疊現(xiàn)象增加時,CDA的覆蓋率下降更為明顯。部分節(jié)點部署在其他地方無法保持連接性。

圖7通過衡量生成的拓撲結(jié)構(gòu)來重復連通性實驗。可以看到,CDA在各種節(jié)點數(shù)量條件下生成的拓撲結(jié)構(gòu)均連通。然而,CGCA生成的拓撲不是如此。本文作者發(fā)現(xiàn),當節(jié)點數(shù)量增加時連通拓撲數(shù)量下降,但從未到達1。需要更多的節(jié)點來保證連通性。出現(xiàn)這一結(jié)果的一個原因就是α值設(shè)為1.8,設(shè)置值不太合適,難以保證連通性,如圖5所示。

圖6 r=18且s=10時改變傳感器節(jié)點數(shù)量獲得的 覆蓋率比較情況Fig 6 Coverage percentage comparison for varying number of sensor nodes where r=18 and s=10

圖7 r=18且s=10時改變傳感器節(jié)點數(shù)量獲得的覆蓋率 比較情況Fig 7 Number of connected components comparison for varying number of sensor nodes where r=18 and s=10

4 結(jié) 論

由于環(huán)境不可訪問,需要一種分布式機制,以便提高在復雜環(huán)境情況下運行的多種UAWSNs應用的柔韌性。假設(shè)傳感器從直升機拋下后均勻隨機部署于目標區(qū)域,研究目標是計算傳感器的深度,在實現(xiàn)總體傳感器覆蓋范圍最大化的同時保證節(jié)點與水面基站的連通性。本文中提出一種UAWSNs純分布式節(jié)點部署機制,通過假設(shè)節(jié)點只能在垂直方向移動來改變傳感器深度。仿真實驗結(jié)果表明：本文算法在保持網(wǎng)絡(luò)連通性的同時,實現(xiàn)的覆蓋效果與基準算法非常相近。

[1] 郭忠文,羅漢江,洪 鋒,等.水下無線傳感器網(wǎng)絡(luò)的研究進展[J].計算機研究與發(fā)展,2010,47(3):377-389.

[2] 王力立,黃 成,徐志良, 等.事件驅(qū)動的水下傳感器網(wǎng)絡(luò)部署研究[J].傳感器與微系統(tǒng),2013,32(9):50-52.

[3] Gkikopouli A,Nikolakopoulos G,Manesis S.A survey on underwater wireless sensor networks and applications[C]∥2012 ue 20th Mediterranean Conference on Control & Automation,IEEE,2012:1147-1154.

[4] 蔣 鵬,阮斌鋒.基于分簇的水下傳感器網(wǎng)絡(luò)覆蓋保持路由算法[J].電子學報,2013,41(10):2067-2073.

[5] 黃俊杰,孫力娟,王汝傳,等.三維水下傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].Journal of Nanjing University of Posts and Telecommunications:Natural Science,2013,33(5):123-129.

[6] Akkaya K,Newell A.Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks [J].Computer Communications,2009,32(7):1233-1244.

[7] Cayirci E,Tezcan H,Dogan Y,et al.Wireless sensor networks for underwater survelliance systems [J].Ad Hoc Networks,2006,4(4):431-446.

[8] Cui J H,Kong J,Gerla M,et al.The challenges of building mobile underwater wireless networks for aquatic applications [J].Network,IEEE,2006,20(3):12-18.

[9] Wu J,Li H.On calculating connected dominating set for efficient routing in Ad Hoc wireless networks[C]∥Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications,ACM,1999:7-14.

Research on node deployment scheme in UAWSNs based on CDS

GONG Jian-hu

(School of Management,City University of Macau,Macau 999078,China)

Self-deployment of sensors with maximized coverage in underwater acoustic wireless nensor networks (UAWSNs) is challenging due to difficulty of access to 3D underwater environments.The problem is further complicated if connectivity of the final network is required.Propose a purely distributed node deployment scheme for UAWSNs which only requires random dropping of sensors on water surface.The goal is to expand the initial network to 3D with maximized coverage and guaranteed connectivity with a water surface base station.The idea is based on determining connected dominating set of the initial network and then adjust the depths of all dominate and dominator neighbors of a particular dominator node for minimizing the coverage overlaps among them while still keeping the connectivity with the dominator.Simulations results indicate that connectivity can be guaranteed regardless of the transmission and sensing range ratio with coverage very close to a coverage-aware deployment approach.

underwater acoustic wireless sensor networks(UAWSNs); connected dominating set; depths; coverage; connectivity

10.13873/J.1000—9787(2014)08—0018—05

2014—05—23

TP 393

A

1000—9787(2014)08—0018—05

龔健虎(1967-),男,廣西桂林人,博士,講師,主要研究方向為無線傳感網(wǎng)、數(shù)據(jù)庫技術(shù)。