文章快速检索  
  高级检索
WSN中基于迭代局部搜索的Mobile Agent路径规划方法
屈应照, 胡晓辉    
兰州交通大学电子与信息工程学院, 甘肃 兰州 730070
摘要: 无线传感器网络中,相对于传统上广泛使用的C/S计算范式,基于Mobile Agent的计算范式展示出强有力的生存优势.因此,Mobile Agent作为一种分布式中间件技术,已经成为无线传感器网络中高效地自主性数据融合和能量均衡研究领域的热点.由于Mobile Agent的访问路径很大程度上影响数据融合的性能和系统能量开销,所以,确定一个有效的Mobile Agent访问路径是一件颇有意义的研究.本文提出一种新的路径规划方法,采用迭代局部搜索的算法获取Mobile Agent对节点区域的访问路径;同时考虑了Mobile Agent迁移时数据负载,中间节点转发数据时实际的能量开销以及对相邻路径节点的利用.通过仿真实验分析表明本文提出的方法在能量消耗、服务时间方面优于现有的一些多路径规划方法.
关键词: 无线传感器网络     数据融合     移动代理     多路径规划     迭代局部搜索    
Itinerary Planning of Mobile Agent Based on Iterated Local Search in Wireless Sensor Network
QU Yingzhao, HU Xiaohui    
School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
Abstract: Compared with the client/server computing paradigm, which is traditionally widely used, the computing paradigm based on mobile agent provides many powerful advantages in wireless sensor networks. Therefore, the mobile agent as a distributed middleware technology is the subject of this research for efficient automatic data aggregation and energy balance in wireless sensor networks. As the mobile agent's itinerary greatly influences the performance of data aggregation and the overall energy consumption, creating an efficient mobile agent's itinerary is meaningful. Thus, a novel itinerary planning is proposed in this paper. This approach uses iterated local search algorithm to plan a visited itinerary for every mobile agent. This schedule not only takes into account the data loading and actual energy consumption when the mobile agent traverses some intermediate nodes and forwards data by these nodes, but it also makes full use of some nodes from a disjoint itinerary to minimize the overall itinerary cost. Simulation experiments show that this proposed approach performs better than other existing multi-itinerary approaches in terms of energy consumption and service time.
Key words: wireless sensor network (WSN)     data aggregation     Mobile Agent     multi-itinerary planning     iterated local search    

1 引言

近年来,无线传感器网络(wireless sensor network,WSN)引起许多学者极大的研究兴趣. WSN是由一些能量和资源受约束的微型传感器节点组成,这些节点采集其监测区域的环境信息,并通过单跳或多跳的无线通信方式形成一个自组织网络系统,利用节点间协作的方式将采集数据传输给基站(或Sink节点).由基站进行集中分析处理并将处理结果通过Internet和卫星等通信方式反馈给远程用户终端. WSN网络结构图如图 1所示.

图 1 无线传感器网络结构图 Figure 1 The structure of wireless sensor networks

协作信息处理方式是WSN最重要的特性之一,它允许联合多个源节点采集的数据进行集中处理.因而,在节点进行数据传输前,根据WSN具备协作信息处理的特性可以利用节点间数据存在高度的时空相关性,使用数据融合技术来减少网络中数据冗余,进而减少网络数据传输量,从而延长了网络的生命周期.针对协作信息处理方式,一些基于分布式计算范式的方法陆续被提出,如:基于Client/Server(C/S)的方法[1]、基于Mobile Agent的方法[2-3]等.

基于C/S的计算模型是WSN中应用最广泛和普遍的分布式计算模型[1].但是,C/S的计算模型存在许多弊端:

(1) 该模型有很大的数据传输量,因而需要较高的带宽资源.

(2) 由于各个节点同时给基站发送数据,而基站只能按顺序接收数据,所以这种模型能量消耗高、网络延迟大.

(3) 靠近基站附近的节点由于高负荷的工作,需要消耗更多的能量,进而导致这类节点过早的失效,从而网络性能、生命周期大幅度降低.

此外C/S模型存在着规模性、可扩展性问题以及对高复杂度计算能力的需求.

