高效的移动sink路由问题的启发式算法

基于移动sink节点的WSN节能路由协议【摘要】针对无线传感器网络中能量消耗不均引起的热区问题，提出一种基于移动sink节点的WSN节能路由协议MSERP，将整个网络分成若干个虚拟网格，根据节点剩余能量和到网格重心距离选举簇头。

通过PSO算法来确定sink的下一个移动位置，粒子适应值函数由簇头到sink节点的距离和sink节点周围簇头能量因素定义。

仿真结果表明，该协议有效地解决了热区问题，提高了网络的生存周期。

【关键词】无线传感器网络；热区问题；移动sink节点；PSO算法中图分类号：TP212.9 文献标识码： A 文章编号：2095-2457（2017）26-0010-002Based on the Mobile Sink Node of WSN Energy-efficient Routing ProtocolZHANG Yu-lan GUO Xiao-hui（School of Computer Engineering，Chongqing College of Humanities，Science & Technology，Chongqing 401524，China）【Abstract】WSN energy-efficient routing protocol based on a mobile sink node of （MSERP）was proposed in this paper.The whole network was divided into some virtual unit，which choose cluster heads according to the residual energy and the distance of a node and a virtual unit of center. The next stay the best location of the sink is determined by PSO algorithm. The definition of the fitness function of particle is based on two factors：the distance of cluster heads to sink and the energy of cluster heads around the sink. Simulation results demonstrate that the protocol can efficiently solve the hot spot problem and prolong the network lifetime.【Key words】Wireless Sensor Networks （WSN）；Hot spot problem；A mobile sink；PSO algorithm0 引言?魍车奈尴叽?感器网络分簇算法，sink保持静止，距离sink越近的节点由于需要转发更多的数据而过早死亡，容易出现“热区”问题。

53 54 55
2011年 科研热词 链路服务质量 软错误 软件体系结构模型 贪婪算法 谓词式覆盖 谓词式关系(二叉树) 谓词式 试错 自适应软件 自动推理 网关部署 组合查询 空间索引 空间查询处理 空间数据库 移动数据 知识编译 混合遗传算法 混合网络 海明距离 流水调度 构件分派 最大完工时间 无线传感器网络 无等待 数据缓存 数据查询 敏感寄存器 扫描线算法 扩展规则 总空闲时间增量 开销 基于内容路由 在线演化 图划分 图像视觉特征 图像标注改善 启发式算法 启发式策略 启发式奖赏函数 可靠性 发布/订购 分层强化学习 关键路径 关键字查询 关系数据库 全局最近邻查询 元组组合 候选集 俄罗斯方块 人工智能 prbt-*算法 推荐指数 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2012年 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
科研热词 推荐指数 重复发表 1 贪心算法 1 计算法 1 蚁群算法 1 蚁群优化 1 自适应搜索 1 结构化测试 1 社交网络 1 状态格局 1 物理模型 1 测试用例 1 测试数据自动化生成 1 测试序列 1 条件/判定覆盖 1 智能规划 1 文章 1 撤销 1 扩展有限状态机 1 微型计算机系统 1 影响力最大化 1 并行算法 1 平衡约束 1 常量合成 1 大规模并行系统 1 大规模优化组合 1 多值规划任务 1 处理器 1 圆形packing问题 1 启发式算法 1 启发式方法 1 启发式应用 1 启发式修正 1 启发式 1 可达性分析 1 变异算法 1 动态挥发率 1 分配算法 1 元启发式搜索技术 1 任务分配问题 1 一致性规划 1 tbh 1 social network 1 influence maximization 1 heuristic algorithm 1 greedy algorithm 1

无线传感器网络中一种基于移动Sink的数据收集算法张蕾;张堃;宋军【摘要】A novel algorithm MSDG( Mobile Sink-based Data Gathering)which based on mobile sink data gathering does not depend on the location of nodes, is proposed in mobile wireless sensornetworks( WSNs). It solves the"hot spot "problem, that is multi-hop routing in WSNs brings to energy hole. Sink node builds the routing tree along the nearest fixed node as root node. At the same time, the sensed data in cluster node carry on data fusion calculation through the cluster, thus the data fusion is flanked by trees to send to Sink node in reverse-by-jump. Simulation results show that in the aspect of average energy consumption and network lifetime, the performance of MSDG surpasses data gathering protocols of LEACH and ACE-L.%针对移动无线传感器网络设计一种不依赖于节点地理位置的基于移动汇聚节点( Sink)的数据收集算法(Mobile Sink-based Data Gathering,MSDG).该算法解决了无线传感器网络中多跳路由通信时出现能量空洞的“热点”问题.Sink沿途以最近的固定节点作为根节点动态构建路由树.簇内移动节点感知的数据经簇头进行数据融合计算,然后将融合后的数据沿路由树反向逐跳转发给Sink.仿真结果表明,MSDG在节点的平均能耗和网络生存时间等方面的性能远超过LEACH、ACE-L等数据收集协议.【期刊名称】《传感技术学报》【年(卷),期】2012(025)005【总页数】5页(P673-677)【关键词】无线传感器网络;数据收集;分簇;移动Sink【作者】张蕾;张堃;宋军【作者单位】北京建筑工程学院计算机教学与网络信息部,北京100044;北京建筑工程学院计算机教学与网络信息部,北京100044;北京建筑工程学院计算机教学与网络信息部,北京100044【正文语种】中文【中图分类】TN919.25随着物联网技术、嵌入式技术以及低功耗的无线通信技术的发展，生产具备感应、无线通信以及信息处理能力的微型无线传感器已成为可能，这些廉价的、低功耗的传感器节点共同组织成无线传感器网络WSNs(Wireless Sensor Networks)，通过节点间的相互协作，将其监测和感应到的信息(温度、湿度等)传送到基站(Sink)，实现网络数据收集功能。

移动Sink的传感器网络路径优化策略于志博;孔祥雪;裴金金【期刊名称】《传感器与微系统》【年(卷),期】2016(035)011【摘要】Introducing mobile sink in wireless sensor networks(WSNs)can avoid network congestion and energy hole and reduce energy consumption of network,but it lead to large delay because of limitation of moving speed. Aiming at this problem,path optimization strategy of mobile sink under delay constrains is proposed. Adjustable node weight is designed according to relationship between delay and energy consumption of network. The optimal node weight is obtained through simulated annealing genetic algorithm. The sink nodes and the optimal moving path are acquired through iteration procedure based on the optimal node weight. Simulation results show that the strategy can reduce energy consumption network and have fast convergence under the premise of meeting delay constrains.%在无线传感器网络（WSNs）中引入移动 Sink 可以避免网络拥塞和能量空洞并降低网络能耗，但由于移动速度的限制导致时延较大。

传感器网络中多移动sink节点的路径规划算法俸皓;罗蕾;董荣胜;王勇【摘要】This paper considers the situation where multi-mobile sinks and path endpoints are located along the edge of the circumference, and abstracts it as a hybrid optimization problem characterized in high dimensionality and large searching space. Classic algorithms like thek-splitour algorithm cannot optimize its continuous variables. This paper first obtainsk sub-paths by adoptingk-splitour algorithm and designs the method to eliminate the crossing of sub-paths to acquire local optimumfor discrete variables. Then the algorithm acquires multi-mobile sinks path planning results efficiently by designing local optimization methods for continuous variables to decide on the location of access points on each communication disk. The upper bound of the algorithm and its theoretical proof are presented. The experiments show the effectiveness of both the designed model and its algorithm in solving the path planning problem in data collection.%考虑多移动sink且路径端点在圆周边界上的情形，将此抽象为一个混合优化问题，该优化问题具有维数高和搜索空间大的特点，经典的算法(如k-splitour算法)无法针对其连续分量进行优化，为此该文首先以k-splitour算法获得k条子路径并设计了消除子路径交叉的方法，以获得对离散分量的局部寻优，再通过设计对连续分量的局部优化方法以确定每个通信圆盘上访问点的位置，从而可以高效地获取多个sink移动节点的规划路径解。

