无线电监测站部署效率评估与优化方法研究*

徐 英,周尚武,丁 锋

(1.国防科技大学电子对抗学院,合肥 230037;2.安徽新华学院,合肥 230088)

无线电监测往往需要多个监测传感器(以下简称监测站)组成监测网络[1],以实现对监测区域或目标的最大化覆盖。用最少的监测站实现最大的监测覆盖率,即,实现监测站部署的最优化规划,是提高节点部署效率和延长网络生命周期的前提。对监测站部署优化需要解决两个方面的问题,一是优化算法,二是部署效率评估。传统的无线电监测网络规划[2-3]主要从选址原则、标准、周边环境等方面考虑[4],没有考虑监测站部署效率优化问题。陈升来、刘旭、胡进辉等分别通过遗传算法[5-10]、遗传编程[11]、模拟退火遗传[12]等算法解决无线电监测网络规划的监测站优化部署问题,利用适应度函数评估种群中每个个体解决目标问题的能力,得到的优化部署结果与染色体数目和循环次数有较大关系,运算量大,且单纯以覆盖率作为指标容易出现重复率过大的问题。

针对无线电监测站分布式部署优化存在的不足,构建对无线电监测网络协同监测部署效率评估指标体系,基于空间二次聚类算法进行优化部署,实现部署效率的量化评估和最优化部署,并通过仿真实验验证了算法的有效性和实用性。

1 监测传感器网络部署效率指标体系

对监测站部署效率的评估是对多个监测站协同监测[13-14]的部署效率进行综合评估[15],需要考虑监测覆盖率、传感器数量、监测重复率等多方面的影响因素,评估指标体系可分解为如图1所示。

图1 监测传感器网络监测效率评估指标体系分解图

①协同监测覆盖率

监测站部署优化的目的是用最少的监测站实现最大的监测覆盖率。对于区域监测[16],假设已知单个监测站的监测覆盖范围,对应的监测区域为Mi,由于不同监测站的监测区域可能会有重合,多个监测站协同监测区域定义为所有监测站可监测区域的并集集合,则协同监测覆盖率H由下式确定:

(1)

式中:i=1,2,…,k,k为部署的监测站个数,X为监测任务区域,Area(·)为区域面积。

对于点目标监测,假设第i个监测站的可监测目标集Pi={p1,p2,……,pNi},共有目标Ni个,不同监测站可以监测的目标可能会有重合,因此多个监测站协同监测目标集定义为所有监测站可监测目标集的并集集合,则协同监测覆盖率H由下式确定:

(2)

式中:i=1,2,…,k,k为部署的监测站个数,W为监测任务目标集合,Count(·)为目标集合中的目标数。

②协同监测重复率

为了提高监测站的利用率,应尽量避免不同监测站的监测区域或监测目标之间有较大的重合,即要求协同监测的重复率较小。对于区域监测,多个监测站协同监测重复区域为所有监测站可监测区域的交集集合,则定义协同监测的重复率为协同监测重复区域和协同监测区域的比值,由下式计算得到:

(3)

对于点目标检测,多个监测站协同监测重复目标集为所有监测站可监测目标集的交集集合,则定义协同监测重复率为协同监测重复目标数和协同监测目标数的比值:

(4)

2 基于空间二次聚类的监测站优化部署算法

无线电监测站部署优化的根本思想是求出一组最优的监测站站址分布方案,用最小的成本(即最少的监测站)来实现设定的协同监测覆盖率,达成监测站的最优化部署。

设有空间要素集合F={f1(x1,y1),f2(x2,y2),…,fn(xn,yn)}(n≥2),其中fi(xi,yi)表示发射站i的空间位置二维坐标向量,fi到fj(1≤i,j≤n)的空间距离为Disfij,定义为:

(5)

假设监测站在各个方向的监测距离相同,取监测距离R作为阈值。当若干个空间要素的空间距离接近,且分布在同一个半径为R的圆内时,可划分为同一类簇。取簇内所有空间要素的外接矩形的中心作为圆心,获得一次聚类中心。

经过一次聚类后,不同簇内的点仍有可能在同一个半径为R的圆内,此时,依据簇中心与外接矩形点的位置关系,对一次聚类结果进行二次聚类,即取一次聚类的簇中心作为二次聚类的空间要素,阈值取为2R,簇中心满足聚类条件且两簇的最远点距离小于2R的相邻簇,则合并为一个簇。

设一次聚类获得m个类簇,各簇中心分别为(X1,Y1),(X2,Y2),…,(Xm,Ym),第k个簇中所有空间要素的外接矩形的4个顶点坐标分别为(minxk,minyk)、(maxxk,minyk)、(minxk,maxyk)和(maxxk,maxyk),则将第k个簇和第p个簇二次聚类为同一类簇的约束条件如下:

条件1:

Dis[(Xk,Yk),(Xp,Yp)]<2R
Dis[(minxk,minyk),(maxxp,maxyp)]<2R
Dis[(maxxk,maxyk),(minxp,minyp)]<2R

(6)

条件2:

Dis[(minxk,minyk),(Xp,Yp)]<2R
Dis[(minxk,maxyk),(Xp,Yp)]<2R

(7)

条件3:

Dis[(maxxk,maxyk),(Xp,Yp)<2R]
Dis[(maxxk,minyk),(Xp,Yp)]<2R

(8)

条件4:

Dis[(Xk,Yk),(minxp,minyp)]<2R
Dis[(Xk,Yk),(minxp,maxyp)]<2R

(9)

条件5:

Dis[(Xk,Yk),(maxxp,maxyp)]<2R
Dis[(Xk,Yk),(maxxp,minyp)]<2R

(10)

当上述条件1～5同时满足时,将两个簇聚类为一个簇。以二次聚类中心为监测站站址,可以实现对发射站目标的全覆盖监测。

二次聚类结果可能出现监测目标集合重复或包含的情况,可根据需要设置重复率约束条件,并对存在空间点集重合包含关系的簇进行合并。

3 试验仿真

选取文献[11]中的实验数据进行仿真试验,参数设置如下:

覆盖范围:(x,y)∈(0≤x≤127,0≤y≤127);

发射站坐标:(1,10),(25,106),(10,45),(78,83),(65,44),(111,90),(78,23),(96,39),(77,102),(36,43)共10个发射站;

监测站覆盖半径:25。

图2 文献[11]中的结果

文献[11]采用遗传编程算法进行优化部署,条件是用最少的监测站实现针对发射站90%以上的覆盖率,即用最少的监测站覆盖9个或者9个以上发射站。通过二进制编码、选择复制、交换和变异等操作,循环若干次后得到最佳监测站坐标列表。其仿真结果显示,循环21次后得到的最佳方案中监测站数目为6个,如图1[11],监测目标覆盖率为90%,重复率为10%。然而,通过对此例的进一步仿真实验发现,采用遗传算法的优化部署结果与染色体数目和循环次数有较大关系,且单纯以覆盖率作为指标容易出现重复率过大的问题,如果要获得较为优化的方案,需要增加染色体数目和循环次数。比如,在本例中,通过增加随机染色体数目和循环次数,并设置重复率约束条件,可以进一步得到更少监测站、更高覆盖率的更优化部署,图2中所示的最佳监测站数目为4个,监测目标覆盖率为100%,重复率为0。但是,增加随机染色体数目和循环次数会极大地增加算法运算时间,限制了这种方法的实用性和可行性。图1和图2中“+”为监测站部署位置,“·”为发射站站址,圆周范围为监测站可覆盖监测的范围。

以监测目标全覆盖(发射站覆盖率为100%)为条件,利用本文方法进行监测站优化部署的步骤如下:

①对发射站进行一次空间聚类,得到聚类结果,如图3,图中“·”表示发射站位置,圆周范围为以一次聚类中心为圆心、监测距离R为半径的监测范围,此时的监测目标覆盖率为100%,但是监测目标重复率为10%,监测站数目为8个,且监测站的监测区域有较多重叠,存在监测站冗余;

图3 增加循环次数和重复率约束条件得到的结果

②对步骤①的结果进行二次聚类,当两个簇同时满足二次聚类约束条件1～5时,将这两个簇二次聚类为一个簇,结果如图4,图中”+”为二次聚类中心,圆周为以二次聚类中心为圆心、监测距离R为半径的圆,此时的监测目标覆盖率为100%,重复率为0,监测站数目为4个;

图4 一次聚类结果

图5 二次聚类结果

③对存在空间点集重合或包含关系的簇进行合并。

为了验证算法的有效性和适用性,进一步增加发射站点数,进行监测站部署方案优化。增加发射站坐标分别为:(50,80),(105,72),(44,66),(8,60),(88,10),优化部署结果如图5所示。

图6 增加发射站点后的优化部署结果

4 结论

对无线电监测传感器网络节点进行部署优化可以有效提高监测效率。基于监测传感器网络部署效率指标评估和空间二次聚类方法的监测站部署优化算法,综合考虑了监测站数量和监测覆盖率、重复率等相关指标,通过约束条件的设置,兼顾监测覆盖效果和部署效率,与遗传算法相比,运算量大大降低,且用更少数量的监测站和更小的监测重复率实现了更大的监测覆盖率,即获得的部署方案效率更高、更优化。