水声网络中生物友好的网关部署优化

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-03-23

金志刚¹, 王宁¹, 吴菁晶², 苏毅珊¹
1. 天津大学电气自动化与信息工程学院, 天津 300072;
2. 东北大学计算机科学与工程学院, 辽宁沈阳 110169
收稿日期：2017-04-10
基金项目：国家自然科学基金资助项目(61571318)；海南省重点研发计划项目(ZDYF2018006)；广西壮族自治区科技项目(2016AC01003)。
作者简介：金志刚(1972-)，男，上海人，天津大学教授，博士生导师。

摘要：海洋哺乳动物与水声传感器网络共享水声信道, 导致网络端到端延时增加, 数据包投递率降低.针对这一问题, 提出一种生物友好的水声网络多网关部署优化策略.该策略以网关作为网络的数据汇聚中心, 用统计学方法确定海洋哺乳动物位置, 并根据水声信道模型计算生物干扰半径, 从而确定生物-网关干扰区域.以最小化网络端到端平均时延为目标, 联合整数线性规划和贪婪-交换启发式算法优化网关部署.仿真结果表明:与随机部署和不考虑生物干扰的网关部署方法相比, 采用本文策略使端到端时延降低62%和52%, 数据包投递率提高36%和19%.
关键词：水声传感器网络生物友好网关端到端时延贪婪-交换算法
Environment-Friendly Optimized Gateway Deployment for Underwater Acoustic Sensor Networks
JIN Zhi-gang¹, WANG Ning¹, WU Jing-jing², SU Yi-shan¹
1. School of Electrical and Information Engineering, Tianjin University, Tianjin 300072, China;
2. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: SU Yi-shan, E-mail: yishan.su@tju.edu.cn
Abstract: A novel environment-friendly optimized gateway deployment for underwater acoustic sensor networks is proposed to overcome the problem of increased end-to-end delay and decreased packet delivery rate caused by marine mammals sharing the acoustic channel with underwater acoustic sensor networks. Gateways are considered as data centers of underwater acoustic sensor networks and the location of marine mammals is determined with statistical methods. The interference region of mammals-gateway is determined through combining the location with the radius of interference calculated by acoustic channel model. The strategy utilizes integer linear programming and greedy-exchange heuristic algorithm to realize the minimization of the average end-to-end delay. Simulation results and comparisons with the random deployment and the deployment ignoring mammals show that the new proposed gateway deployment strategy decreases the end-to-end delay by 62% and 52% and increases the packet delivery rate by 36% and 19%.
Key words: underwater acoustic sensor networkenvironment-friendlygatewayend-to-end delaygreedy-exchange algorithm
随着海洋开发与利用的力度日益加大, 水声传感器网络(underwater acoustic sensor networks, UASNs)越来越多地应用于商业、环境保护和军事领域.复杂的水声通信环境导致水声信道具有带宽有限、高延迟、高误码率以及节点动态变化的特性^[1], 这些特性使得UASNs在网关部署、信道接入、节点定位及路由选择等方面面临许多问题，并且对于水声信道来说, 海洋生物、UASNs节点及其他人工水声网络共享稀缺的水下频谱资源, 又给UASNs的拓扑设计带来巨大挑战.
由于网关需要收集无线传感器节点采集的数据信息并将其传送到数据中心, 导致网络中的大部分数据都汇聚到网关, 因此网关的部署位置就成为影响整个网络性能的重要因素.网关部署大多采用以节点K为中心的方式, 将网络中的节点作为网关候选, 对网关选择进行优化, 这种网关部署方式简单快捷, 得到广泛研究和应用^[2].由于陆上传感器网络一般只考虑平面架构, 而UASNs节点和网关部署一般都为三维空间, 其中最接近UASNs的陆上节点部署是关于中继节点的部署^[3].但水声信道与陆上无线信道不同, 需要考虑的因素也不同, 比如由于水声信号传输速率较小, 需要充分考虑其在水声信道传输的时延问题.文献[4]提出一种水面多网关部署方法，在网关间使用无线电通信, 大大降低了网络时延.
由于各类海洋哺乳动物的回声定位(clicks)、应急突发(burst pulse)以及通讯信号(whistle)^[5]也是以水声信号为载体，因此一方面海洋哺乳动物声信号使得UASNs内的水声信号噪声增加, 因此为了达到接收端的信噪比门限需要增大信号的发送功率, 这将降低网络空间复用率和网络寿命.甚至生物的声信号会造成水下节点的采集数据到网关的路径不可达；另一方面水声网络对海洋哺乳动物的声学干扰会导致动物定位错误、行为紊乱, 甚至会使其听力缺失以致死亡.文献[6]虽然考虑了水下传感器网络的生物友好问题, 但其是通过频谱感知的方式定位哺乳动物临时位置, 从而实现生物友好的频谱决策.但是对于海洋哺乳动物长期存在的区域, 比如生活着中华白海豚和江豚等多种海洋哺乳动物的中国的北部湾部分海域, 如果仅仅通过频谱分配和功率控制避免两者的相互干扰, 就需要节点进行频繁的信道估计和路由决策^[7], 势必会产生较大的时间和能量上的开销.
针对上述问题, 本文提出一种生物友好的水声网络网关部署策略(environment-friendly underwater gateway deployment strategy, EF-UGD).EF-UGD通过统计待测水域海洋生物的大概率存在位置进而确定生物-网关干扰区域, 并将网关部署问题转化为整数线性规划问题.在考虑生物-网关干扰的情况下, 以最小化端到端的平均传输时延为目标, 充分考虑网络通信链路的流量约束和网关数目限制等条件, 使用贪婪-交换启发式算法优化水面网关部署位置，得到近优解.
1 生物友好的网关部署优化生物友好的网关部署既要考虑生物对网关由于信道共享造成的信号干扰, 还需规避网络对生物的干扰.因此优化网关部署, 要规避海洋哺乳动物与网关的干扰区域, 优化网络拓扑结构, 设计满足端到端时延最短的网关优化部署策略.
1.1 网关部署模型本文考虑的网关部署基于已知的水下网络节点部署, 并考虑水生哺乳动物与网关的相互干扰, 如图 1所示.将网关部署优化问题看作图优化问题, 其中图优化问题中的节点代表水下传感器和网关的候选位置, 通过选择一组网关候选位置的子集, 在满足数据流约束、生物-网关干扰约束以及水面网关数量约束的条件下设计网关部署策略，优化网络性能.
图 1(Fig. 1)