doi:10.3969/j.issn.1003-3114.2020.02.015引用格式:柏琪,朱晓娟.无线传感器网络中移动sink 节点的路径规划[J].无线电通信技术,2020,46(2):228-233.[BAI Qi,ZHU Xiaojuan.Path Planning of Mobile Sink Node in Wireless Sensor Network [J].Radio Communications Technology,2020,46(2):228-233.]无线传感器网络中移动sink 节点的路径规划柏㊀琪,朱晓娟(安徽理工大学计算机科学与工程学院,安徽淮南232001)摘㊀要:在无线传感器网络中,大量感知数据汇集到sink 节点的采集方法会导致sink 节点附近的节点能量耗尽,造成能量空洞㊂针对该问题,利用移动的sink 节点进行数据收集是一种解决方法,其中移动sink 的路径规划成为一个重要的问题㊂提出了一个移动sink 路径规划算法,将无线传感器中随机分布的节点划分为不同的子区域,寻找sink 节点移动的最佳转向点,最终得到最优的移动路径,以实现无线传感器网络生命周期最大化㊂仿真实验表明,与现有方案相比,该算法能显著延长网络的生命周期㊂关键词:移动sink;路径规划;转向点;生命周期中图分类号:TP393㊀㊀㊀文献标志码:A㊀㊀开放科学标识码(OSID):文章编号:1003-3114(2020)02-0228-06Path Planning of Mobile Sink Node in Wireless Sensor NetworkBAI Qi,ZHU Xiaojuan(School of Computer Science and Engineering,Anhui University of Science and Technology,Huainan 232001,China)Abstract :In wireless sensor networks,a large number of sensing data collected to sink nodes will lead to energy depletion of the nodes near sink nodes,resulting in energy hole.To solve this problem,it is a solution to collect data by using mobile sink nodes.The path planning of mobile sink becomes an important issue.In this paper,a mobile sink path planning algorithm is proposed,which divides randomly distributed nodes into different sub regions,searches for the best turning point of sink node movement,and finally obtains the optimal mobile path to maximize the lifetime of wireless sensor network.Simulation results show that compared with the existing scheme,the algorithm can significantly extend the lifetime of the network.Key words :Mobile sink;Path planning;Turning point;Network lifetime收稿日期:2019-11-12基金项目:国家自然科学基金项目(51504010)Foundation Item :National Natural Science Foundation of China(51504010)0　引言无线传感器网络中通过多跳路由汇聚到sink 节点是传统的数据收集方法㊂离sink 节点很近的传感器节点或簇头,被视为sink 节点的中介,需要转发远处传感器节点的数据包,这会导致能量有限的传感器节点快速消耗掉自身的能量,从而死亡,这被称为热点或能量空洞问题[1-4]㊂为了避免这种情况,使用移动sink 节点来解决这一问题,将sink 节点安装在一些车辆上,围绕网络区域移动进行数据收集㊂使用移动sink 进行数据收集有以下优点:①传感器节点将数据转发到移动sink 节点的跳数相对较小,这会减少拥塞和数据包丢失的概率[5];②移动sink 节点的存储和计算资源较充分;③使用移动sink 节点,在很大程度上减少某些传感器节点数据转发负载,可以更好地利用传感器的能量,从而延长了整个网络的寿命㊂目前,sink 节点移动的轨迹选择主要有3种类型:随机移动㊁固定移动和可控移动[6]㊂在基于随机移动的方法中,sink 节点的移动轨迹不是预先设定的㊂例如,节点放在动物身上,动物的移动轨迹是随机的,虽然这个方案很容易实现,它的优点是保证移动sink 节点到每个节点进行收集数据的概率是相等的,但其性能是不确定的,因为它可能会产生很长的路径,造成链路断开,产生额外的能量损耗㊂在固定移动中,移动sink节点将移动sink访问一些预先指定的位置,并从传感器节点组中收集数据,它需要只访问有限数量的节点,但不会根据无线传感器网络节点的能量情况进行路线改变,缺乏灵活性㊂在可控移动中,可以根据路径反馈的信息进行路径规划㊂因此,它能够在指定延迟限制内进行数据收集,可以很好地平衡网络寿命与延迟的问题㊂1㊀相关工作近年来,为了解决能量空洞问题,提高无线传感器网络的生命周期,许多算法已被提议用于移动sink节点的路径规划㊂周晖等人[7]提出移动多sink 生物启发式路径规划算法,采用蚁群优化作为上层算子,根据网络运行过程中的变化,即节点数量和能量变化,实时优选下层算子集,选中的下层算子集规划各移动sink节点的路径㊂黄冰倩等人[8]首先利用图论知识,把无线传感器网络看成一个连通的无向图,将传感器节点转化成图的顶点,并选取虚拟信标节点,利用蚁群算法对选取的节点进行遍历,从而获得移动路径㊂俸皓等人[9]提出了一种新的基于萤火虫群的路径规划方法㊂首先依据问题的特性对可行解空间进行了压缩;然后为提高算法在高维解空间的搜索效率,对离群萤火虫粒子设计了变异操作并设计了个体逐维移动的方式,提高了算法的求解精度并加快了算法的收敛速度㊂文献[7-9]运用生物智能的路径规划算法,这类算法没有考虑现实中的适用性,数据的处理和成本太高㊂陈友荣等人[10]提出了一种高效的距离感知路由算法,通过无线传感器网络的移动汇聚,汇聚节点以一定的速度沿网络边界采集监控数据㊂但是该算法中提到的障碍物和移动sink节点的移动感知问题没有得到解决,且过于复杂导致数据传输速率受到影响㊂与以上算法相比,结合实际情况,本文考虑合理规划移动sink节点的路径,最大限度延长网络寿命㊂首先将移动sink节点通信范围内的传感器节点的剩余能量信息传达给移动sink节点,然后通过能量密度与移动路径选择算法选择出移动sink的最佳转向点,得到sink节点移动的最优路径㊂对于能量密度和具体的移动路径选择算法会在后面进行详细介绍㊂2㊀网络模型2.1㊀问题描述无线传感器网络是使用同构的传感器节点随机部署在HˑW的长方形区域内,其中每个传感器节点都有有限电源和相同的通信半径,并且移动sink节点能量不受限制㊂本文为了避免移动sink节点进行不必要的移动,规定检测区域内的节点都为簇首,该网络为骨干网络[11]㊂在监测区域内,假设传感器节点呈现正态分布,四周的节点分布较稀疏,中间部分比较集中㊂移动sink节点从矩形区域的左边中点出发,根据规划的路径进行匀速移动,在通信范围内进行数据的收集,直到区域右边中点,看做完成一轮采集㊂本文将矩形区域划分成若干个子区域,以便更准确进行转向点选择㊂以下是一些假设㊂①每个传感器节点在部署后保持静止并具有唯一识别号码;②假定在每个转向点位置,移动sink节点的逗留时间可以忽略不计;③所有通信都通过共享无线电建立;④网络生命周期定义为直到第一个节点死亡为止;⑤假设从传感器节点到移动sink节点没有重传数据,移动sink节点负责将收集到的数据传到信息处理中心,且移动sink节点运动速度恒定不变㊂2.2能耗模型本文提出相应的能量模型,其中单个传感器节点在发送或接收k比特数据所需的能量为:E1=E elec k㊂(1)在信号放大器件上消耗的能量为:E2=E amp d2k,(2)式中,E amp为单位功率放大器的能量消耗,d为两个节点之间的距离㊂所以接收消息时只存在第一步的能量消耗;发送数据所消耗的能量为两步的和,即:E T=E1+E2㊂(3)2.3㊀能量密度本文提出的能量密度是指单位区域内传感器节点的能量㊂它在一定程度上反映了传感器网络负载是否平衡,对于移动sink节点的转向点也有很大影响㊂使用二分法划分区域,在能量密度较高的区域会尽可能多地划分子区域,增加转向点的数量,避免因某个节点承载过多的转发任务而造成能量耗尽㊁节点死亡的后果,达到传感器网络的能量平衡㊂能量密度的计算公式如下:ED =RE /N ,(4)式中,ED 为能量密度,RE 代表子区域内传感器节点的剩余能量总和,N 为子区域内无线传感器节点的数量㊂对于一个区域内能量密度大小,以整个网络的能量密度T 为标准,如果ED >T ,则说明该子区域能量密度大,需要考虑增加转向点;相反,如果ED <T ,则说明该子区域能量密度小㊂3㊀转向点选择与子区域划分首先对移动sink 节点路径规划的必要性进行研究,如图1所示㊂移动sink 节点从A 移动到B ,经过整个传感器网络区域,这个路径是一条固定的直线,靠近该路径的节点可以把数据直接传送给移动sink 节点,但是由于传感器节点的能量有限,远离该路径的节点想要发送数据必须经过多跳转发才能成功㊂由此可以看出,这样的路径影响整个网络的生命周期㊂为了解决该问题,本文提出了转向点的概念,如图2所示㊂移动sink 节点同样是从A 移动到B ,但在移动过程中,它不是一条固定的直线路径,而是经过多次转折,转折的目的是为了尽可能保证分布在路径两边的传感器节点传送数据到移动sink 节点需要转发的次数比较少,也就是跳数减少,这样大大均衡了网络的能量负载,提高生命周期㊂图1㊀直线移动Fig.1㊀straight linemovement图2㊀规划路径移动Fig.2㊀Planning path movement假设在一个矩形感知区域内,sink 节点的的起始点坐标分别为A 和B ,如图2所示㊂A 点的坐标为(X A ,Y A ),B 点坐标为(X B ,Y B ),网络中所有节点的横坐标都在X A 和X B 范围之内㊂实验假设的传感器节点网络,如图3所示,需要使用二分法[12-13]将感知区域划分为R 个区域㊂首先以它的中轴线划分,第一个转折点的坐标(X 1,Y 1)=X A +X B2,y (),可以固定它的横坐标,但是它的纵坐标是不确定的,所以设y =k ㊃Δy ,其中k 为任意的常数,Δy 为固定的单位网格的长度㊂图3和图4是二分法第一次划分的结果㊂图3㊀k 为4时转折点结果Fig.3㊀K is the result of turning point at4图4㊀k 为2时转折点结果Fig.4㊀K is the result of turning point at 2图3中,有几个节点的数据包需要转发3次,图4中的节点数据包最多转发2次,对比可以看到在转折点坐标为(X A +X B2,2Δy )时,移动sink 节点的路径提供较好的网络性能㊂(X A +X B2,2Δy )是第一次划分区域得到的转折点坐标结果,第二次划分时,在第一次划分的两个子区域重复第一次寻找转折点的过程㊂通过迭代操作下去,会得到一系列转向点,对比些转向点,选择其中的最优转向点,最大程度使网络负载达到平衡㊂4㊀簇首到移动sink 的最短路径本文在设计移动sink 的移动路径有一个重要前提,在数据传输阶段,如果传输数据距离移动sink 较远,不在其通信范围内,此时通过另外簇首节点进行数据转发,要保证传输数据路径是最短路径,以跳数来判断传输路径是否为最短路径㊂具体步骤用Dijkstra 算法[14-16]来求解㊂①给定两个集合:已求出最短路径节点集合S (初始时,在S 中添加一个源节点V 1)和未求出最短路径的所有节点的集合U ㊂②从U 中选取一个距离V 1最小的顶点K加入到S中(选定的距离就是V1到K的最短路径)㊂且只有当该距离小于传感器节点的一跳范围时,才能加入S,如果两个节点不能通过一跳到达,距离就为ɕ,排除该节点㊂③以K为新考虑的中间点,修改U中各节点的距离㊂若从源节点V经过顶点到节点U的路径距离比原来不经过节点K的路径距离短,则修改V1到U的距离㊂④重复步骤②㊁③直到sink节点加入到S中,就能知道源点V1到sink节点进行数据传输的最短路径㊂5　路径规划算法通过以上子区域的划分㊁转向点的选择和传输数据的最短路径可以得出最终的路径规划算法㊂算法思想为:将传感器网络划分为合适数量的子区域,找出移动sink节点的转向点,在转向点中选择最优的,依次连接所有最优转向点,最后得到移动sink 节点的最佳路径㊂具体算法如下㊂步骤1:以中轴线将传感器网络区域一分为二,分为左右两个子区域,并进一步划分多个子区域,选择候选转向点㊂输入:整个区域簇首的剩余能量:R1.R2...Rm...Rn 左子区域内各个簇首的剩余能量:R1.R2...Rm右子区域内各个簇首的剩余能量:Rm...Rn整个区域内簇首节点数量:n左区域内簇首的数量:m右区域内簇首的数量:n-m过程:1:for㊀R1to RmED L=(R1+ +Rm)/mʊ计算左子区域的能量密度2:for㊀Rm to RnED R=(Rm+ +Rn)/(n-m)ʊ计算右子区域的能量密度3:for㊀R1to RnT=(R1+ +Rn)/nʊ计算整个区域的能量密度4:if㊀ED L<T||ED R<T利用第3提到的子区域划分方法进行区域划分5:else该区域不再进行子区域划分6:end㊀输出:划分区域线上的点为候选转向点步骤2:选择最优转向点㊂输入:候选点A(X1,Y1),B(X2,Y2) (X n,Y n),其中X1=X2= =X n,Y1=k1Δy,Y2=k2Δy Y n=k nΔy(k为常数,Δy 为固定网格格数)各个簇首到sink节点的跳数h1,h2 h n过程:1:for㊀h1to hn㊀ʊ选择A作为转向点,遍历所有簇首节点到sink节点的跳数R A=(h1+h2+ hn)/nʊ选择A作为转向点传输数据所需要的平均跳数2:for㊀h1to hnʊ选择B作为转向点,更新步骤1中簇首节点到sink节点的跳数R B=(h1+h2+ hn)/nʊ选择B作为转向点传输数据所需要的平均跳数3:if㊀R A<R BtakeA into S[i][j]㊀ʊS为最优转向点的集合4:elsetake B into S[i][j]5:循环操作到所有转向点比较完成6:end输出:最优转向点的集合S步骤3:sink节点以匀速依次经过最优转向点,该路径就是sink节点的移动路径㊂图5~图8分别为移动sink节点在不同迭代操作次数下,移动路径的改变㊂图5㊀初始状态Fig.5㊀Initialstate图6㊀第1次迭代Fig.6㊀Firstiteration图7第2次迭代Fig.7㊀Seconditeration图8㊀第3次迭代Fig.8㊀Third iteration从图中可以看出,初始状态有些簇首需要将数据包转发4~6次,随着不同时期下路径的改变,传感器节点需要转发的数据包越来越少,迭代3次后传感器节点最多只要转发2次,能量消耗也趋于平衡,生命周期也会大幅度延长㊂6　仿真实验采用Matlab进行仿真,在实验中,假设在监测区域为300m∗400m的范围,300个传感器节点随机分布,传感器节点的传输半径为40m,普通节点的起始能量为1J,节点发送单位字节数据的能耗为100nJ,接收单位字节数据的能耗为20nJ,sink节点沿着规划路径匀速运动,每个周期产生的平均数据为1000B,规定从区域左边边界移动到右边边界为一个周期,完成一个周期的数据收集为一轮㊂仿真实验的约束条件为:①传感器节点静止不动,移动sink节点没有能量约束;②在一个周期内,无数据传输的节点不参与路径规划㊂为了验证本文提出路径规划算法的有效性,将其与文献[5]中提出的sink节点固定转向移动算法进行对比㊂固定转向移动算法在转向点的选择上不考虑网络的剩余能量,在sink节点移动之前已经确定了转向点,固定在监测区域的水平边界上,sink节点在转向点之间直接进行移动㊂仿真实验将从每轮存活节点百分比㊁节点的平均剩余能量㊁网络平均跳数三个方面进行判断,比较两种算法的网络生命周期㊂图9是在收集数据的不同轮数下,传感器节点存活的百分比㊂从图中可以看出,与文献[5]中的sink节点固定转向算法相比,sink节点固定转向算法在2500轮时就出现了节点死亡,本文算法在3 500轮后才出现节点死亡,到6000轮时,存活节点还剩60%,而sink节点固定转向算法只存活了一半,这说明了本文提出的算法能有效延长网络的生命周期㊂图9㊀每轮存活节点百分比Fig.9㊀Percentage of surviving nodes in each round图10为传感器网络中两种算法节点平均剩余能量的曲线对比图㊂由图10可知,本文设计的移动sink节点路径规划算法与sink节点固定转向算法在工作的前25s,能量消耗的差距并不大,但是随着时间的进行,sink节点固定转向算法的能耗问题就显现出来,能量消耗明显加快,由此可以判断,本文提出的算法很大程度上解决了能耗问题,延长了网络生命周期㊂图10㊀节点平均剩余能量Fig.10㊀Average residual energy of nodes 图11为网络平均跳数对比图㊂对于sink节点固定转向算法,在前50s没有传感器节点死亡,网络平均跳数保持平衡,本文算法平均跳数略有下降,随着网络运行时间的增加,两种算法下传感器网络的平均跳数都出现明显下降㊂但是,本文算法对应的网络平均跳数始终低于sink节点固定转向算法,有效降低了数据丢包的概率与传感器节点能耗,从而达到延长网络生命周期的目的㊂图11㊀网络平均跳数Fig.11㊀Network average hops7　结束语针对无线传感器网络中的能量空洞问题,提出了移动sink节点路径规划的算法,该算法使用二分法划分区域,基于传感器节点的能量密度选择转向点的位置㊂仿真结果表明,本文所提出的方案可以减少能量空洞问题,从而延长网络寿命㊂与现有算法比较后,显示出它在延长网络生命周期方面的优越性㊂下一步工作的重点是分析不同数量移动sink节点的路径规划以及它们之间如何协调收集数据问题㊂参考文献[1]㊀郭剑,孙力娟,许文君,等.基于移动sink的无线传感器网络数据采集方案[J].通信学报,2012,33(9):176-184.[2]㊀冯亚超,贺康,杨红丽,等.一种无线传感器网络数据收集协议的研究与优化[J].传感技术学报,2014,27(3):355-360.[3]㊀HU Yifan,ZHENG Yi,LIU Hailin,et al.Mobile Sink PathPlanning Research for Underwater Heterogeneous SensorNetwork[C]ʊ第30届中国控制与决策会议论文集,2018:291-296.[4]㊀周唯,刘冬,刘会师.基于无线传感器网络拓扑的研究与设计[J].软件,2013,34(12):22-25.[5]㊀周涛,高美凤.密集型传感器网络中移动sink的路径选择机制[J].计算机应用研究,2013,30(4):1120-1122.[6]㊀陶丹,陈后金.移动无线传感网络中基于Sink协助的数据采集算法[J].北京交通大学学报,2013,37(6):1-7.[7]㊀周晖,薛磊,钱兰美.大规模传感网移动多Sink生物超启发式路径规划[J].仪表技术与传感器,2017(10):105-109.[8]㊀黄冰倩,杜庆治,龙华.面向WSN的移动锚节点路径规划算法[J].云南大学学报(自然科学版),2018,40(1):29-35.[9]㊀俸皓,罗蕾,王勇,等.基于萤火虫算法的无线传感器网络移动sink节点路径规划方法[J].微电子学与计算机,2016,33(5):47-51.[10]陈友荣,陆思一,刘半藤,等.移动无线传感网的移动感知路径选择算法[J].传感技术学报,2019,32(1):117-126.[11]周新莲,朱泽鹏.无线传感器骨干网络路由算法[J].吉林大学学报(理学版),2019,57(2):363-368. [12]张晓勇,王仲君.二分法和牛顿迭代法求解非线性方程的比较及应用[J].教育教学论坛,2013(25):139.[13]梁青,焦峰.WSN中基于二分法与移动Sink的数据收集协议[J].计算机工程,2016,42(12):39-43. [14]吴红波,王英杰,杨肖肖.基于Dijkstra算法优化的城市交通路径分析[J].北京交通大学学报,2019,43(4):116-121,130.[15]ZHOU Minhang,GAO Nina.Research on Optimal PathBased on Dijkstra Algorithms[C]ʊProceedings of the3rdInternational Conference on Mechatronics Engineering andInformation Technology(ICMEIT2019),2019:900-908.[16]叶颖诗,魏福义,蔡贤资.基于并行计算的快速Dijkstra算法研究[J/OL].计算机工程与应用:1-11[2019-10-24].http:ʊ/kcms/detail/11.2127.TP.20190724.1129.006.html.作者简介:柏㊀琪㊀安徽理工大学计算机科学与工程学院硕士研究生,主要研究方向:物联网㊁无线传感器网络㊂朱晓娟㊀博士,安徽理工大学副教授㊂主要研究方向:无线传感器网络㊂。

