龚健虎

(澳门城市大学 管理学院,澳门 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-),男,广西桂林人,博士,讲师,主要研究方向为无线传感网、数据库技术。