图 1 生物友好的网关部署Fig.1 Environment-friendly gateway deployment

候选位置的选择是一个比较复杂的问题, 本文只研究当已经给定了网关的候选位置, 并且是在已满足连接的约束条件的前提下, 即每个水下节点都必须至少有一个到网关候选位置的可达路径的条件下选择网关节点位置.其中每个水下节点信息的产生速率相同, 网关必须收集所有产生的数据包.对由于MAC协议产生的排队延迟来说, 在网络负载小的情况下可以忽略, 并且数据碰撞的可能性也很小, 可以忽略其对网络性能的影响.
1.2 生物-网关干扰区域的划定为了避免网关的数据传输与海洋哺乳动物活动的相互干扰, 需要定义生物-网关干扰区域.其中生物-网关干扰区域的确定需要分为两部分:海洋哺乳动物聚集区域MMGR(marine mammal gathering region)和水声干扰区域MMIR(marine mammal interference region)的确定.
首先是MMGR的确定.通过对待测水体区域海洋哺乳动物的长期观测, 统计观测数据并通过聚集分布CA指数的计算, 确定中华白海豚是聚集分布类型, 即在同一区域的不同位置其存在概率非均匀分布，根据海洋哺乳动物出现概率对监测水域进行划分.设出现概率分别为P₁, P₂, …, P_n且P₁＞P₂＞…＞P_n, P₁+P₂+…+P_n=1，若P_i+1＜P_th≤P_i, i∈[1, n-1]则哺乳动物出现概率P_i对应的位置即为MMGR，其中P_th为设定的出现概率阈值.例如以中华白海豚为例, 文献[8]中观测并统计了中华白海豚出现位置分别与水深以及与海岸线距离的关系的概率分布情况.其中水深在0~5 m，5~10 m，10~15 m，15~20 m和20~25 m时, 生物出现的概率分别为8%，52%，32%，7%和2%.距离海岸线分别为0~0.2 km，0.2~0.4 km，0.4~0.6 km，0.6~0.8 km，0.8~1.0 km和1.0~1.5 km时, 生物出现的概率分别为26%，60%，10%，2%，1%和2%.若P_th=50%，则相应的MMGR即为水深5~10 m的区域和距离海岸线200~400 m的区域.
然后是对MMIR的划定.将干扰距离d_inf定义为当某一干扰源与接收端的距离小于干扰距离时, 干扰信号将会使接收节点的通信不能正常进行, 导致接收错误或接收中断.一般情况下, 随着通信系统作用距离和工作频率的增加, 水声信号的能量损失也会增加, 这就限制了水声信号最大作用距离和最高工作频率, 也使得带宽受限.对于水下声通信, 信道增益为