针对C/S计算模型存在的问题,文[3]提出一种基于Mobile Agent的分布式计算模型并应用在WSN数据融合和高效节能方面. Mobile Agent (MA)是一段可以在网络节点间自主运行的智能性程序代码,它承载着用户指定的任务,在每个被访问的节点进行局部地数据收集、融合处理;以这种方式遍历网络相关节点完成指定任务,携带任务结果返回基站,基站将结果进一步处理并反馈给用户.将移动Agent应用于分布式系统中,具有降低网络负载、自治执行、动态适应、平台无关等优点[4].综合文[5-6]所述,MA有4个主要组成部分,即:代理标志、指令代码、数据空间和访问路径.其中,访问路径决定MA遍历网络时对节点的访问次序及相应的系统开销;因此,访问路径的优劣对整个网络的数据融合性能和能量开销有着重要的影响.但是,确定MA的最优访问路径是一个NP难问题[7].所以,学者们陆续将一些启发式思想方法应用在MA的访问路径规划上,试图寻找关于MA访问路径的次优解,以此达到提高系统的数据融合性能;同时,使网络能量开销尽可能的低.这些启发式思想方法,既有动态的路径规划方法;也有静态的路径规划方法[8].其中,动态路径规划方法比较适合应用在一些移动对象的路径踪迹在初始状态下是未知的,例如:目标追踪、分类器应用等;静态路径规划方法比较适合应用在周期性采集其监测物理环境状态信息并传输给基站,例如:在数据监测方面的应用.

动态路径规划方法对MA迁移路径在发生改变时可能发生的错误做出实时的反应;但是,动态确定MA下一个将要访问的节点时需要较多的决策时间;它同时还会消耗更多的能量,并且对MA的容量需求更大(因为MA智能性越高,其对MA的功能需求就越多).另外,动态规划方法还需要一个有效的路由协议,以便MA不仅可以动态确定其下一个将要访问节点还可以确定其返回到Sink节点的路径;这些问题对于静态路径规划方法都是非必需的.因为在静态路径规划方法中,MA都是使用预先确定的路径;这些路径都是由Sink节点在派发MA之前,根据网络状况和先验知识条件计算而确定的.

静态的路径规划方法根据网络并行派发MA的数量可分为:(1) 单路径规划方法(single-itinerary planning,SIP)[8],(2) 多路径规划方法(multi-itinerary planning,MIP)[8];如图 2所示. SIP在小型WSN网络中,性能表现出令人满意的结果;但是,随着WSN中节点数量的增加,SIP的性能状况开始恶化.因为当MA沿着其访问路径进行收集和融合源节点的数据时,MA的往返时延和能量开销也随着网络规模增加而急剧上升[2, 8].同时,随着网络节点数量的增加,MA收集数据的规模也逐渐增加,进而增加网络的带宽资源及能量开销.此外,SIP方法还可能会产生其他隐患问题,例如:MA在几个节点之间的迁移时,会发生MA丢失现象[9-10].然而MIP通过派发多个MA到网络中并行收集、融合源节点的数据;由于每个MA被分配一个节点数量较小的节点子集,因而在一定程度上有效地缓解了SIP方法在网络规模增大时产生的一系列隐患问题.

图 2 Mobile Agent的静态路径计算模型图 Figure 2 The computation model of static path on Mobile Agent

所以,基于MIP理论的研究是一项颇有意义的工作.文[10]提出一种基于访问中心位置的算法(visiting center location,VCL),它是把每个源节点的影响因子分散到其它的源节点上,通过计算每个节点累计的影响因子,影响因子值最大的节点就选为中心位置;然后将所有位于特定距离节点的划分到以此中心点的簇中.但是,在实际网络环境中由于应用环境条件的限制,节点通常是无规律性分布,这种情况下该算法中簇的划分将大幅度受影响,进而影响算法效率;所以这种算法不具备一般性的应用.另外,由于该算法中根据一个特定距离值将节点划分为簇,因此,这个特定距离值的大小也会影响该算法的性能;并且这个特定距离的最优值很难通过计算得到或者通过精确定量分析得到.

文[11]提出一种基于平衡的最小生成树算法(Balanced minimum Spanning Tree,BST),它使用Prim算法产生一棵根源于汇聚节点的最小生成树,在这棵生成树中所有单分支的节点被划分为同一个簇.由于它采用贪心策略,所以,需要参数因子α来实现能量开销和任务延迟的均衡.

