李敬伟,赵开新,2,梁 娟,2
(1.河南工学院 计算机科学与技术学院,河南 新乡 453003;2.河南省生产制造物联大数据工程技术研究中心,河南 新乡 453003)
无线网络已经覆盖了人们生活的各个方面,无线网络空间覆盖规划在移动网络的建设中起着越来越重要的作用[1-3]。在有效的投资条件下,合理建站、提高用户满意度是无线网络空间覆盖规划的最低要求,但传统的覆盖规划存在着测试工作量繁重、测试成本较高、用户体验较差等问题。目前,国内外在无线网络空间覆盖规划方面做了很多研究。在国内,朱晓荣等人提出了一种RPMA低功耗广域网网络规划方法[4],该方法有效改善了无线网络覆盖规划测试成本高的问题,但是该方法存在着网络节点散布不均匀、覆盖率不高、存在覆盖盲区等问题。王振东等人提出了一种基于改进差分进化方法的无线传感器网络覆盖优化方法[5],该方法虽然提高了无线网络的覆盖性能,但存在着不能深度覆盖、方法复杂、信号覆盖质量差等问题。在国外,Pathmakumar等人提出了一种基于爆破机器人运动轨迹的最优无线网络空间深度覆盖规划模型[6],该模型选择爆破臂的扫掠角作为爆破机器人的运动轨迹,利用基于多目标优化的扫掠角计算框架结合遗传算法计算爆破机器人的最优运动轨迹,使爆破时间和爆破能量能同时达到最小化。目前该模型已经通过了多次仿真实验的有效性验证,并且在特种行业爆破作业时开始使用。Vazquez-Carmona等人提出了一种基于无人机运动轨迹的无线网络空间深度覆盖路径规划模型[7],该模型控制无人机在指定目标区域内进行作业,避免了无人机超出目标区域带来的一系列不可预测的问题。上述研究虽然在无线网络空间覆盖规划方面都取得了一定的进展,但都存在着网络节点覆盖质量不高的问题。
本文提出了一种新的无线网络空间深度覆盖规划方法,该方法首先利用基于K-means聚类算法来挖掘无线网络空间深度覆盖规划特征,并根据数据特征将数据集中相似的数据划分到同一簇,然后构建递阶层次结构模型,依据该模型通过层次分析法得到无线网络空间深度覆盖性评估结果,并判定影响覆盖性的重要因素。最后采用基于文化蚁群算法(Memetic Ant Colony Algorithm, MACA)的无线网络空间深度覆盖规划方法进行编码和解码以及寻优更新等操作,以有效提高无线网络空间中各网络节点的覆盖质量。
1.1 无线网络空间深度覆盖规划特征
K-means聚类算法应用广泛,它可根据数据特征将数据集中相似的数据划分到同一簇,簇的个数K由用户指定。在无线网络空间深度覆盖规划应用中,K-means聚类算法首先根据距离来度量无线网络空间中不同数据实例的相似程度,并且把距离相近的数据实例划分到同一簇。然后,通过无线传感器网络收集数据实例。无线传感器网络主要由传感器节点、远程客户端和基站组成,各个传感器节点负责收集数据实例。传感器节点收集数据实例后,先传送给基站,再由基站上传到远程客户端文件系统中。最后,选取K个数据实例作为初始聚类中心形成K个初始的聚类,再将其余数据实例根据与初始聚类中心的距离划分到不同的聚类中形成新的聚类,并根据各聚类的最新结果重新定义各聚类的中心,这样依次迭代一直到所有数据实例都划分到不同的聚类中,最终获得的各个聚类即为无线网络空间深度覆盖规划特征,使用此规划特征可以增强聚类结果的稳定性。在获得无线网络空间深度覆盖规划特征的过程中,全局变量起着重要作用。全局变量为客户端文件系统中某个文件中的k个聚类中心点,这k个聚类中心点由初始化聚类中心点k个样本不断迭代形成。在文件系统中设置一个监听线程和一个处理线程,它们之间利用消息队列协同工作,使得文件系统内的信息处理不会相互影响,数据能够正确处理,各聚类之间的通信安全得到保障,从而提高了无线网络空间深度覆盖规划的质量。其中聚类样本数据集为:
(1)
式中,da表示聚类中心值。
聚类样本数据集详细规划步骤如下:
步骤一:用di=(di1,di2,…,din)与dj=(dj1,dj2,…,din)描述数据集的随意两个n维向量。
步骤二:用O(di,dj)表示数据样本中心:
(2)
步骤三:样本点n的组合数除以全部样本点两两距离总和,获得样本点间的平均距离,该平均距离用Paverg表达,如式(3)所示:
(3)
式中,cn表示样本点总数量。
选取初始聚类中心方法的具体步骤如下:
步骤一:输入终止条件、聚类个数、矩阵、集合和聚类中心集合。
步骤二:输出k个初始聚类中心,获得k个初始聚类中心后,判断输出的条件是达到终止条件。
步骤三:(1)将经求解获取的样本点间的距离Ddist(di,dj)保存在矩阵里。(2)初始化集合保存最小距离样本点,聚类中心中保存第一个初始的聚类中心。(3)聚类中心保存矩阵次小距离的样本点中心,计算第三距离小的样本点并反复推算(3)。(4)直至聚类中心获得k个初始聚类中心。
通过上述过程得到无线网络空间深度覆盖规划特征,不仅减少了迭代次数、加快了无线网络的初始化速度,还解决了极值影响无线网络整体生命周期的问题。
1.2 无线网络空间深度覆盖评估方法
依据无线网络空间深度覆盖规划特征,首先构建递阶层次结构模型,然后使用层次分析法得到无线网络空间深度覆盖性的评估结果,最后再依据评估结果来判定影响覆盖性的重要因素。
递阶层次结构模型包括目标层、准则层、指标层和方案层,这四层按照从上至下的顺序进行排列。目标层用于判断无线网络空间深度覆盖性能优劣;准则层具有影响目标层的作用[8],包含覆盖重数、覆盖时间两部分,覆盖重数包括N重覆盖时长、平均N重覆盖面积百分比以及最大覆盖重数三个指标,覆盖时间包括有效覆盖时间百分比、平均响应时间、N重练习覆盖时长以及间隙时长百分比四个指标;指标层由覆盖重数和覆盖时间中的七个指标构成;最终选择的深度覆盖方案被视为方案层。基于上述递阶层次结构,构建判断矩阵A-B,该矩阵根据目标层A判断准则层B中各种指标的重要性。指标层C中的N重覆盖时长、面积百分比以及最大覆盖重数可评判准则层B中的覆盖重数,剖析指标层C中的全部指标结果,与准则层B中各指标值的结果比较各指标极值,并进行归一化处理。指标值归一化处理采用极值法,如式(4)所示:
(4)
式中,t表示指标值归一化处理所需时间,T表示需要指标值归一化处理的数据总量。利用极值法建立无线网络空间深度覆盖评估平台,选取合理的指标值归一化处理后的结果值作为评估平台每个评估节点的初始中心,将剩余数据分成最接近归一化处理结果值的若干个聚类。然后通过包括底层指标评价值与总排序权重的函数进行计算,最后可以得到无线网络空间深度覆盖性能评估结果。
1.3 构建无线网络空间深度覆盖规划模型
依据所得的无线网络空间深度覆盖性能评估结果,构建无线网络空间深度覆盖规划模型。无线网络空间深度覆盖规划模型如式(5)所示:
(5)
采用MACA对无线网络空间深度覆盖规划模型进行优化。
2.1 MACA
蚁群算法(Ant Colony Optimization, ACO) 是一种仿生学算法,该算法能够在图中寻找两点之间的最优路径,又被称为蚂蚁算法。ACO是受蚂蚁觅食行为启发得到的一种算法,蚂蚁在觅食过程中,总能根据自己的需要找到一条从蚁巢和食物源的最佳路径。文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的一种算法。
MACA是一种在ACO中输入文化基因算法的新算法[12],它由一群非智能体或轻度智能体通过相互协作来完成智能行为,为解决复杂问题提供了新的可能。在MACA中,为获得最优路径,每个智能体均需要依据信息素矩阵规划最佳路径,信息素矩阵是多个智能体运动过程和信息素更新过程中产生的矩阵。MACA的具体步骤如下:
步骤一:每个智能体基于信息素矩阵进行路径搜索,完成搜索后进行局部信息素更新。
步骤二:为增强MACA的寻优能力,需构建优化结构。所有智能体完成路径搜索后,选出n个精英智能体,引入文化基因的框架进行智能体与智能体之间的相互竞争和协作,以智能体的独立寻优和种群的信息交流为优化框架,进一步提升算法的寻优能力。
步骤三:智能体进化完成后,对全局信息素矩阵进行更新,智能体与种群通过信息素矩阵进行协作,最终实现协同进化。
2.2 无线网络空间深度覆盖规划模型的优化
基于MACA的无线网络空间深度覆盖规划模型优化方法包括编码和解码、初始化种群方位、路径搜索、改进信息素矩阵、个体协同竞争以及寻优更新六个步骤。
步骤一:编码和解码。编码前首先要标记好规划区域内各节点的序号,然后按照距指定聚类中心节点的长短依次进行编码。解码按照就近选择的原理将接收到的符号还原成相对应的编码信息,从而确定解码方案[13]。
步骤二:初始化种群方位。在不同方位的起点放置m个智能体,使种群的种类变多,为了使全部路径初始节点上都有智能体,初始节点数n少于智能体个数m,在不相同的n个节点上重复安放n个智能体。
步骤三:路径搜索。通过信息素矩阵和启发式矩阵完成路径搜索。在路径搜索过程中,首先使用禁忌搜索策略进行局部搜索,并使用贪婪策略访问节点。信息素矩阵用τ描述;启发式矩阵用HE描述,信息素的相对重要性用α描述;启发信息相对重要性用β描述,随机性及确定性因素随着α、β的升高而增强。
步骤四:改进信息素矩阵。改进当前信息素矩阵以获得智能体最优路径的前提是构建第N代智能体运动路径[14],信息素矩阵由每个智能体运动过程中所释放的信息素组成。信息素矩阵每次改进都会根据智能体不同的运动路径选择不同的信息素形成新的信息素矩阵。
步骤五:个体协同竞争。为实现交叉及变异操作,首先进行局部搜索,在进行局部搜索操作前,需要从排列好的智能体中挑选出个精英智能体,这些智能体的排列顺序由适应度函数F确定。为使下一代继承上一代优秀基因,原始的精英智能体将被经过遗传和优化操作后的更加优秀的智能体取代;反之,遗传操作前的智能体基因将被保留[15]。
步骤六:寻优更新。输出最优规划模型,无线网络空间深度覆盖规划模型必须达到最大更新代数的要求,当不能达到最大更新代数时,将禁忌搜索表清除,再次回到步骤二,进而不断完成寻优更新直至达到最大更新代数的要求。至此,无线网络空间深度覆盖规划过程全部结束。
为了验证本文所提出方法的可行性和可靠性, 通过Matlab 2015b进行仿真实验。仿真实验的模拟对象为某市Y区，该区包含大型商场和居民区及学校，业态丰富但无线网络空间覆盖质量不高，深度覆盖问题与日俱增，属于价值大、风险高、需要重点监视的区域。仿真实验中的监视区情景如图1所示：
图1 仿真模型中的监视区情景
图1中，黑色矩形区域为重点监视区，黑色圆柱形物体为障碍物，监视区内各网络节点的规格相同，各节点拥有相同的视角、有效视距和通信半径，整个监视区以m为单位来度量。
3.1 覆盖规划仿真效果展示
图2—4分别为应用MACA迭代至第0代、400代及800代时获取的覆盖规划网络节点分布情况，60个节点被随机分布在监视区中，但不能确保所有节点都能进行有效通信。
图2 仿真模型中的网络节点分布(第0代)
由图2可知，某些节点的感知范围出现重叠现象，且有部分节点不在有效通信半径范围内，这部分不在有效通信半径范围内的节点为孤立节点，无法接入网络。
图3是迭代至第400代的网络节点分布情况。由图3可知，所有的孤立节点已全部消失，符合全部节点入网条件，且所有节点均能有效绕过障碍物，无线网络空间深度覆盖率明显提高。
图3 仿真模型中的网络节点分布(第400代)
图4是迭代至第800代的网络节点分布情况。由图4可知，当迭代至800代时，与第400代相比较，重叠的感知范围明显减少，重点覆盖范围的覆盖面积大幅提高，节点覆盖率大幅度提升。实验结果表明，采用本文所提方法在迭代至第800代时的有效覆盖率最高，无线网络空间深度覆盖率提升最显著。
图4 仿真模型中的网络节点分布(第800代)
3.2 优化覆盖效果分析
表1展示了图2—4中节点的实际覆盖率及其与理想覆盖率的对比关系，实际加权覆盖率及其与理想加权覆盖率的对比关系。
表1 节点覆盖率与理想值的对比
由表1可知，节点覆盖率从第0代迭代至400代，实际覆盖率从15.21%升至17.97%，实际加权覆盖率从15.14%升至17.48%，实际覆盖率与理想覆盖率之比为92.63%，实际加权覆盖率与理想加权覆盖率之比为85.51%，网络节点覆盖率明显提升。节点覆盖率从第400代迭代至800代，实际覆盖率已从17.97%提升到了20.23%，提升了2.26%，实际加权覆盖率提升了3.44%，节点实际覆盖率与理想覆盖率之比提升了6.42%，实际加权覆盖率与理想加权覆盖率之比大约提升了10%。实验结果表明，随着迭代次数的增加，网络节点实际覆盖率能极大限度地逼近理想极限值。
为了检验本文所提方法在节点数不同时对覆盖率的提升情况，将节点数从60个分别更改为120个、180个及240个，将迭代次数依次变为第300代、600代和900代，所获得的节点覆盖率数据如图5所示。
图5 节点数不同时的覆盖率
由图5可知，当迭代次数相同时，节点数越多，覆盖率越高；
在小于300代的迭代中，节点覆盖率提升速度最快，在300—600代的迭代中，节点覆盖率提升速度明显下降，在600—900代的迭代中，提升速度增长缓慢，直至接近理想值时，速度难以提高。实验结果表明，节点覆盖率随着迭代次数的增加而不断提高，直至极大限度逼近理想极限值。
3.3 规划时间对比结果
为了更好地验证本文所提方法的可靠性，将覆盖规划的工作量与时间的对比关系进行验证，然后画出规划工作量与规划时间对比关系曲线，并将对比关系曲线与文献[4]、文献[5]、文献[6]所提方法进行对比。
如图6所示，文献[5]和文献[6]所提方法的对比关系曲线大致吻合，随着规划工作量的增加，所用规划时间也不断增加；
文献[4]所提方法的对比关系曲线波动较大，随着规划工作量的增加，所用规划时间却呈下降趋势；
本文所提方法对比关系曲线较为平缓，随着规划工作量的增加所用规划时间稳步上升，而且最小规划时间大大缩短，能够较大程度节约规划时间，提高规划效率。
图6 规划工作量与规划时间对比关系曲线
本文提出了一种新的无线网络空间深度覆盖规划方法，首先采用K-means聚类算法挖掘无线网络空间深度覆盖规划特征，然后使用层次分析法构建递阶层次结构模型、评估覆盖性并构建无线网络空间深度覆盖规划模型，最后使用MACA对模型进行优化，实现了无线网络空间深度覆盖的高效规划。
猜你喜欢 覆盖率无线网络聚类 民政部等16部门：到2025年村级综合服务设施覆盖率超80%今日农业(2022年15期)2022-09-20我国全面实施种业振兴行动 农作物良种覆盖率超过96%今日农业(2021年21期)2021-11-26时间触发卫星无线网络同步仿真研究载人航天(2021年5期)2021-11-20无线网络安全漏洞及防范策略电子技术与软件工程(2019年8期)2019-07-16无线网络信息安全技术及风险分析电子制作(2019年24期)2019-02-23数种基于SPSS统计工具的聚类算法效率对比软件导刊(2018年11期)2018-11-19面向WSN的聚类头选举与维护协议的研究综述现代计算机(2018年27期)2018-10-25基于信令分析的TD-LTE无线网络应用研究消费导刊(2017年24期)2018-01-31电信800M与移动联通4G网络测试对比分析价值工程(2018年3期)2018-01-23改进K均值聚类算法舰船电子对抗(2017年6期)2018-01-11