(1)

(2)

式中:A₀是归一化常数; k是传播系数(对于水声通信k通常取1.5);d是发送端与接收端之间的距离; α是吸收系数.
水声信道的可用带宽极窄, 随着通信系统作用距离的增加, 水声信道的可用工作带宽大大降低.源端和目的端的距离与相应的可用带宽关系如表 1所示.
表 1(Table 1)

表 1 通信距离与带宽关系Table 1 Relationship of communication distance to bandwidth

距离d/km	带宽B/kHz
d=1 000	B＜1
10＜d＜100	2＜B＜5
1＜d＜10	B≈10
0.1＜d＜1	20＜B＜50
d＜0.1	B＞100

表 1 通信距离与带宽关系 Table 1 Relationship of communication distance to bandwidth

此外, 源端和目的端节点的相对运动也会增强水声信道的时变和空变特性, 进而增强多普勒频移, 使得网络的误码率增大.多普勒频移为

(3)

式中:f_d为多普勒频移; f_r为接收信号频率; f_s为发射信号频率; v_s为源端节点移动速度; v_r为目的端节点移动速度; c为水中声速.考虑到洋流等外力的影响, 水下传感器节点位置是非固定的, 但各节点的运动有极强相关性, 所以可认为节点的相对位置固定, 即源端和目的端没有相对运动.
根据式(1)和式(2)的信道模型计算海洋哺乳动物的通信半径R₁、干扰半径R₂以及水面网关的通信半径R₃、干扰半径R₄.如图 2所示, 为了避免生物对网关通信的干扰, 需使生物的虚线部分与水面网关的实线部分没有交叠即两者距离需大于R₂+R₃; 同时还需避免网关对生物通信的干扰, 使两者距离大于R₁+R₄.因此d_inf=max{R₂+R₃, R₁+R₄}.以确定的MMGR位置为圆心, 以d_inf为半径的圆形区域即为生物-网关干扰区域MMIR, 在该区域中不布放水面网关.
图 2(Fig. 2)

图 2 生物-网关的干扰距离Fig.2 Interference distance between marine mammals and gateway

1.3 生物友好的水面网关部署策略该生物友好的水面网关部署是通过充分考虑海洋哺乳动物对水声传感器网络中水面网关布放位置的影响, 确定水面候选位置中水面网关的布放位置, 使其在满足网关数量、流量约束以及冲突约束的前提下, 最小化数据包端到端的延迟期望(minimizing expected end-to-end delay, MEED).所用符号定义如表 2所示.
表 2(Table 2)

表 2 符号表Table 2 Symbol table

符号	定义
U	水下传感器节点的集合
W	水面网关候选位置的集合
V	网络中所有点的集合:V=U∪W
C_u	在水下节点u的通信范围内的节点的集合
e	通信链路
E	所有可能的通信链路e的集合: E={e(u, v):u∈U, v∈C_u}
G	网络拓扑图:G=(V, E)
E_{out_u}	水下节点u的输出链路的集合: E_{out_u}={e(u, v):v∈C_u}?u∈U
E_{in_v}	流入节点v的链路的集合: E_{in_v}={e(u, v):e(u, v)∈E}?u∈U
τ	包的传输时间
h_u	在节点u处的包的平均生成速率, 即在数据包传输时间τ内生成的数据包的期望
H	整个网络的总的数据包生成速率
f(e)	在边e上每个包的时间的平均流
x_w	二进制变量:

表 2 符号表 Table 2 Symbol table

整个网络总的数据包生成速率H应该等于数据包到达水面虚拟汇聚点的到达率, 即在数据包传输时间τ内到达虚拟汇聚点的数据包的期望:

(4)

因此MEED问题就可以表示为

(5)

s. t.

(5a)

(5b)

(5c)

(5d)

式(5a)即限制水面网关的数量最多为N.式(5b)是水面候选位置处的流量约束, 即只能在水面网关布放点接收数据, 也就意味着当x_w=0时, 流入候选点t的总流量为0.式(5c)表示在任何节点发送和接收的总的数据传输速率不能超过通信链路的最大带宽B, 即对水下传感器来说,

, ?v∈V, 但是对于水面网关来说, 由于其不利用水声信道发送数据, 故其约束条件简化为

, ?w∈W.式(5d)表示对任意处于MMIG区域的水面候选位置来说, 都使其相应的x_w为0, 即不布置网关.
此外, 网络中每个节点处的流量符合流量守恒条件:对于水下传感器节点, 从一个节点流出的平均流量的总和与流入该节点的流量总和加上当前节点的数据生成速率的总和相等，即

, ?u∈U.并且网络节点符合端到端流量守恒:所有水下节点的总的数据生成速率等于由所有水面网关组成的虚拟汇聚点的总的数据吸收率, 因为由源节点产生的每个数据包最终都会被水面网关先接收再送至水面或者其他控制中心，即

.
由于对一个数据包来说, 端到端的延迟是其经过的从该数据包源节点到最终接收它的网关节点路径中每一跳的延迟总和.其中每一跳延迟都包含三部分:排队和数据存取延迟、发送延迟和传输延迟.
设P_uw为水下源节点u到生物-节点干扰区域外网关候选位置w所有可行路径的集合, 例如:p_i={e₁, e₂, …, e_m-1, e_m}是P_uw中的一条路径, 其中e₁, e₂, …, e_m-1, e_m是构成路径p_i的链路, 则p_i的端到端延迟τ_{p_i}为

(6)

则u到w的平均端到端的延迟为

(7)

其中f_{p_i}为通过路径p_i的从u到w的数据流速率，则在路径中每个链路的流量为

(8)

根据文献[4]得网络所有节点的端到端的延迟的期望为

(9)

即将相应的目标函数转化为

(10)

