基于CDS的水下聲音無線傳感器網絡節點部署方案研究

龔健虎

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

基于CDS的水下聲音無線傳感器網絡節點部署方案研究

龔健虎

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

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

水下聲音無線傳感器網絡； 連通支配集； 深度； 覆蓋； 連通性

0 引 言

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

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

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

1 問題建模

1.1 假設

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

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

圖1 本文網絡模型Fig 1 Network model in this paper

1.2 問題定義

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

2 基于的深度計算

2.1 算法概述

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

2.2 形成二維骨干網絡

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

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

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

圖2 骨干網絡Fig 2 Backbone network

2.3 支配節點和被支配節點的深度計算

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

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

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

(1)

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

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

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

(2)

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

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

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

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

2.4 偽代碼

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

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

輸入：

u：起始節點(開始時是網絡的領袖節點)

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

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

1:Vu←dominatees Of(u)

2:Du←neighborDominators Of(u)

3:Lprevious←Φ

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

5:forallwj∈Vu∪Dudo

6:ifwj.z已經設置過then

7: 繼續下次迭代

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 算法分析

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

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

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

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

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

3 性能評估

3.1 仿真設置和比較對象

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

3.2 性能結果

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

1)改變α的實驗

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

圖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時,如果要保持節點u和v間的通信鏈路,則2個節點間會出現覆蓋重疊。然而,當α大于2時,即使保持鏈路通信,節點也不會有嚴重重疊。因此,對α≥2,所有算法的性能比較穩定。

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

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

圖5的結果還表明:覆蓋范圍和連接性間存在折中關系。因為數據采集必須要求網絡連通,所以，只要α<2.5,就應該首選CDA；否則,首選CGCA。

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

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

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

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

4 結 論

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

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

[2] 王力立,黃 成,徐志良, 等.事件驅動的水下傳感器網絡部署研究[J].傳感器與微系統,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] 蔣 鵬,阮斌鋒.基于分簇的水下傳感器網絡覆蓋保持路由算法[J].電子學報,2013,41(10):2067-2073.

[5] 黃俊杰,孫力娟,王汝傳,等.三維水下傳感器網絡覆蓋優化算法[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-),男,廣西桂林人,博士,講師,主要研究方向為無線傳感網、數據庫技術。