文[12]提出一种次优路径(the near optimal itinerary design,NOID)算法,它主要是确定网络中完成用户指定任务所需MA数量最优值,并且该最优值可以最小化网络数据融合的开销;同时采用最小生成树产生MA的次优访问路径.但是,NOID算法面临着较慢的计算速率和高复杂度的计算过程.文[2]基于NOID算法存在的上述问题提出一种基于树的路径(the tree-based itinerary design,TBID)算法,采用贪婪式算法思想将Sink节点为中心的节点区域划分成多个同心圆,由内到外选择距离最小的节点形成一个二叉树.但是,MA完成任务并返回Sink节点的路径开销翻倍,并且算法性能还面临着树中大量分支的干扰和影响.

文[13]提出一种EMIP算法,该算法的网络拓扑结构构造方法与文[10]的构造方法相似.即:以Sink节点为圆心,节点最大传输范围为半径的圆形区域Z,区域内节点将成为每条访问路径的头节点.然后以参数θ=2π/N(NZ区域中节点总数量)的圆形扇区将整个网络区域进行分簇,每个簇使用SIP方法规划MA对其簇的访问路径.

现有基于MIP方法的一些算法,存在以下几方面问题:

(1) 一般情况下假定MA的存储空间为常量值,MA由Sink节点派发,沿着其访问路径进行数据收集并返回到Sink节点.但是,当MA的访问路径较长时,MA由内向外遍历节点进行数据收集,MA装载的数据量逐渐增大,则增加了MA迁移时往返数据负载及系统能量开销.

(2) 很多相关研究中,都预设MA在一对节点间迁移时能量开销与节点间迁移距离成正比.然而,实际环境中这种预设存在逻辑矛盾.例如:(a)由于节点对的物理距离超出其最大传输范围,需要经过若干个中间节点转发才能实现此对节点之间的通信.此时MA迁移距离要明显大于两节点物理距离. (b)在一个相对稀疏的节点区域,节点(uv)之间有两条路径d1d2,其中d1 < d2,但是路径d1的跳数是路径d2的多倍.由于中间节点在转发数据时需要消耗能量,很明显MA在路径d1迁移时能量开销高于路径d2的能量开销.

(3) 在基于树的算法中,给树的每个分支派发MA执行数据收集时,MA遍历树分支的访问路径一般情况下都是按着树的后序遍历方法产生.如图 3所示,基于树结构的路径算法,T1就是传统上MA都按着树的后序遍历:BGFDEC,进行数据收集.其中节点B、G虽然在MA访问路径序列是相邻的,但是在树结构上需要5跳才能实现两者间的通信.因此,如果按着树的后序遍历进行数据收集,MA需要装载着B节点的数据经过5次中间节点的转发才能到达G节点,进行后续数据收集,这无疑增加了网络能量开销.如果将节点B作为MA路径上最后的访问对象,或许更为恰当,如图 3中T2所示.

图 3 基于树结构的路径规划算法示例图 Figure 3 The itinerary planning algorithm based on tree structure

针对上述存在的问题,本文提出的方法是基于迭代局部搜索(iterated local search,ILS)的启发式方法[14],该方法广泛用于解决离散优化问题. ILS每次从不同的初始条件开始,对一个局部搜索程序反复进行改进,以此获得一个改良的次优解;受文[14-15]思想启发,本文将ILS方法应用到WSN中MA的路径规划.本文提出的方法强化了现有一些MIP算法存在的缺陷.首先,本文方法充分地考虑了MA在网络上迁移时数据负载问题.其次,在计算MA在节点间迁移实际的能量开销时,兼顾了中间节点进行数据转发的能量开销.最后,本文并非按着传统的MA路径规划方法,即:① 对源节点集合进行簇的划分;② 对每个簇中MA,构建其访问路径;为了使所有MA的访问路径开销临近最小值,本文将上述两项操作流程在算法的执行阶段统一进行,最终节点均被划分到相应的MA访问路径上.

2 算法描述