随机分布的无线传感器网络中移动sink的路径规划常捷;张灵【期刊名称】《计算机科学》【年(卷),期】2017(44)2【摘要】针对大量节点正态分布的无线传感器网络,为了提高网络的寿命,提出了一种移动sink的高效路径规划方案.首先由节点的分布规律将网络划分为多个子区域,然后在此基础上以最大化网络寿命为目标找到sink的最佳转折点,最后得到一条最优路径.通过NS-2中大量的仿真实验结果表明,与已有的类似方案相比,该方案可以有效均衡网络能耗,延长网络的生命周期,同时取得较好的网络性能.%In wireless sensor networks with a large number of normally distributed nodes,in order to improve the network lifetime,an efficient path planning scheme of a mobile sink was proposed in this paper.Firstly,the network is divided into several subregions by the distribution of nodes.Then,the best turning point of sink on this basis is found in order to maximize the network lifetime.Finally,an optimal path is got.Lots of simulation results under NS-2 show that compared with existing similar schemes,this scheme can effectively balance the network energy consumption,prolong the network lifetime and achieve better network performance.【总页数】5页(P147-151)【作者】常捷;张灵【作者单位】广东工业大学计算机学院广州510006;广东工业大学计算机学院广州510006【正文语种】中文【中图分类】TP393.01【相关文献】1.无线传感器网络节点定位中移动信标的路径规划 [J], 张强;张庆;张磊;于纪言;贾方秀;2.无线传感器网络节点定位中移动信标的路径规划 [J], 张强;张庆;张磊;于纪言;贾方秀3.WSN数据收集中移动Sink的路径规划和簇头节点选取问题的综合研究 [J], 惠晓威;刘彦每4.无线传感器网络中移动sink节点的路径规划 [J], 柏琪; 朱晓娟5.基于萤火虫算法的无线传感器网络移动sink节点路径规划方法 [J], 俸皓;罗蕾;王勇;董荣胜因版权原因，仅展示原文概要，查看原文内容请购买。