由于该网关部署问题可以看作是NP-hard问题, 因此对于一个空间范围较大的目标区域, 很难在多项式时间内找到一个最优解, 因此考虑使用贪婪-互换启发式算法解决该水面网关部署问题.在贪婪过程中, m个水面网关的近优解是在m-1个水面网关部署的基础上通过添加一个满足约束条件的网关，使目标即网络延迟期望最小而得到.
贪婪-互换启发式算法:
假设初始整形规划问题为L, 初始化L^*=L
For j=1, 2, …, m do:
Step 1:修改网关数量的约束条件即式(5a), 使其上限为j;
Step 2:与X^*相对应的每一个w∈W都有x_w^*=1, 将该条件加入到L^*中；
Step 3:重复以上步骤直到j=m；
Step 4:对每个满足x_w^*=1的节点, 使其依次与其他MMIR之外的x_w^*=0的节点w∈W交换, 取相应目标函数最小的节点作为解X^*；
Step 5:与X^*相对应的每一个w^*∈W都有x_w^*^* = 1, 对于之前的解w∈W都有x_w^*=0, 将该条件加入到L^*中；
Step 6:直到目标函数收敛, 即得到生物友好的水面网关的近优解.
首先是贪婪过程, 初始化后假设水面网关数目为1, 然后用整形规划的方法搜索得到候选位置中的最优解, 并将最优解处的网关部署状态变量更新；然后将网关数量增加至2, 再使用整形规划的方法从剩余的候选位置中搜寻第二个最优解, 使得目标函数最小, 将该位置的状态变量更新.按照该流程循环下去直到式(5)的约束条件不再成立, 即受到最大网关数量的限制时即得到一个近优解.最后为了提高算法质量, 在该近优解的基础上, 再次进行已选网关与未选水面候选位置的互换:对选出的水面网关与剩余的水面候选位置依次进行互换, 使得目标函数减小最多.对所有被选网关重复该过程, 使得目标函数收敛即不能再降低.
2 仿真与性能评价为验证EF-UGD的有效性, 通过实验从时间延迟和数据包投递率两个方面加以验证.最后将EF-UGD与随机选择网关位置的方法和DSGD方法进行对比.实验所用到的参数设置参考了Aqua-sent OFDM MODEM.
网络分布在6 km×6 km的方形水域中, 其中25个水面网关候选位置均匀分布在该方形水域中, 相邻候选位置水平和垂直距离都为1.5 km; 49个水下传感器节点均匀布放, 相邻传感器节点的水平和竖直距离都相距1 km，深度为100 m.其中数据包中用于数据检测和同步的前导部分在带宽为5 kbit/s时的传输时延为1 s，水声传播速度为1.5 km/s，数据包生成率为1个/s，数据包长为200 B.海洋哺乳动物与水面网关候选位置共存并随机分布在该区域中, 根据水生哺乳动物位置选取水声干扰区域MMIR.
图 3是在没有生物干扰和有生物干扰的情形下, 带宽为5kbit/s时，使用3种不同的水面网关部署算法模拟得到的平均网络时延.从图 3a中可以看出, 无生物干扰且部署的网关数目较少时，对于网络平均时延, EF-UGD算法比随机选点算法和DSGD算法有一定幅度的降低，例如在网关数目为5时, 分别降低了25%和19%.但是随着网关数目的增加, 网络时延降低速度变缓至最终不变.这是因为当网关数达到一定量时, EF-UGD所选出的水面候选位置已满足与所有水下节点的最短距离通信, 此后随着网关数目的增加, 网络时延不再减小, 最终达到一稳定值.但是EF-UGD的收敛速度较快, 因此在达到目标时延时网关数目相对较少.从图 3b中可以看出, 有生物干扰时, EF-UGD的网络平均时延相比随机选点算法和DSGD算法分别降低25%和19%.对比图 3a和3b中网关数目为10的情形, 随机选点算法、DSGD算法以及EF-UGD算法的网络时延, 由于生物干扰分别增加0.32, 0.42和0.05 s, 可以看出生物干扰对EF-UGD的影响相对较小.
图 3(Fig. 3)

图 3 网络平均时延(B=5 kbit/s)Fig.3 Network average delay (B=5 kbit/s) (a)—无生物干扰；(b)—有生物干扰.

图 3、图 4模拟了在有生物干扰和无生物干扰情况下带宽分别为5 kbit/s和10 kbit/s时网关数目的变化对整体网络平均时延的影响.对图中给出的时延曲线进行分析, 带宽增加使得布置相同数目的网关时整个网络的平均时延有较大的降低, 对比EF-UGD不同带宽的时延变化:当网关数目增加到一定程度后, 带宽为10 kbit/s的网络时延比5 kbit/s时降低了55%.这是因为带宽的增加使得数据包的发送速率增加，从而使数据包经过每一跳转发时的发送时延降低, 因此使得网络平均时延降低.此外，对于相同的网络平均时延, 需要的网关数目随着带宽的减小而增加.这是因为对于同一网络, 带宽的降低导致总数据生成率与带宽的比率增大, 使得水面网关因此接近饱和状态, 从而需要更多的网关来处理额外的数据包.例如当B=10 kbit/s时, 仅仅通过增加3个水面网关就可以使网络的平均时延由单网关时的2.99 s降低到1.32 s，即降低了56%.因此提高网络时延性能可以通过增加水声信道带宽和增加网关数目的方法实现.
图 4(Fig. 4)