MA访问路径规划确定MA在WSN中的访问节点集合及先后顺序,要求以较小的系统代价满足较好的应用性能,是WSN中有效实施MA机制的核心问题之一[16].通常情况下,可以用一个完全图G=(VE)来表示无线传感器网络的结构,V表示WSN中节点的集合;E表示WSN中任意节点对之间链路的集合,此处节点间链路可以是直接通信的链路也可以是间接通信的链路.每条链路都有一个权衡值,该数值是通过计算在此链路上转发1 bit数据所消耗的能量而得到.本文采用普通的融合模型,即融合率为f(0 < f < 1);例如:如果源节点采集数据量大小是d,则MA在前j个节点收集的数据量为jdf.

根据MIP理论可知,基于MIP思想产生若干条MA次优访问路径I={I1I2,…,In},这些路径消耗总能量Ctotal应该临近最小值,其中CtotalIcosti采用式(1)、(2) 计算得到.

(1)
(2)

其中,cj=cxy表示MA在节点对(xy)之间迁移时能量开销;s表示MA初始规模大小,即:主要包括MA指令代码和储存访问节点的ID号.此处需要注意的是,MA只在第一次遍历路径节点时携带自己指令代码,把那些需要频繁使用的代码存储到源节点本地;MA在进行下一轮采集时只携带发生变更的指令代码.所以,s可以被认为是一个极小的常量,甚至在很多情况下它可以被忽略.

2.1 系统能耗模型

为了分析本文算法的系统能量开销情况,本文所采用的能耗模型是Heinzelman[17]等人提出的一阶无线电模式.因而,访问路径上传输能耗看作是直接链接的节点间在发送和接收MA时产生的能耗,因为在WSN中节点间传输1 bit数据的能耗远远大于处理该数据的能耗[18-19];所以,通常路由协议研究中只计算节点间通信传输消耗的能量. 例如:第j个簇内,MA在节点a和节点b之间迁移时产生传输能耗采用式(3)~(5) 计算得到:

(3)
(4)
(5)

其中,k表示MA装载数据包的大小,单位为bit;Eelec表示节点在发送或接收电路产生的能耗;εamp表示节点发送中继器的信噪比;dab表示节点间的传输距离;Rmax表示节点最大的传输距离.

2.2 ILS-MIP算法

本文提出的方法是基于迭代局部搜索的MA多路径规划方法,简称为ILS-MIP,它同属于静态的路径规划方法.

ILS-MIP算法初始阶段,每个节点可以定位自己坐标位置,Sink节点(或基站)根据收集的此类信息计算节点间物理距离及确定节点间的通信功率标准;并构建网络拓扑结构,并给节点间的链路赋一个权衡值,此权衡值等于在节点间转发1 bit数据的能量开销;注意,此处链路链接是可以直接单跳通信的节点对.然后,Sink节点通过使用Dijkstra算法,得到一个关于节点间能量开销的二维矩阵,矩阵中任意两个节点间的通信能量开销是最小的;此处任意节点对是直接的单跳通信或者遍历若干个中间节点的间接多跳通信. Sink节点根据此二维矩阵信息,更新网络拓扑结构.从而最终得到n条访问路径I={I1I2,…,In},使得这些访问路径总能量开销临近最小值. ILS-MIP算法的流程示意图,如图 4所示.

图 4 ILS-MIP算法流程示意图 Figure 4 The flow diagram of ILS-MIP algorithm
2.2.1 ILS-MIP算法初始化阶段

首先,ILS-MIP以Sink节点为中心,以α·Rmax为半径,构建一个圆形子区域Z,该区域内的节点都可以与Sink节点进行单跳通信.其中,α是一个常数因子(0 < α≤1),Rmax是整个网络节点中最大的传输距离.子区域Z中节点数量直接决定了ILS-MIP算法产生的访问路径的数量k,即:|Z|=k,子区域Z中每个节点将成为每条MA访问路径的头节点.此阶段算法伪代码描述过程,如表 1所示.

表 1 ILS-MIP算法初始化的伪代码描述表 Table 1 Pseudo code description table for ILS-MIP initialization
2.2.2 ILS-MIP算法执行阶段

ILS-MIP算法完成初始化后,开始执行一个重复迭代的搜索过程,将子区域Z范围外的所有源节点都划归到MA在本阶段,ILS-MIP把满足如下条件SNy∈{V-Z}且attachedSNy=False的候选节点归附到MA访问路径上任意节点SNx上,检验是否满足使得归附后的访问路径能量开销Icosti(xy)最小.如果满足要求,则将此节点归附到该路径Ii节点SNy,并将attachedSNx=True;否则,继续检验该路径下一个节点,并重复此过程的检验,直到满足题设要求的最佳节点为止.

