水下传感器网络覆盖优化算法*
2014-07-11姜卫东刘胤祥
郭 勇 姜卫东 刘胤祥
(海军指挥学院信息系 南京 211800)
1 引言
水下传感器网络部署分为确定部署和随机部署,随机部署存在网络节点分布不均,覆盖率低等问题。而目前针对水下传感器网络随机部署后的覆盖优化问题研究并不多,由于水下传感器网络是无线传感器网络在水下的延伸[4],可借鉴无线传感器网络对该问题展开研究。针对无线传感器网络覆盖,林祝亮[5]提出了基于概率测量模型的粒子群优化策略,以网络有效覆盖率为优化目标,通过粒子群算法实现有效覆盖;贾杰[6]针对传感器节点密度高的特点,研究了工作节点集选取问题,提出了基于加权遗传算法和基于约束遗传算法的优化覆盖机制,延长了网络生存时间;王蕊[7]针对由少量移动节点和固定节点组成的无线传感器网络提出了一种基于鱼群算法的优化部署方案,该方案以网络覆盖率为目标函数,将移动节点的位置迁移过程抽象为人工鱼的追尾和觅食行为,并在人工鱼的状态更新过程中加入虚拟力影响因子来引导人工鱼的游动方向,有效提高了网络覆盖率,优化了网络性能。
2 模型描述
本文考虑在边长为L的正方形区域部署N个传感器节点组成一个二维水声网络,其中N1个固定节点,N2个移动节点。在实际的军事或工程应用中固定节点可由固定水声站或锚节点水声器充当;移动节点可由水下AUV担任。在监测区域外围部署汇聚节点进行覆盖优化计算并将结果发送给移动节点,移动节点按照指令移动到指定位置,从而优化网络部署,提高网络覆盖率。
2.1 网络模型
1)传感器节点采用布尔感知模型[8],每个节点抽象为一个点,具有相同的感知半径Rs;
2)网络初始化时,所有节点分布在(0,0)~(L,L)的正方形区域范围内,每个传感器节点位置已知,且能感知周围节点位置;
3)监测区域之外的汇聚节点能量不受限制,可与传感器节点进行直接或间接通信;
4)为降低能耗,在算法执行中,传感器节点不移动,只在优化算法结束后才移动到最终位置。
2.2 人工鱼群算法网络覆盖优化模型
设当前网络中传感器节点矢量为Z=[,,…,,…,]T(i∈[1,N])。其中Psi为第i个传感器节点,其位置为(xi,yi)。
类风湿关节炎是一种自身免疫性、以炎症细胞因子浸润和慢性炎症反应的疾病。RA临床表现为关节慢性炎症浸润、关节疼痛、关节肿大和畸形。及早诊断类风湿关节炎和抑制炎症反应对类风湿关节炎治疗和预后至关重要[10-11]。本论文中,我们发现P2X7受体在类风湿关节炎患者滑膜组织中高表达,且对类风湿关节炎具有较好的诊断价值。此外,P2X7受体与炎症细胞因子密切相关,抑制P2X7受体的表达可抑制关节滑膜细胞的炎症细胞因子分泌和炎症反应,表明P2X7受体不仅是类风湿关节炎的诊断标志物,也是治疗类风湿关节炎的潜在靶点。
初始化生成M条人工鱼Z1,Z2,…,Zj,…,ZM(j∈[1,M]),每条人工鱼都有N个传感器节点分布在监测区域内,其中Zj=[,,…,,…,PsjN]T(i∈[1,N],j∈[1,M]),既表示人工鱼又表示人工鱼状态。为简化处理,假设第j条人工鱼Zj中第i个传感器sji为Zj中到当前传感器网络中第i个传感器si最近的传感器节点。设T为当前传感器节点对监测区域的覆盖率,则Tj(j∈[1,M])为第j条人工鱼对监测区域覆盖率。
定义两条人工鱼Za和Zb(a,b∈[1,M],a≠b)的距离为
人工鱼的一些其他参数不作详细介绍,只将其简述如下:Visual为人工鱼的感知视野,λ为人工鱼的步长,δ为人工鱼的拥挤度因子。设置公告板,记录最优目标函数值Tk和最优人工鱼Zk。
3 水下传感器网络覆盖优化
3.1 改进全局人工鱼行为在覆盖率优化中的描述
鱼群算法是一种群智能优化算法[9~10],江铭炎[11]在人工鱼搜索过程中加入最优人工鱼信息来加速人工鱼寻优的收敛速度,即全局人工鱼群算法。然而其向最优人工鱼移动的比例是一定的,不能根据情况动态变化,寻优速度和精度受限,针对以上问题,本文在人工鱼行为中引入权重系数,加速算法收敛。改进的追尾行为描述如下:
设人工鱼i当前状态为Zi,目标函数值为Ti。探索其当前邻域内d(d<Visual)目标函数值Tj最大的伙伴Zj,Zj邻域内伙伴数为nf。若Tj/nf>δTi,则人工鱼i朝伙伴Zj和最优人工鱼Zk方向移动一步:
Random(0,λ)是一个在(0,λ)之间随机分布的2N维向量,c是权重系数,是向最优人工鱼靠拢的比例,若人工鱼i离最优人工鱼较远,则c较大,向最优人工鱼移动较多,加速算法收敛;若人工鱼i离最优工鱼较近,则c较小,向最优人工鱼移动较少,在目标人工鱼附近寻优。若不满足条件则执行聚群行为,聚群、觅食行为的权重系数引入方法和追尾行为类似,此处不再赘述,随机行为与鱼群算法一样。
每次行动完毕后,人工鱼将自己的目标函数值与公告板比较,若好于公告板,则更新公告板中的最优目标函数值Tk和最优人工鱼Zk。
3.2 步长变化公式
人工鱼群算法虽然有很多优点,但也存在后期收敛慢,寻优精度不高等缺陷,这是由于人工鱼的步长是固定值,随着目标函数值的升高,固定步长使得人工鱼在最优值附近震荡,无法到达最优值。
为了克服以上缺点,引入可变步长[12]。随着目标函数值的升高,动态地缩小步长,提高搜索精度,步长调整公式为
T是当前最优目标函数值,Tset是设定的目标函数值,λmin是最小步长。随着当前最优目标函数值的升高,步长慢慢变小,人工鱼寻优精度提高。
3.3 改进全局人工鱼群算法对网络覆盖优化步骤
根据上述改进算法,对水下传感器网络的覆盖率优化步骤如下:
1)初始化M条人工鱼,每条人工鱼都有N个传感器节点的位置坐标;
2)设置覆盖率目标值Tset、运算轮数n、人工鱼步长、最小步长等参数,并将第一条人工鱼设为最优人工鱼Zk;
3)按照条件执行改进全局人工鱼群算法的追尾、聚群、觅食和随机等行为,并按照式(4)更改步长;
4)检查执行后的覆盖率是否提高,若提高则更新最优目标函数值和最优人工鱼;
5)若达到覆盖率目标值或者超出设置轮数,则执行步骤6),否则执行步骤3);
6)输出最优覆盖率和最优人工鱼。
4 实验仿真
为验证改进全局人工鱼群算法对水下传感器网络的覆盖优化性能,将其与遗传算法和鱼群算法进行了对比实验,实验参数如表1所示。
表1 改进全局人工鱼群和鱼群算法的实验参数
图1 三种算法覆盖率对比图
由于传感器初始分布具有一定的随机性,所以分别对三种算法进行了50次仿真,图1为覆盖率平均值与轮数的关系。图2~图5为初始时和三种算法优化后的一次传感器分布,其中实心圆代表固定传感器及其感知范围,空心圆代表移动传感器及其感知范围。
图2 初始随机网络分布
图3 遗传优化网络分布
图4 鱼群优化网络分布
图5 改进全局鱼群优化网络分布
从图1可以看出,初始时,15个固定节点和35个移动节点组成的网络覆盖率为55%左右,随着轮数的增加,遗传算法、鱼群算法和改进的全局人工鱼群算法50轮优化后的网络平均覆盖率依次为71.92%、78.47%和85.75%,改进全局人工鱼群算法优化后的覆盖率要高于其他两种算法,且收敛较快。由图2~图5可知,随机部署后传感器分布不均匀,有很大区域未被传感器覆盖,遗传算法和鱼群算法优化后都有部分覆盖盲区,而全局人工鱼群算法优化后传感器覆盖盲区较小。可见,改进全局人工鱼群算法在水下传感器网络覆盖优化方面具有覆盖率高和节点分布均匀等优点。
5 结语
本文将全局人工鱼群算法应用到水下传感器网络覆盖优化问题中,在鱼群算法的四种行为中加入了按一定比例向最优人工鱼移动的过程,并根据覆盖率动态改变人工鱼步长。实验结果表明,改进的全局人工鱼群算法较遗传算法和鱼群算法在水下传感器网络覆盖优化中网络覆盖率高、优化速度快,能有效提升网络性能。
[1]Dario Pompili.Efficient Communication Protocols For Underwater Acoustic Sensor Networks[D].Atlanta:Georgia Institute of Technology,2007.
[2]李淑秋,李启虎,张春华.水下声学传感器网络的发展和应用[J].声纳技术及应用专题,2006,35(11):945-952.
[3]郭忠文,罗汉江,洪锋.水下无线传感器网络的研究进展[J].计算机研究与发展,2010,47(3):377-389.
[4]王长生.水下传感器网络节点布置方法研究[D].合肥:合肥工业大学,2011.
[5]林祝亮,冯远静.基于粒子群算法的无线传感器网络覆盖优化策略[J].计算机仿真,2009,26(4):190-193.
[6]贾杰,陈剑,常桂然.无线传感器网络中基于遗传算法的优化覆盖机制[J].控制与决策,2007,22(11):1289-1292.
[7]王蕊,刘国枝.基于鱼群优化算法的无线传感器网络部署[J].振动与冲击,2009,28(2):8-11.
[8]周利民,杨科华,周攀.基于鱼群算法的无线传感器网络覆盖优化策略[J].计算机应用研究,2010,27(6):2276-2279.
[9]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.
[10]李晓磊,钱积新.基于分解协调的人工鱼群优化算法[J].电路与系统学报,2003,8(1):1-6.
[11]江铭炎,袁东风.人工鱼群算法及其应用[M].北京:科学出版社,2012:110-111.
[12]王联国,洪毅,施秋红.全局版人工鱼算法[J].系统仿真学报,2009,21(23):7483-7486.