一种新的支持移动sink的多媒体传感器网络路由协议汤子隆程良伦（广东工业大学自动化学院，广州510006）摘要：轻便的手提式移动设备已经越来越普及。

本文提出了一种新的支持移动sink的多媒体传感器网络路由协议，该协议利用锚节点作为转发节点与移动sink进行通信，避免多媒体传感器节点与sink直接进行远距离通信，在多媒体传感器节点中采用改进的基于地理信息的路由协议建立路由路径。

仿真实验表明该协议不仅能支持移动sink，而且能够有效降低节点能耗，延长网络寿命，提高数据传输效率。

关键词：多媒体传感器网络；移动sink；锚节点；基于地理信息的路由协议中图法分类号：TP393 文献标识码：AA New Geographic Routing for mobile sink in WirelessMultimedia Sensor NetworksTang Zi-long Cheng Liang-lun(Faculty of Automation, Guangdong University of Technology, Guangzhou 510006)Abstract：Portable mobile devices have been becoming more and more popular. This paper proposes a new protocol for mobile sink in multimedia sensor network routing. The protocol uses anchor nodes as forwarding node to communicate with the mobile sink so that direct long-distance communications for multimedia sensor nodes and sink can be avoided, and sensor nodes in the multi-media uses an improved geographic greedy forwarding routing protocol to establish the routing path. Simulation results show that the agreement will not only support the sink mobility, but also support nodes to reduce energy consumption, extend the network lifetime and improve the efficiency of data transmission. Keywords：multimedia sensor networks; mobile sink; anchor nodes; geographic routing1 引言随着监测环境的日趋复杂多变，由传统无线传感器网络（wireless sensor networks, WSNs）所获取的简单数据已经不能满足人们对环境监测的全面需求，迫切需要将大量丰富的图像、音频、视频等多媒体信息引入到以传感器网络为基础的环境监测活动中来。