图 4 网络平均时延(B=10 kbit/s)Fig.4 Network average delay (B=10 kbit/s) (a)—无生物干扰；(b)—有生物干扰.

图 5是模拟B=5 kbit/s且有生物干扰时, 使用三种不同水面网关部署算法的数据包投递率.由图可以看出，EF-UGD算法明显优于其他两种算法, 当网关数目达到一定量时, 数据包投递率比DSGD算法和随机选点算法分别提高19%和36%.这是由于哺乳动物发声对网络数据包的传输产生了干扰, 从而增加随机选点算法和DSGD算法的数据包错误传输率, 使其端到端路径不可达.而考虑到生物干扰区域的EF-UGD算法使得网络的端到端路径较少受到生物水声干扰的影响, 从而较大提高了数据包投递率.
图 5(Fig. 5)

图 5 数据包投递率Fig.5 Packet delivery ratio

3 结语针对海洋哺乳动物与水面网关在UASNs中和谐共存的问题, 为减小UASNs间水声通信与海洋哺乳动物间水声通信的相互干扰, 通过确定水生哺乳动物的水声干扰范围, 结合生物干扰约束、网关数目约束以及网络各链路的流量约束, 提出一种生物友好的水声网络多网关部署优化策略, 实现了端到端数据包的高效传输.仿真实验结果表明, 采用本文提出的EF-UGD方法能有效降低网络端到端传输的平均时延，有效提高网络数据包的投递率.
参考文献

[1]	Liu J, Wang Z, Peng Z, et al.SUAVE: swarm underwater autonomous vehicle localization[C]// Proceedings of the 2014 IEEE Conference on Computer Communications.Piscataway: IEEE, 2014: 64-72.http://www.researchgate.net/publication/271473025_Suave_Swarm_underwater_autonomous_vehicle_localization
[2]	Gravalos I, Makris P, Christodoulopoulos K, et al.Efficient gateways placement for Internet of things with QoS constraints [C]// Proceedings of the 2016 IEEE Global Communications Conference.Piscataway: IEEE, 2016: 1-6.http://ieeexplore.ieee.org/abstract/document/7841780/
[3]	Misra S, Hong S D, Xue G, et al. Constrained relay node placement in wireless sensor networks:formulation and approximations[J].IEEE/ACM Transactions on Networking, 2010, 18(2): 434–47.DOI:10.1109/TNET.2009.2033273
[4]	Ibrahim S, Liu J, Al-Bzoor M, et al. Towards efficient dynamic surface gateway deployment for underwater network[J].Ad Hoc Networks, 2013, 11(8): 2301–2312.DOI:10.1016/j.adhoc.2013.05.011
[5]	杨武夷, 孙馨喆, 张宇, 等. 一种宽吻海豚通讯信号自动分类的方法[J].声学学报, 2016, 41(2): 181–188. ( Yang Wu-yi, Sun Xin-zhe, Zhang Yu, et al. An automatic classification method for whistles of bottlenose dolphin(tursiops truncates)[J].Acta Acustica, 2016, 41(2): 181–188.)
[6]	Yao G, Jin Z, Su Y.An environment-friendly spectrum decision strategy for underwater wireless sensor networks [C]// Proceeding of the 2015 IEEE International Conference on Signal Processing for Communications.Piscataway: IEEE, 2015: 6370-6375.http://dx.doi.org/10.1109/ICC.2015.7249339
[7]	徐久强, 李鹤群, 王进法, 等. 基于边权与节点负载的路由策略研究[J].东北大学学报(自然科学版), 2015, 36(12): 1691–1695. ( Xu Jiu-qiang, Li He-qun, Wang Jin-fa, et al. Research on routing strategy based on edge weight and load[J].Journal of Northeastern University (Natural Science), 2015, 36(12): 1691–1695.)
[8]	Karczmarski L, Cockcroft V G, Mclachlan A. Habitat use and preferences of Indo-Pacific humpback dolphins sousa chinensis in Algoa Bay, South Africa[J].Marine Mammal Science, 2000, 16(1): 65–79.DOI:10.1111/mms.2000.16.issue-1