龔健虎

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

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

龔健虎

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

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

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

0 引 言

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

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

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

1 問題建模

1.1 假設(shè)

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

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

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

1.2 問題定義

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

2 基于的深度計(jì)算

2.1 算法概述

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

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

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

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

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

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

2.3 支配節(jié)點(diǎn)和被支配節(jié)點(diǎn)的深度計(jì)算

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

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

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

(1)

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

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

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

(2)

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

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

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

圖3 深度計(jì)算過程Fig 3 Depth computation process

2.4 偽代碼

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

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

輸入：

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

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

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

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的消息和運(yùn)行時(shí)間復(fù)雜度。

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

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

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

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

3 性能評(píng)估

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

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

3.2 性能結(jié)果

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

1)改變?chǔ)恋膶?shí)驗(yàn)

首先把α從0.5變化至3展開實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖4所示?？梢钥吹剿蟹椒ǖ母采w率隨r/s的增加而增加。原因是當(dāng)r/s增加時(shí)傳輸范圍也增加。如果傳輸范圍增加,節(jié)點(diǎn)間距也將增加,降低了覆蓋重疊,實(shí)現(xiàn)覆蓋最大化。

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

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

在圖5給出了所有算法生成的拓?fù)鋱D的連接性?？梢钥吹?無論α取值如何,CDA始終只形成1個(gè)連通組件;然而,CGCA情況有所不同,直到α=2.5時(shí),網(wǎng)絡(luò)仍未連通。這是因?yàn)镃GCA算法試圖維持較高的覆蓋率,導(dǎo)致節(jié)點(diǎn)鏈路中斷。最終節(jié)點(diǎn)間無路徑到達(dá)水面基站。然而,CGCA算法的連通組件數(shù)量隨α增加而下降。當(dāng)α=2.5時(shí),網(wǎng)絡(luò)連通。

圖5 改變?chǔ)習(xí)r連通組件的數(shù)量Fig 5 Number of connected components by varying α

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

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

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

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

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

4 結(jié) 論

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

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

[2] 王力立,黃 成,徐志良, 等.事件驅(qū)動(dòng)的水下傳感器網(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].電子學(xué)報(bào),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-),男,廣西桂林人,博士,講師,主要研究方向?yàn)闊o線傳感網(wǎng)、數(shù)據(jù)庫(kù)技術(shù)。