基于全局时延最小化的移动Sink数据收集算法常捷;张灵;曾碧【摘要】For the latency problem brought by the movement of Sink node,this paper presents a mobile Sink data gathering program based on optimal path(OPDG). Firstly,a set of rendezvous points(RP)are obtained by MWHA (Minimum Weighted Heuristic Algorithm)algorithm. Then a best set of access points are selected according to the RP set. Finally,the shortest path is found across the access points. The mobile Sink will travel along this path peri⁃odically and collect data at each access point. Lots of simulation results show that compared with existing algorithm , OPDG algorithm can shorten the delivery latency and prolong the network lifetime.%针对Sink节点移动所带来的时延问题，提出了一种基于最优路径的移动Sink数据收集方案OPDG（Data Gathering Based on Optimal-Path）。

首先由MWHA（Minimum Weighted Heuristic Algorithm）算法得到汇聚节点RP（Rendezvous Point）的集合，然后根据这些RP节点求出移动Sink的最佳驻留点集合，最后求出经过驻留点的最短路径。

基于能量感知的无线传感器网络Sink节点移动方案吴文铁;李敏;文永革【摘要】Energy of nodes in Wireless Sensor Network ( WSN ) directly impacts on the network lifetime. Therefore,from the perspective of saving energy of nodes,sink node moving scheme based on energy awareness is proposed in this paper, which is marked as EASM-INL. In EASM-INL scheme, according to energy level, sensor nodes adjust the transmission range. As the slack, it shortens the transmission range in order to save electricity. In addition,sink node collects the information about energy of sensor nodes,and computes the Maximum Capacity Path ( MCP) . As long as there is a path capacity value less than the threshold,sink node is readyto move. It computes the maximum capacity path in north,south,east,west direction,and moves along the direction in minimum value. Then,it establishes theoretical derivation model and analyzes the EASM-INL scheme in term of improving the performance of network lifetime. Finally,this paper uses numerical simulation to verity the performance of EASM-INL scheme. Simulation results show that EASM-INL scheme can prolong network lifetime compared with traditional sink moving schemes.%节点能量直接影响无线传感器网络的寿命。

基于二次栅格划分的移动sink最小路径构建算法王薇;史浩山;黄鹏宇;高宝建;牛进平;王举【期刊名称】《西北工业大学学报》【年(卷),期】2016(034)006【摘要】在无线传感器网络中引入移动sink能够有效解决能量空洞问题，从而提高无线传感器网络的生存时间。

但是移动sink的移动速度限制通常会影响数据收集的时延特性，文章的研究重点即如何为移动sink构建最佳巡航路径，从而减小信息收集时延。

充分利用传感器节点的通信范围，将构建最佳路径问题转化为求解带邻域的旅行商问题TSPN（traveling salesman problem with neighborhoods），并提出了一种基于二次栅格划分的可变长编码单亲遗传算法的最佳路径构建方法。

该算法首先在网络区域中使用粗粒度栅格进行划分，并利用可变长度编码的单亲遗传算法获得最佳途经栅格，从而构造出初始最佳路径。

然后对于每一个途经栅格再次使用细粒度栅格进行划分以优化收集路径。

仿真结果表明，新算法能够获得更短的数据收集路径，大幅度减低了网络信息收集时延，有效地拓展了网络的生存时间。

【总页数】6页(P1016-1021)【作者】王薇;史浩山;黄鹏宇;高宝建;牛进平;王举【作者单位】西北工业大学电子信息学院，陕西西安 710072; 西北大学信息科学与技术学院，陕西西安 710069;西北工业大学电子信息学院，陕西西安710072;西安电子科技大学通信工程学院，陕西西安 710071;西北大学信息科学与技术学院，陕西西安 710069;西北大学信息科学与技术学院，陕西西安710069;西北大学信息科学与技术学院，陕西西安 710069【正文语种】中文【中图分类】TP393【相关文献】1.基于栅格的传感网多移动Sink数据收集方案 [J], 杨瑞;沙超;卞遥;朱毅凯;王汝传2.基于栅格划分构建平面点集凸壳的算法研究 [J], 张大远;刘玉树3.基于二分法的多移动sink栅格数据收集协议 [J], 魏艳婷;张玉霞;李道全4.基于遗传算法的移动Sink数据采集信宿路算法 [J], 谢英辉;胡君;唐一韬5.基于改进PSO算法的WSN移动Sink路径规划算法 [J], 白秋产因版权原因，仅展示原文概要，查看原文内容请购买。