现有基于MIP的路径规划方法中,候选节点都是链接到当前路径的终端节点上;而在本文中,候选节点不仅可以链接到访问路径终端节点上,还可以插入到任何已经链接的节点对之间.关于此阶段算法伪代码描述,如表 2所示.

表 2 ILS-MIP算法执行阶段的伪代码描述表 Table 2 Pseudo code description table for ILS-MIP execution stage

为了更好地描述和说明本文ILS-MIP算法,本文在此给出关于ILS-MIP算法2阶段的一个简单实例.

图 5I所示,访问路径Ii上现有Sink节点及节点C、D;根据式(2) 得,此时访问路径Ii的能量开销:Icosti=s·cSink,c+(s+dfccd+(s+2dfcd,Sink,现有节点A、B是节点区域内暂时未归附到任何访问路径上,在ILS-MIP算法的执行阶段,将节点A、B依次插入到此条访问路径上任意可能的位置,使得插入后访问路径能量开销最小.由算法2知,将节点A插入到路径时有3个候选位置,分别是(Sink,C)、(C,D)、(D,Sink),如图 5 Ⅱ、Ⅲ、Ⅳ所示.在此3种情况下,访问路径的能量开销分别为

图 5 关于ILS-MIP算法执行阶段的示例图 Figure 5 Diagram of an example for ILS-MIP execution stage

根据ILS-MIP算法可知,节点A最终插入的位置X应满足,插入后所得新的MA访问路径在所有可能插入位置中能量开销最小,即:

同理可得,节点B的插入位置. ILS-MIP算法执行阶段最终的访问路径效果图,如图 6所示.

图 6 ILS-MIP访问路径的访问顺序示例图 Figure 6 Diagram of an example for ILS-MIP access itinerary

综上所述,本文提出的ILS-MIP算法主要流程:首先,Sink节点分别与Z区域的节点相连,以此获得一个初始的访问路径集合.然后,通过使用迭代局部搜索规则,逐渐将网络中剩余节点归附到MA各条访问路径上,从而访问路径逐渐地向节点区域外层延伸. ILS-MIP算法构建访问路径的策略有益于将相邻节点划归到同一条访问路径上;并且,为了使访问路径系统总开销尽可能小,本文中MA在到达其访问路径外层的节点后,按着由外层向内层的方向进行数据收集,并最终返回到Sink节点;从而可以减少MA迁移时数据负载和能量开销,如图 6中的路径节点访问顺序.

在实际网络环境中,当MA在一对节点间迁移,节点间物理距离超出其传输范围时;MA需要遍历相关中间节点且单跳距离应小于节点传输范围,才能到达目标节点.如图 6所示,在本文中,虚线指向的节点表示MA为了进行数据收集而必须遍历的中间节点,此类节点仅对MA进行接收和转发操作,MA不对其采集的数据进行收集和融合操作.实线指向的节点表示MA将对此类节点采集的数据进行数据收集、融合操作,并且此类节点负责对MA进行接收和转发操作.当Sink节点将访问路径分发给相应的MA时,清晰地区分路径中此两类节点.因此,ILS-MIP在计算MA在其访问路径迁移时能量开销,充分考虑了中间节点转发数据的能量开销.图 6中,路径I2上包含有路径I3上标号为15的节点,15号节点充当的是中间节点,它只对MA进行接收和转发,MA不会对此节点采集的源数据进行收集操作.在路径I3上,15号节点既是源节点又是中间节点,MA对其进行数据收集,同时它负责对MA接收和转发操作.

3 仿真及结果分析 3.1 仿真设置

本文采用CC2420无线模块模型组件在TinyOS[20-21]的仿真平台TOSSIM下,对TBID[2]、VCL算法[10]、EMIP[13]和本文提出的ILS-MIP算法进行仿真,并在能量消耗、服务时间两方面展开分析和比较.

MA规模主要是指令代码空间和数据空间,根据数据融合算法的不同,数据空间不断发生变化,而代码空间基本上保持不变.基于这种情况,本文MA仿真实现机制采用文[6]提出的方案:首先,将指令代码空间内容通过无线信道广播给网络中所有源节点,当MA到达相应源节点时,结合MA数据空间的数据以及源节点本地采集的数据进行相关操作,将最终处理结果存储到MA数据空间中.因此,可以大大减少网络节点重复转发MA代码空间的能量开销.

节点随机部署在200 m×200 m网络节点区域,其中Sink节点位于节点区域中心位置(100,100).其中,假定本实验环境中WSN网络模型具备以下几个特征:

(1) 节点具有定位功能,即:通过GPS或者其他方法获取其物理坐标.

(2) 节点部署以后不再发生移动,并且Sink节点有充足的能量供应.

(3) 每个节点都有唯一的标识符.

(4) 所有节点都有相同的初始电池能量.

(5) 网络中传输的所有单个数据包的大小是相同.

(6) 节点只有剩余能量感知功能[22-23].

MA在网络上迁移时采用尽可能低的传输功耗标准.本文仿真过程所用到的参数[10, 24]表 3所示.

表 3 仿真过程参数表 Table 3 The table of simulation experiment parameters
3.2 仿真结果分析

(1) 总能量消耗:它包括节点采集、处理、接收和发送数据的总能量消耗;以及包括中间节点转发MA所消耗的能量.如图 7反映了在包含300个节点且网络总能量为150 J的网络中,节点的总能量消耗与采集周期的变化关系.

图 7 节点消耗的总能量与采集周期关系图 Figure 7 The relationship between the total energy consumption of nodes and network′s acquisition cycle

图 7可以看出,TBID算法、ILS-MIP算法在能耗方面明显优于VCL算法、EMIP算法;并且,TBID算法与ILS-MIP算法在数据采集周期达到250轮后,能量消耗差距逐渐拉大;其中,ILS-MIP算法相对于TBID算法,能量消耗增长速率放缓并逐渐趋于稳定.主要由于:(a) ILS-MIP算法在能耗方面,综合考虑MA迁移时中间节点转发数据的实际能量消耗,使之成为能耗方面较为高效的算法. (b)并且,ILS-MIP算法在路径规划方面,候选节点可以插入到访问路径任何位置,这种节点插入方式不同于传统方法中候选节点仅可以插入到访问路径的终端节点,这样使得访问路径能量开销尽可能地临近最优值. (c)最后,ILS-MIP算法在确保MA迁移时路径开销尽可能小的前提下,规划MA的迁移路径,即:MA迁移路径中可能包含其它访问路径的节点作为中间节点;此方式不同于传统方法中MA只能在其访问路径节点集合中迁移.总之,ILS-MIP算法通过采用上述方法,在一定程度上将网络能量开销分散均衡,使得网络总体能量消耗降低,同时网络性能得到改善,从而网络的生命周期得以延长.

(2) 服务时间:图 8描述了任务服务时间与网络节点规模的变化关系.任务服务时间表示:网络中MA对其访问节点集合进行数据收集处理并返回到Sink节点的时间开销.即:Sink节点派发第一个MA开始至网络中最后一个MA返回到Sink节点所耗费的时间.此服务时间的计算同节点能量开销一样,相应地考虑了中间节点转发数据的时间开销.

图 8 服务时间与网络节点数量关系图 Figure 8 The relationship between service time and the number of network nodes

图 8中可以得到,在包含少于或等于200个节点网络中,VCL、EMIP、TBID和ILS-MIP此4种算法的服务时间相似.但是,如图 8所示在网络规模为300个节点时,EMIP的服务时间为45.3 s、TBID为41.9 s、VCL为39.9 s、ILS-MIP为31.1 s;并且,随着网络规模的逐渐增大,EMIP算法的服务时间明显高于其它3种算法,表明此算法的路径规模存在显著的差异进而造成数据负载不均衡.其中,TBID算法随着网络规模的增大,其服务时间开始显著低于VCL算法,证明其簇的划分方式在网络规模增大时,展现出一定的优越性.相对于其它3种算法,ILS-MIP服务时间的优越性越来越明显,并且逐渐趋于稳定范围.这是由于ILS-MIP算法计算得到关于所有MA的访问路径具有均衡的规模;在这样情况下,随着网络规模的增大,头节点集合区域Z的节点数量会相应增加,此时,网络中关于MA访问路径的数量也相应增加并且每个路径长度会越来越短.在MA的访问路径相对较短的情况下,MA的数据负载和访问延迟都相应地减小.但是,ILS-MIP在不同的数据融合算法下,验证其网络开销及性能是否趋于稳定以及求解与其匹配的最佳数据融合算法将是下一步进行研究和讨论工作重点.

4 结束语

本文基于MIP方法中现有一些算法存在的问题,结合迭代局部搜索理论——普遍用于解决离散优化问题的启发式方法,提出一种ILS-MIP算法.通过该算法计算和确定关于MA的次优访问路径集合,MA沿其访问路径遍历节点逐渐进行对节点采集数据的收集和融合处理. ILS-MIP相对于MIP中其它一些算法,存在以下几点特性:(1) 它综合考虑MA在网络中进行数据收集方式及MA的数据负载问题. (2) 它在计算MA在网络中迁移时的实际能量开销,充分地分析中间节点转发数据的能量开销. (3) 在进行源节点划分到访问路径时,候选节点可以插入访问路径的任何位置上,只要满足插入此位置后所得访问路径的能量开销比该路径其它位置的能量开销都小. (4) 在使得MA迁移时能量开销尽可能小的前提下,MA遍历的中间节点可能会包含其它路径上的节点.通过仿真表明,ILS-MIP算法性能在网络能量总开销、服务时间方面优于现有一些算法.在后续工作中,将对本算法在网络延迟、数据融合性能和安全性等方面进行研究和讨论,使得本算法具有更为有效的静态路径规划方案.

参考文献
[1] Xu Y, Qi H. Distributed computing paradigms for collaborative signal and information processing in sensor networks[J]. Journal of Parallel & Distributed Computing, 2004, 64(8): 945–959.
[2] Konstantopoulos C, Mpitziopoulos A, Gavalas D, et al. Effective determination of mobile agent itineraries for data aggregation on sensor networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(12): 1679–1693.
[3] Qi H, Xu Y, Wang X. Mobile-agent-based collaborative signal and information processing in sensor networks[J]. Proceedings of the IEEE, 2003, 91(8): 1172–1183.
[4] 张毅, 张秀梅, 陈炜, 等. 移动自组织网络中基于移动Agent的多约束QoS多播路由算法[J].信息与控制, 2010, 39(1): 47–53.
Zhang Y, Zhang X M, Chen W, et al. A multi-constrained QoS multicast routing algorithm based on mobile agent for mobile Ad Hoc network[J]. Information and Control, 2010, 39(1): 47–53.
[5] Chen M, Gonzalez S, Leung V C M. Applications and design issues of mas in wireless sensor networks[J]. IEEE Wireless Communications, 2008, 14(6): 20–26.
[6] 林华杰, 史浩山. 基于无线传感器网络移动代理变种在TinyOS中的实现[J].传感技术学报, 2007, 20(10): 2324–2327.
Lin H J, Shi H S. Implementation of mobile agent variation based on wireless sensor network in TinyOS[J]. China Journal of Sensors and Actuators, 2007, 20(10): 2324–2327.
[7] Chen M, Yang L T, Kwon T, et al. Itinerary planning for energy-efficient agent communications in wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(7): 3290–3299.
[8] Venetis I E, Pantziou G, Gavalas D, et al. Benchmarking mobile agent itinerary planning algorithms for data aggregation on WSNs[C]//2014 Sixth International Conference on Ubiquitous and Future Networks (ICUFN). Piscataway, NJ, USA: IEEE, 2014: 105-110.
[9] Mpitziopoulos A, Gavalas D, Konstantopoulos C, et al. CBID: A scalable method for distributed data aggregation in WSNs[J]. International Journal of Distributed Sensor Networks, 2010, 5(4): 1–13.
[10] Chen M, Gonzalez S, Zhang Y, et al. Multi-agent itinerary planning for wireless sensor networks[J]. Quality of Service in Heterogeneous Networks, 2009: 584–597.
[11] Chen M, Cai W, Gonzalez S, et al. Balanced itinerary planning for multiple mobile agents in wireless sensor networks[M]//Ad Hoc Networks. Berlin, Germany: Springer, 2010: 416-428.
[12] Gavalas D, Mpitziopoulos A, Pantziou G, et al. An approach for near-optimal distributed data fusion in wireless sensor networks[J]. Wireless Networks, 2010, 16(5): 1407–1425.
[13] Wang J, Zhang Y, Cheng Z, et al. EMIP: Energy-efficient itinerary planning for multiple mobile agents in wireless sensor network[J]. Telecommunication Systems, 2015: 1–8.
[14] Lourenço H R, Martin O C, Stützle T. Iterated local search: Framework and applications[M]//Handbook of Metaheuristics. Berlin, Germany: Springer, 2010: 363-397.
[15] Takada Y, Hu Y, Hashimoto H, et al. An iterated local search algorithm for the multi-vehicle covering tour problem[C]//2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). Piscataway, NJ, USA: IEEE, 2015: 1242-1246.
[16] 张亚明, 史浩山, 刘燕, 等. WSNs中基于蚁群模拟退火算法的移动Agent访问路径规划[J].西北工业大学学报, 2012, 30(5): 629–635.
Zhang Y M, Shi H S, Liu Y, et al. A better itinerary analysis for mobile agent(MA) through using ACA-SAA algorithm in wireless sensor networks[J]. Journal of Northwestern Polytechnical University, 2012, 30(5): 629–635.
[17] Heinzelman W. Energy-efficient communication protocols for wireless microsensor networks[C]//Proceedings of the Hawaii International Conference on Systems Sciences. Piscataway, NJ, USA: IEEE, 2000: 3005-3014.
[18] Singh M, Prasanna V K. System-level energy tradeoffs for collaborative computation in wireless networks[M]//System-Level Power Optimization for Wireless Multimedia Communication. Berlin, Germany: Springer, 2002: 113-131.
[19] Barr K C, Asanovic' K. Energy-aware lossless data compression[J]. ACM Transactions on Computer Systems (TOCS), 2006, 24(3): 250–291.
[20] Amjad M, Sharif M, Afzal M K, et al. TinyOS-new trends, comparative views and supported sensing applications: A review[J]. IEEE Sensors Journal, 2016: 1–1.
[21] 潘浩, 董齐芬, 张贵军, 等. 无线传感器网络操作系统TinyOS[M]. 北京: 清华大学出版社, 2011.
Pan H, Dong Q F, Zhang G J, et al. The operating system of wireless sensor network-TinyOS[M]. Beijing: Tsinghua University Press, 2011.
[22] 徐智勇, 袁凌云, 夏幼明, 等. 基于TinyOS 2.1无线传感网的能量监测模型设计与实现[J].传感器与微系统, 2011, 30(4): 99–101.
Xu Z Y, Yuan L Y, Xia Y M, et al. Design and implementation of energy monitoring model based on TinyOS 2.1 in wireles schsor networks[J]. Transducer and Microsystem Technologies, 2011, 30(4): 99–101.
[23] 杜永文, 冯珂, 练云翔. 无线传感器节点能量自主预测算法研究[J].微电子学与计算机, 2016, 33(12): 113–116.
Du Y W, Feng K, Lian Y X. Research on self-prediction algorithm of residual energy for WSN[J]. Microelectronics & Computer, 2016, 33(12): 113–116.
[24] 李致远, 毕俊蕾, 王汝传. 基于移动Agent的无线多媒体传感器网络QoS路由算法[J].传感技术学报, 2016, 29(7): 1032–1041.
Li Z Y, Bi J L, Wang R C. A QoS routing algorithm based on mobile agent for wireless multimedia sensor networks[J]. Chinese Journal of Sensors and Actuators, 2016, 29(7): 1032–1041.
http://dx.doi.org/10.13976/j.cnki.xk.2017.0296
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

屈应照,胡晓辉
QU Yingzhao, HU Xiaohui
WSN中基于迭代局部搜索的Mobile Agent路径规划方法
Itinerary Planning of Mobile Agent Based on Iterated Local Search in Wireless Sensor Network
信息与控制, 2017, 46(3): 296-303.
Information and Control, 2017, 46(3): 296-303.
http://dx.doi.org/10.13976/j.cnki.xk.2017.0296

文章历史

收稿/录用/修回: 2016-05-13/2016-07-19/2016-07-22

工作空间