Sink轨迹固定传感器网络的高效数据采集机制郜帅;张宏科;徐怀松【摘要】在sink移动轨迹固定的传感器网络中,由于sink点有限的通信时间和节点的随机分布,使得很难兼顾数据采集量的提高和整体能耗的降低.为了解决该问题,提出了一种最大数据量最短路径(maximum amount shortest path,简称MASP)数据采集方法.MASP对网络中成员节点与sub-sink节点之间的匹配关系进行集中式优化.采用0-1线性规划方法对MASP问题进行形式化描述,提出了一种基于二维染色体编码的遗传算法进行求解,并给出了相应的数据通信协议设计.另外,MASP可以扩展支持低密度网络和多sink点网络.基于OMNET++的仿真结果表明,MASP 在能耗利用率方面要远远优于最短路径树方法(shortest path tree,简称SPT)及固定sink数据采集方法.【期刊名称】《软件学报》【年(卷),期】2010(021)001【总页数】16页(P147-162)【关键词】传感器网络;移动sink;轨迹固定;数据采集;能耗利用率【作者】郜帅;张宏科;徐怀松【作者单位】北京交通大学,电子信息工程学院,北京,100044;北京交通大学,电子信息工程学院,北京,100044;Department of Computer Science and Engineering, The University of Texas at Arlington, Texas, USA【正文语种】中文【中图分类】TP393能耗问题是困扰无线传感器网络(wireless sensor networks,简称WSNs)实际应用的主要障碍之一.在WSNs中,sink周围的节点由于需要转发更多的数据导致能量过早耗尽,容易形成WSNs能耗瓶颈.近年来,人们提出各种sink移动方案[1−17]使得全网能量消耗在更多的节点之间均衡,从而缓解能耗瓶颈问题.本文应用场景主要针对sink移动轨迹固定的无线传感器网络,其中,sink点沿着固定轨道周期移动,大量传感节点随机分布在轨道周围并采用多跳通信方式将数据传送到移动sink点.在此类网络中,sink点的移动性会带来其通信时间的限制,从而极大地约束了系统数据采集能力.故,如何提高能耗利用率,利用有限的能量采集尽可能多的数据成为该系统一个重要评价指标.在已有的文献中,最短路径树算法SPT(shortest path tree)[6,7,9]经常被用于寻找传感节点到移动sink的路径.SPT 能够有效降低系统能耗,却经常无法采集到预期的数据量,能耗利用率较低.针对 sink移动轨迹固定的大规模密集型传感器网络,本文提出了一种高效的数据采集机制 MASP(maximum amount shortest path),根据sink点的有效通信时间去优化各传感节点到sink的传输路径,从而使系统数据采集量最大化,同时降低网络总能耗,提高系统能耗利用率.本文第1节首先分析特定的应用场景模型和SPT算法的缺点.第2节提出MASP 优化问题并用0-1整数规划模型来描述该问题.第3节给出基于遗传算法的集中式解法.第4节结合MASP机制设计数据采集通信协议.第5节对MASP进行功能扩展,使之支持低密度网络和多移动sink点网络.第6节是MASP及遗传算法的性能仿真分析.第7节是综述传感器网络移动sink方案研究现状.1 应用场景模型分析本文考虑一种 sink点移动轨迹固定的大规模密集型无线传感器网络,实际应用场景包括野外生态环境监测、智能农业监测、大型建筑物健康结构监测等.图1给出一个应用场景模型示例.移动sink点M安装在机器人或者汽车等运动载体上,这些运动载体通常沿着已有的道路设施进行反复移动,因而sink点移动轨迹固定.每当sink点M移动到终点并返回起点时,称其完成一“轮”移动,本文以“轮数”来衡量网络性能.传感器节点随机、均匀散布在移动轨道L两侧.当sink点M移动到节点附近时,节点开始向M发送数据.根据移动sink点M的通信范围 R,可以将全部监测区域划分为两部分:直接通信区域 DCA(direct communication area)和多跳通信区域MCA(multi-hop communication area).图1中,L1和L2两条曲线之间的区域即为直接通信区域,该区域内的节点(称为sub-sink)距离轨道较近,因而能够向sink点M直接传送数据.而对于MCA中的节点(称为成员),需要采用多跳中继方式将数据传送给sub-sink,后者缓存来自各成员的数据并最终发送给移动sink点. Fig.1 WSN with path-fixed mobile sink图1 Sink轨迹固定无线传感器网络应用场景本文对该应用场景的特点进行如下假设:(1) 移动sink点具有足够的能量资源、存储资源和计算能力;(2) 各节点具有相同的属性,连续采集并发送数据,sub-sink点有足够的存储空间缓存数据;(3) 各成员必须且仅能选择一个sub-sink作为目的;(4) 考虑密集型网络,所有节点之间可以通过单跳或多跳方式互相连通;(5) 所有成员节点沿着最短路径向其所属的sub-sink点发送数据.在图1场景中,固定的移动轨迹和速度限定了移动sink点与各sub-sink点之间的通信时间长度.因此,在每个sink运行周期内,各 sub-sink点所能发送的最大数据量是固定的.另一方面,sub-sink所发送的数据主要来自于成员节点,故各 sub-sink所包含成员节点的数量决定了其所缓存的数据量的大小.实际缓存数据量和所能发送最大数据量的比较将直接影响到移动sink点单个周期内的数据采集量.也就是说,图1中系统数据采集量与各 sub-sink所包含的成员节点数量有关,可以通过调整成员数量来提高数据采集量.另一方面,成员节点数量将影响网络中的数据流向,从而直接影响网络整体能耗.本文所关心的是如何控制成员数量,即如何优化成员节点在各sub-sink点之间的分配使得在最大化系统数据采集量的同时能够尽可能地降低能耗.文献[6,7]中提出最短路径树SPT方法去选择sub-sink点.在SPT中,各成员选择距离其跳数最短的sub-sink作为目的,成员采集的数据沿着多条源于各 sub-sink的最短路径树向树根发送或中继.显然,SPT方法能够最小化全网能耗,但SPT中的sub-sink选择标准仅仅根据跳数信息而不考虑各sub-sink点的数据发送能力,因而可能会造成sub-sink的成员数量与其数据发送能力不匹配.例如,某些sub-sink 点与移动sink的通信时间较长,但其成员数量较少,导致没有足够的数据可以发送;而另一方面,某些sub-sink点的通信时间很短,但成员数量很大,导致无法完全发送缓存的大量数据信息.此外,大量数据流向“饱和”的节点还会导致网络能耗的不均匀,缩短网络生存时间.图2给出了SPT算法的运行结果.图2(a)中,SPT仅仅能够采集到大约理论最大值一半的数据量.图2(b)给出了图2(a)中在150个节点的情况下,各sub-sink点所含成员数量与最小成员需求量的比较,而后者则是根据各 sub-sink点的最大数据发送能力计算得到.从前面的分析可知,如果最小成员需求量无法满足,将导致移动sink通信时间的浪费和数据采集量的减少,例如图2(b)中的sub-sink 12.总之,SPT方法虽然能够有效降低能耗,但是由于数据采集效率较低,因而导致能耗利用率低下.Fig.2 Performance evaluation of shortest path tree algorithm图2 SPT算法性能评价2 最大数据量最短路径问题本文的主要目标是,针对sink移动轨迹固定的无线传感器网络,综合考虑数据采集量和能耗两项技术指标,提出一种优化的sub-sink选择机制,提高系统能耗利用率,具体包括两个优化目标:(1) 系统数据采集总量最大化;(2) 在目标(1)的基础上系统整体能耗最小化.为便于表述,用ntotal表示传感节点总量,nss和nmember分别表示sub-sink数量和成员数量.很显然,2.1 数据采集总量最大化系统数据采集总量 q由来自各 sub-sink的数据量组成,即 q =q.其中, n 表示选择 sub-sink itotaltotal ssissi作为目的的成员节点数量.对于任意 sub-sink i,实际所发送的数据总量 q s si取决于其缓存数据量与最大发送数据量之间的比较,如公式(1)所示:公式(1)中,dt和ds分别表示数据传输速率和数据采集速率.t为sink点的运行周期,isst 表示sub-sink i与sink点的通信时间长度.公式(1)中,除 issn 外的所有参数都是固定不变的.因此,系统数据采集总量最大化的充分必要条件为公式(2)表明,只要各sub-sink点的成员数量不小于最小成员需求(minimum requirement,简称 MinReq),则移动sink就可以采集到理论上的最大数据量.2.2 系统能耗最小化在传感器网络研究中,first radio order能耗模型[18]经常被用于计算节点发送和接收能耗.在first radio order能耗模型中,节点发送能耗与传播距离的平方成正比.本文不考虑功率控制问题,假定所有节点采用固定的发射和接收功率,节点能耗与节点之间的实际距离无关.为此,本文采用公式(3)所示的简化能耗模型,该模型已在相关文献[19]中被用于计算能耗.在公式(3)所表示的能耗模型中,节点总能耗p由接收和发送的数据总量kr和kt来决定.e为常数,表示发送和接收单位比特数据的能耗.在移动sink单个运行周期内,任意节点i接收数据量和发送数据量之间的关系为= + q ,q表示节点i在单个运行周期内所采集到的数据总量.根据假设(5),所有成员节点沿着最短路径向其所属的sub-sink点发送数据,故可以得到全网所有节点接收数据总量与跳数之间的关系,见公式(4):公式(4)中,hi表示节点 i到其所属 sub-sink点的最短跳数.如果节点 i为 sub-sink,则 hi为 0.根据公式(4),可以将单轮系统总能耗ptotal表述为最小跳数和的形式,如公式(5)中,pi为任意节点 i的单轮总能耗.根据公式(5),系统总能耗最小化问题等价于全网节点距离其所属sub-sink点跳数和最小化问题.2.3 最大数据量最短路径优化问题第2.1节和第2.2节分别对达到能耗最小化和数据量最大化两个优化目标的条件进行了分析,这里给出如下最优化问题描述:目标函数满足约束条件:优化目标函数(6)最小化最短跳数和,也意味着全网整体能耗最小化.约束条件(7)将确保移动sink点数据采集量最大化,而约束条件(8)则对各sub-sink点成员数量的总和进行约束.上述最优化问题可以描述为:寻找最佳的成员分配机制或sub-sink选择机制,建立各成员与sub-sink之间优化的一一映射关系,使得在确保系统数据采集量最大的前提下最小化全网整体能耗.因此,该最优化问题称为最大数据量最短路径问题 MASP(maximum amount shortest path).根据前述假设,在MASP中,各成员必须且仅能选择一个sub-sink作为目的,且各sub-sink点对所含有的成员数量有下边界约束.根据这一特征,为了便于求解,可以将MASP问题转化成0-1整数线性规划问题.• 矩阵A(nmember×nss):由 aij元素组成(i=1,…,nmember,j=1,…,nss).aij为二进制变量,aij=1表示成员 i选择sub-sink j作为目的;aij=0表示sub-sink j不是成员i的目的;• 矩阵H(nmember×nss):由 hij元素组成(i=1,…,nmember,j=1,…,nss).hij表示成员节点 i到 sub-sink j的最短跳数.目标函数满足约束条件:新目标函数(9)等价于目标函数(6).约束条件(10)确保每个成员必须且仅选择一个sub-sink,约束条件(11)确保各sub-sink的成员数量大于最小需求量MinReq.约束条件(12)与前述的假设条件(4)一致,即考虑高密集型网络,成员总量大于最小需求量的总和.关于节点密度较低的网络,即成员总量小于最小需求量总和的情况将在后面进行讨论.3 基于遗传算法和局部搜索的启发式算法最优化问题(9)是一类广义指派问题,而广义指派问题是一类 NP-完全组合优化问题[20].遗传算法是一种有效解决组合优化问题的启发式算法.本文利用遗传算法的基本原理,结合局部搜索的优势,给出了集中式 MASP问题解法,实现了成员数量的最优分配.3.1 染色体编码与初始群体生成遗传算法中常用的染色体(chromosome)编码都是一维编码.在目标优化函数(9)中,解的形式是nmember×nss二维矩阵.为了便于表述和计算,这里采用解的原始形式作为染色体编码方式,即二进制二维编码方式.图3给出了染色体二维编码的实例.图3左图为一个简单网络拓扑,S1,S2,S3表示3个sub-sink点,n1～n10表示10个成员节点.Sub-Sink点内的数字表示最小成员需求量MinReq,成员节点内的数字表示其所选择的sub-sink编号.对应左图的sub-sink选择结果,可以得到右图二维染色体编码格式.首先,通过为所有成员节点随机选择一个 sub-sink点作为目的,随机产生 N个初始个体组成初始群体(population).初始群体内的个体将满足约束条件(10),但很可能不满足约束条件(11).因此,初始群体有可能包含一系列不可行解.在遗传算法设计中,首先需要将初始群体的不可行解进化为可行解,然后在此基础上进一步提高种群内染色体的质量,从而达到最优.根据染色体编码规则,初始群体中的每个个体是一个nmember×nss二维矩阵Al(l=1,2,3,…,N),这里用lija(i=1,…,nmember,j=1,…,nss)表示矩阵Al的元素.Fig.3 An example for representation of individual’s chromosome图3 种群个体染色体二维编码实例3.2 适应函数与不适应函数适应函数的定义通常综合考虑目标函数和个体不可行度,当个体为不可行解时,给予适应值一定的惩罚.这里,采用将目标函数值和个体不可行度分开处理的方式,分别定义适应函数和不适应函数用于计算个体的适应值(fitness)和不适应值(unfitness),如公式(13)、公式(14)所示.可以看出,适应函数与目标函数(9)相同,反映最短跳数之和,适应值较小的个体较优.不适应函数反映了当前解的不可行度,即当前解偏离可行解的程度.不适应值越小,说明当前解越接近可行解.3.3 种群选取与交配规则关于种群选择,采用随机联赛选择模型,从当前群体中随机选择两对个体,每对个体中适应值较小的个体被选为双亲之一,用于交配生成子代个体.适应值是种群选择的唯一标准,而不适应值将被用于双亲交配过程去提高子代基因的质量.遗传算法中交配规则通常会选择一个或多个交配位,然后对换各交配位之间的基因以获取更高质量的子代.本文采用二维染色体编码,为了确保子代个体继续满足约束条件(10),这里采用逐行交配的模式.交配算法见表1.Table 1 Crossover operator based on unfitness value for each member i表1 基于不适应值的交配规则(对任意成员i)1 Initialize temporary variables 12,,...,ssn v v v to be zero.2 For j=1 to nss, 1 2 AND v a a=PP j ij ij 3 If 1 1∑4 1, 1,2,...,n k vss= =k=7 1= =5 Else 6 1 a a j n C P ij ij ss a a= with possibility 2 1 2( )/( ( ) ( )), 1,2,...,C P ij ij uf A uf A uf A j n p p +p ss=8 End If a a= with possibility 2 1 2( )/( ( ) ( )), 1,2,...,C P ij ij uf A uf A uf A j n p p +p ss在表1所示算法中,矩阵AP1,AP2和AC表示两个父代个体和一个子代个体,分别由元素 ,和构成.临时变量 v 1, v 2 ,...,vn s s用于存储父代个体之间逐行交配的临时信息.算法1中,AND为二进制变量的逻辑与运算符.对任一成员,如果两个父代个体的sub-sink选择相同,则子代个体将继承双亲的选择;如果父代的sub-sink选择不同,则不适应值较小的父代将以较高的概率被继承,从而有利于寻找可行解,提高子代基因质量.图4给出了交配过程的一个实例.图4中,父代1具有较低的不适应值.根据算法1,子代个体继承父代1较多的特点,因此看起来“更像”父代1.在变异过程中,随机选择两个成员并交换其 sub-sink选择,既保证子代个体满足约束条件(10),又完成基因的变异.Fig.4 An example of crossover operation图4 交配规则实例3.4 局部搜索增强算法为了进一步提高子代个体基因的质量,本文采用基于局部搜索的增强算法来降低子代个体的适应值和不适应值,从而缩减遗传代数,加速遗传算法的运行.局部搜索增强算法共分两个阶段:阶段1用于降低子代个体的不可行度,有助于寻找可行解;阶段2则用于降低目标函数值,有助于寻找最优解.阶段1. 基本思想是将部分成员从某些“饱和”sub-sink点转移到“饥饿”sub-sink点.遍历所有sub-sink点j,如果最小成员需求量MinReq没有被满足,则按照j+1,…,nss,…,j−1的次序选择一个成员数量大于MinReq的sub-sink点s,然后在s 所含的成员中随机选择一个成员t,将t的sub-sink选择从s切换到j.阶段2. 基本思想是让选择“饱和”sub-sink点的部分成员重新选择距离其最近的sub-sink点.遍历所有成员节点 i,如果其当前sub-sink点si的最小成员需求量 MinReq被满足,且si不是距离成员i最近的sub-sink,即h i s i ≠min(, j = 1 ,2,...,nss ,则成员i 将放弃si,选择距离其跳数最短的sub-sink作为目的.3.5 群体更新与算法终止条件每一代双亲交配后,根据如下规则更新当前群体:• 如果子代个体与当前群体中某个体相同,则丢弃子代个体;• 如果当前群体包含不可行解,且子代个体的不适应值小于当前群体中的最高不适应值,则更新群体;• 如果当前群体不包含不可行解,且子代个体的适应值小于当前群体中的最高适应值,则更新群体.算法终止条件为:循环执行第3.3节～第3.5节的步骤,直到产生Cstop个不同的子代个体为止.图5总结了上述基于遗传算法的整体流程.Fig.5 Solution based on genetic algorithm (CS: child solution)图5 遗传算法整体流程(CS:child solution)3.6 算法复杂度分析在图 5所示的算法整体流程中,局部搜索增强算法之外的步骤均比较简单,因此,算法每次循环操作的整体复杂度取决于局部搜索增强算法.其中,阶段 1的时间复杂度为O ( n m ember),阶段 2的时间复杂度为O( n ss nm ember ),故遗传算法单个循环全部操作的时间复杂度为 O ( nm ember).值得注意的是,上述分析基于最坏情形(worst case)来考虑.算法实际执行过程中,随着遗传代数的增加,当前群体中的不可行解数量减少,阶段1的处理必然加快.当群体全部由可行解组成时,就没有必要执行阶段1的增强处理了.4 基于MASP的数据采集通信协议考虑到移动sink能量资源、存储资源和计算资源不受限制,数据采集通信协议中复杂的集中式优化计算将由sink点完成.通信协议主要分为两个阶段:初始化阶段和数据采集阶段.4.1 初始化阶段初始化阶段主要用于获取全网拓扑信息、选择sub-sink节点、为各成员节点指派sub-sink等.完成上述任务,需要移动sink点运行3个周期,即3轮.1) 第1轮首先,定义广播消息帧格式:Broad_Msg{type,srcNetwAddr,hop},用于选择 sub-sink和建立最短路径树.第 1轮中,移动sink点不断广播type为0的Broad_Msg{0,0,0},所有接收到该消息的节点被自动选择为sub-sink点.Sub-Sink 点广播type为1的Broad_Msg消息,其他成员节点会继续广播该消息,用于建立多个以sub-sink为根的最短路径树.Type为1的Broad_Msg中,srcNetwAddr 为树根sub-sink的地址,hop为节点距离其当前最短路径树树根sub-sink的跳数.表2给出了第1轮中sub-sink选择和最短路径树建立的具体算法.Table 2 Algorithm of sub-sink selection and SPTs setup at any node表2 sub-sink选择及最短路径树建立算法(对任意节点)1 Initialize the routing table 2 While TRUE do 3 Listen for packets;4 If ReceiveBroad_Msg{0,0,0}5 Be selected as a sub-sink;6 SendBroad_Msg{1,SNA,0} //SNA is the network address of current node 7 Else If Receive Broad_Msg{1,srcNetwAddr,hop}8 Lookup routing table with destination srcNetwAddr;9 If no corresponding route item 10 Add new item to the routing table{Destination=srcNetwAddr,Metric=hop+1}11 BroadcastBroad_Msg{1,srcNetwAddr,hop+1}12 Else If Metric＞hop+1 13 Update route item with new metric Metric=hop+1 14 Broadcast Broad_Msg{1,srcNetwAddr,hop=1}15 Else 16 Ignore current broadcast message 17 End If 18 End If在表3所示算法运行结束后,所有节点获得了距离各sub-sink的最短跳数信息,并将相关信息发送给对应的sub-sink点,后者将于第2轮将最短跳数信息发送给移动sink点.此外,第1轮中各sub-sink点需要记录移动sink点首次进入及最后离开其通信范围的时间.对于移动 sink而言,起点到终点的正向移动与反向过程是完全对称的.所以,这里仅需要记录sink正向移动过程的通信时间即可.2) 第2轮Sub-Sink点将第1轮中收集的最短跳数信息及通信时间信息发送给移动sink.根据这些信息,移动sink将计算分配给各sink点的通信时间.在节点密集分布的场景中,sub-sink与移动sink的通信时间可能会发生重叠,即同时存在两个及以上的sub-sink位于移送 sink的通信范围内.这里采用一种简单的切换方法来分割重叠时间,即一旦有新的 sub-sink进入移动 sink点通信范围,则移动点立即断开与当前sub-sink的通信,开始与新sub-sink通信.通信时间计算完毕后,移动sink点将运行MASP算法为各成员节点选择优化的sub-sink点.这里,通信时间计算和MASP计算都由计算和存储能力较强的移动sink点在离线(off-line)状态下完成.故即使遗传算法的计算时间可能稍长,也不会对系统整体性能造成影响.3) 第3轮移动sink点通过广播消息将第2轮的计算结果扩散到网络中,广播消息由一系列成员节点和sub-sink点之间的匹配关系列表构成.每个接收到该广播消息的节点将获得其目的 sub-sink信息,然后该节点将删除广播消息中与自身相关的条目并继续广播,从而完成sub-sink优化选择结果在全网的扩散.4.2 数据采集阶段初始化结束后,全网节点连续采集数据并沿着初始化阶段建立的最短路径树向目的sub-sink发送.考虑到节点故障或新节点加入造成的网络拓扑变化,当某些节点无法成功地将数据发送给 sub-sink时,可以采用现有的按需路由协议[21]帮助其获得跳数距离最近的可用sub-sink作为临时目的.各sub-sink在移动sink点到来之前缓存其自身及来自其成员节点的传感信息.如前所述,在移动sink和sub-sink的通信中,新sub-sink总是具有较高优先级.为确保各成员之间信息量的均衡,sub-sink则采用轮盘赌方式[6]向移动sink发送数据.第3节的遗传算法是一种离线集中式算法,无法实时感知网络拓扑的动态变化.当sub-sink发生变化或成员信息发生变化时,MASP的计算结果将随之失效.考虑到初始化阶段中的复杂计算均由功能强大的移动 sink点完成,故可以通过周期性重复初始化阶段使MASP感知系统发生变化,而不影响系统性能.5 基于低密度网络和多个移动sink点的功能扩展5.1 支持低密度网络网络节点密度是一个相对的概念,没有绝对的定义.为了方便起见,这里将成员数量与各 sub-sink点最小成员需求量 MinReq之和的比较作为衡量网络节点密度高低的分界线.如果成员数量不少于最小需求量之和,则认为是高密度网络;反之,为低密度网络.前面有关 MASP问题的分析与解法均基于高密度网络.在高密度网络中,由于成员数量过大,单个运行周期内所有节点采集的数据总量要大于移动sink点数据采集量的上限,因此总会存在一部分数据无法被传送到移动sink点.然而在低密度网络中,由于成员数量小于最小需求量之和,移动sink点有可能收集到全部节点采集的数据,使得数据采集量最大化.在低密度网络中,sink点数据采集量最大化的充分必要条件将不再是不等式(2),而是必须确保每个 sub-sink点的数据缓存量不超过其数据发送能力的上限.因此,第2.3节中最优化问题的约束条件(11)和约束条件(12)需要修改为根据约束条件(15)和约束条件(16),可以得到一个新的 MASP最优化问题.为便于区分,将高密度网络中的MASP标记为MASP-HD,将低密度网络中的MASP标记为MASP-LD.第3节中给出的遗传算法依然可以用于求解 MASP-LD问题,但需要作相应调整,例如不适应函数的定义需要修改为公式(17).此外,局部搜索增强算法也应作类似调整,受篇幅所限,这里不再赘述.5.2 支持多移动sink点多移动 sink点能够有效解决因网络规模扩大引起的可扩展性问题.在本文所述的应用环境中,可以引入多个移动sink点来提高网络整体性能,如提升数据采集量、降低网络能耗等.在MASP中,移动sink点与sub-sink点进行直接通信,而成员节点则仅仅需要选择适合的sub-sink点并连续不断地将所采集的传感信息传送到相应的sub-sink点.也就是说,对于众多成员节点而言,移动sink点是一个“透明”设备,成员节点无须了解移动sink点的数量信息和位置信息.据此,本文提出的MASP数据采集方案可以直接应用于多移动sink点的应用场景,具有良好的可扩展性.值得注意的是,在多个移动 sink点沿着不同固定轨道移动的环境下,随着 sink点数量的增加,网络中的sub-sink点也会增加,而最小成员需求量之和也会随之增加.由于节点总量固定不变,因此,随着sink点的增多,网络节点密度可能会发生相对变化,即可能会从高密度网络转变为低密度网络.在实际应用中,需要关注网络节点密度的相对变化,如果成员数量小于最小需求量之和,则使用 MASP-HD 方法;反之,则使用MASP-LD方法.6 性能仿真本节采用OMNET++和MATLAB构建仿真平台,对所提遗传算法和MASP机制进行性能分析.仿真环境主要参数设定为:传感器节点均匀随机分布在矩形监测区域内,sink点以 5m/s的速度匀速移动;sub-sink与移动sink之间的数据传输速率为20kb/s;在数据采集阶段,各节点在sink点运行周期内以200b/s的速度进行连续数据采集,同时将传感信息即时发送给相应目的 sub-sink点;考虑同构网络,所有节点具有相同的初始能量 20J和相同的最大通信距离52m;能耗模型(3)中的常量e设为0.5μJ/bit.6.1 遗传算法性能评估遗传算法终止条件中的Cstop设为5 000,初始种群个体数量大小N设为100.表3给出了不同网络规模下的遗传算法性能比较结果,同一网络规模下反复实验20次.。