无线传感器网络遗传—禁忌搜索移动代理测量调度方法.doc

第11期王晟等：无线传感器网络遗传禁忌搜索移动代理测量调度方法199无线传感器网络遗传禁忌搜索移动代理测量调度方法王晟，王雪，毕道伟（清华大学 精密仪器与机械学系 精密测试技术及仪器国家重点实验室，北京 100084）摘 要：提出一种基于遗传算法和禁忌搜索算法混合优化的移动代理测量调度方法，用于实现测量过程中移动代理派遣次序的优化调度。该机制综合考虑了各移动代理的产生时序、优先级和能耗等指标，在确保各移动代理有效执行的前提下，使代理派遣次序更合理。仿真实验表明，基于遗传算法和禁忌搜索混合优化的移动代理测量调度可以有效降低无线传感器器网络能耗和减少延迟，延长网络寿命，改善网络实时性和测量性能。关键词：无线传感器器网络；移动代理；测量调度；遗传算法；禁忌搜索中图分类号：TP393 文献标识码：B 文章编号：1000-436X(2008)11-0194-06Genetic algorithm-tabu search for mobile agents measurement scheduling in wireless sensor networksWANG Sheng, WANG Xue, BI Dao-wei（State Key Laboratory of Precision Measurement Technology and Instruments, Department of Precision Instruments,Tsinghua University, Beijing 100084, China）Abstract: A mixed strategy for mobile agents measurement scheduling in WSN was proposed, which was combined by genetic algorithm and tabu search. The proposed scheduling strategy takes the creation sequence, priority and energy consumption of mobile agents into consider, for reasonablely dispatching multiple mobile agents and ensuring the measurement performance of WSN. Simulation results demonstrate that the proposed algorithm can effectively arrange the order of mobile agents dispatching, where the energy consumption and time delay can be remarkablely decreased and the lifetime of WSN can be accordingly prolonged.Key words: wireless sensor networks; mobile agent; measurement scheduling; genetic algorithm; tabu search1 引言收稿日期：2008-06-21；修回日期：2008-10-15基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目(2006CB303000); 国家自然科学基金资助项目(60673176, 60373014, 50175056)Foundation Items: The National Basic Research Program of China (973 Program) (2006CB303000); The National Natural Science Foundation of China (60673176, 60373014, 50175056)无线传感器网络由大量无线传感器节点构成，布局灵活，在军事、工业、环境监测等多个领域存在广泛应用前景。传统无线传感器网络常采用客户端/服务器（C/S, client/server）模型完成测量任务。C/S模型通过集中式算法，由各传感器节点完成测量，在服务器中完成数据处理。虽然C/S模型应用广泛，但由于传输数据量大，且服务器运算负担过重，因此C/S模型无法满足无线传感器网络的测量需求。针对无线传感器网络特点，Qi等提出可以采用移动代理模型构建无线传感器网络1。移动代理是一种可在无线传感器节点间自主迁移的计算程序，具有移动性、自主性和协作性等特点2。采用移动代理，可减少数据传输，降低网络带宽和可靠性要求；此外，通过移动代理动态更新节点程序也能减少传感器节点的存储负担。相比于C/S模型，移动代理模型更适合于在能耗敏感、资源受限的条件下完成测量。移动代理测量调度是直接影响无线传感器网络能耗和性能的重要问题。目前，移动代理测量调度的研究很少涉及具体网络运行环境，无线传感器网络内的移动代理研究更少3。Wu等给出了移动代理在无线传感器网络中的传输模型4，Xu和Qi设计了无线传感器网络中移动代理的能耗和延时性能评价指标1，但这些指标都未考虑网络带宽对移动代理测量调度的限制。针对带宽限制问题，本文提出一种综合考虑移动代理产生时序、优先级和能耗的移动代理测量调度方法。该方法采用综合评价指标确保移动代理调度的能效性和实时性，并采用遗传算法（GA, genetic algorithm）禁忌搜索（TS, tabu search）混合优化方法实现对最优调度次序的规划寻优。而后，本文通过仿真实验分析GA-TS混合优化方法对网络能耗和延时的影响，并对比C/S模型与移动代理模型在无线传感器网络带宽约束下的性能，以验证GA-TS移动代理测量调度方法的有效性。2 无线传感器网络移动代理测量调度模型在无线传感器网络中，各传感器节点能力有限，必须通过多节点协作完成测量5，而存储量的限制也决定了传感器节点无法将所有目标测量和信号处理程序都存储于节点中。此外，能效性也是无线传感器网络测量过程中需要着重考虑的问题。因此，仅采用传感器节点无法满足无线传感器网络测量要求。除无线传感器节点外，无线传感器网络通常还包括一个中心处理节点。相对于传感器节点，中心处理节点具有更强的信号处理、网络通信和存储能力。针对无线传感器网络的结构特点，本文采用移动代理模型1完成无线传感器网络测量任务。如图1所示，中心处理节点存储各类移动代理程序，每种移动代理内嵌一种针对特定请求的处理方法，用于完成传感器节点提出的各类测量请求。在实际应用中，传感器节点根据测量需求向中心处理节点发送请求。随后，中心处理节点派遣相应移动代理到请求节点中完成测量。受网络通信能力影响，多个代理只能按照一定次序顺序发送。该次序将直接影响网络延时和能耗，必须根据需求动态优化。图1 采用移动代理技术的无线传感器网络无线传感器网络并行性决定了中心处理节点可能在短时间内接收到由多个传感器节点发送的请求。中心处理节点根据请求生成相应的移动代理，并按照收到请求的次序将移动代理放入派遣队列中。而后，中心处理节点根据派遣队列向请求节点发送移动代理。如果中心处理节点仅按照接收请求的次序派遣移动代理，这种方式称为顺序调度。但顺序调度并没有考虑能耗和延时的影响，而事实上这些因素将直接影响无线传感器网络的寿命和性能1。此外，不同请求具有不同延时要求，仅采用顺序调度可能使某些请求无法在允许的时间范围内完成，导致网络失效。因此，无线传感器网络移动代理测量调度方法应综合考虑移动代理的请求次序、请求优先级和完成请求所需延时和能耗的影响。3 遗传禁忌搜索移动代理测量调度原理3.1 移动代理测量调度指标1) 请求接收次序。请求接收次序表示中心处理节点接收到无线传感器节点移动代理测量请求的先后顺序。通常，移动代理默认按请求次序派遣，即采用先进先出（FIFO, first in first out）原则规划移动代理顺序。2) 请求优先级。该指标表征传感器节点测量请求的紧急程度。紧急程度越高对应的优先级越高，0表示高优先级，1为中间优先级，2为低优先级。高优先级请求对应的移动代理被优先派遣：新接收到的请求如具有比任务队列中其他请求更高的优先级，则将其派遣顺序提前，以确保这部分代理能被优先处理3。3) 能耗。此处，能耗代表完成传感器节点测量请求所需消耗的能量，主要包含移动代理传输能耗和移动代理计算能耗两部分，分别用和表示6。应用中的传输耗时由网络带宽、移动代理尺寸决定(1)假设中心处理节点与请求节点的距离为，在派遣移动代理时，中心处理节点与请求节点采用点对点传输方式，在标准距离下的最小传输功率为，则由空间自由传播模型4可知，传输功率为(2)其中，、和分别为发送增益、接收增益、波长和损失因子。所以，传输能耗为(3)、和为常数，则传输能耗事实上由传输距离和移动代理尺寸共同决定。而对于计算能耗而言，假设无线传感器节点在标准运行频率下的计算功率为，移动代理在标准频率下的执行时间为。在请求节点完成请求实际需要的时间与该节点运行频率成反比(4)计算功率与实际运行频率的平方成正比，即(5)所以，计算能耗为(6)3.2 综合评价指标设计为综合请求接收次序、请求优先级和能耗3个因素对移动代理测量调度的影响，应采用综合评价指标评价各移动代理的调度规划结果。该综合评价指标应满足如下要求：1)先接收到移动代理请求优先派遣；2)高优先级移动代理请求优先派遣；3)低能耗移动代理优先派遣。因此，首先可采用优先级因素修正能耗因素(7)而后设置任务队列中移动代理派遣次序因子(8)其中，表示任务队列中移动代理的数目，为各代理的队列序号。则综合评价指标定义为(9)其中，值越小，移动代理测量调度结果越优，反之，调度结果越差。3.3 GA-TS混合优化移动代理测量调度方法完成综合评价指标定义后，移动代理测量调度优化即转换为以移动代理队列次序为解空间的组合优化问题。研究人员曾尝试通过GA优化实现对移动代理测量调度7，但GA算法在优化过程中容易受到问题规模的限制。此外，GA算法中的交叉算子使群体中的染色体具有局部相似性，这将引发“早熟”问题，从而导致GA算法过早陷入局部最优。由此可见，仅用GA算法无法保证无线传感器网络移动代理测量调度优化的效果。为改进GA算法，研究人员把TS算法的“多样化”思想引入GA算法的交叉和变异操作中，以缓解GA算法的“早熟”问题8。TS算法最重要的特点是记忆已搜索过的局部最优解，并在后续迭代搜索中尽量避开这些解，使搜索途径多样化。采用GA-TS混合优化方法，有利于改善优化过程的基因“多样性”，并使搜索过程具有记忆性，提高解空间搜索效率。GA-TS混合优化方法的基本思想为利用TS算法使GA算法重组过程中的最优个体在遗传子代中存活，并尽可能保持存活个体的多样性。该混合优化方法把TS算法独有的记忆功能引入到GA算法进化搜索过程中，构造新重组算子TSR，同时把TS算法作为GA算法的变异算子TSM，提高GA算法的爬山能力。在重组算子TSR中采用了个规模为T的禁忌表，用于记录当前染色体的适应值。在后续次进化过程中，禁忌表中的染色体除破禁情况外不在新子代中出现。破禁情况指的是禁忌表中的染色体在满足一定条件（破禁水平）下可不受禁忌表限制。其目的是为了在保持子代基因多样性的前提下保证最优个体能够留在子代基因池中。在TSR算子中，破禁水平指的是父代群体适应值的平均值。操作时，首先把子代的适应值同破禁水平相比较，如果其适应值优于破禁水平，则该子代染色体进入下一代中；如果比破禁水平差，但不在禁忌表中，则该子代染色体也进入下一代中；若在禁忌表中，则选择最优父代进入下一代中。TSR算子采用禁忌表使群体中尽可能保持染色体结构的多样性和合理性，降低了算法的搜索范围，提高了搜索效率。TSM算子与标准变异算子都用于保证基因的多样性和全局搜索能力。而标准变异算子采用的是随机变异的方式，因此可能导致变异后子代性能退化。而TSM算子则基于TS算法的搜索过程，通过评价函数和禁忌表确保变异后子代的多样性和性能，使基因变异始终向全局最优的方向进化。基于TSR算子和TSM算子的GA-TS混合优化方法执行步骤的伪码如下所示。Step1设定GA算法的最大进化代数，种群规模，重组概率，变异概率；，生成初始种群，其中每个染色体对应一个待选解；repeatStep2For k=1 To L Do根据式(1)式(9)计算染色体的适应值；EndForStep3按轮盘赌法选个染色体，放入交配池。Step4 生成0、1之间的随机数，；如果，则交配池中第个染色体作为交叉的父代，产生均值为个父代染色体，其中为重组阈值； 对每对父代进行交叉，产生2个子代； 调用TSR对交叉后得到的子代进行重组。Step5生成0、1之间的随机数，；如果有，则调用TSM对交配池中第个染色体进行变异操作，其中为变异阈值；Step6；until 连续代最优个体保持不变，或。Step7输出最优解在移动代理测量调度规划中，GA-TS混合优化算法的染色体设计如图2所示。图2 GA-TS混合优化染色体设计即每个基因位代表一个待派遣的移动代理序号。该基因所对应的适应值由综合评价指标决定。这里取适应值函数为的倒数，即(10)适应值越高，对应的移动代理派遣次序越优。在算法优化中，邻域搜索是构建新解的必要过程。此处，邻域搜索依如下方式定义（如图3所示）。图3 GA-TS混合优化邻域搜索在进行邻域搜索时，GA-TS算法随机交换其中任意两个移动代理的队列次序。因此，每次邻域搜索的范围为，其中为待排序的移动代理数量。4 移动代理测量调度方法性能评估实验4.1 仿真实验环境设置在的无线传感器网络区域中，随机均布20个无线传感器节点，中心处理节点固定布置于区域中心。无线通信带宽，发送增益Gt和接收增益均为2，损失因子，中心处理节点的最小传输功率，传输载波频率。传感器节点在标准频率下的计算功率。移动代理根据请求的优先级划分为0、1和2级别，其中1个0级移动代理，5个1级移动代理和4个2级移动代理，移动代理的尺寸和标准频率下的计算耗时如表1所示。优先级高的移动代理可以请求派遣优先级低的移动代理。仿真过程中，各优先级的请求在无线传感器节点上随机产生，设定总的请求产生概率，其中0级代理请求比例为0.4，1级代理请求比例为0.3，2级代理请求比例为0.3。设置遗传算法的种群规模为50，复制率、交叉率和变异率分别为0.1、0.6和0.3，最大进化代数为400，收敛条件是连续20代最优个体保持不变，禁忌表长度为10。表1移动代理的尺寸和标准耗时优先级移动代理尺寸/byte标准耗时/s0级2000.1621级4000.187, 0.208, 0.297, 0.578, 1.2182级6001.632, 1.895, 1.712, 1.8834.2 C/S模型和移动代理模型对比实验首先分析2种模型对无线传感器网络能耗和延时的影响。此处，延时指从中心处理节点接收到请求派遣相应移动代理到传感器节点的时间间隔。在C/S模型中，每处理一个无线传感器节点的请求，无线传感器节点传输2 250byte原始数据到中心处理节点；而在移动代理模型中，中心处理节点则需要传输200600byte的移动代理到无线传感器节点完成信号处理。在相同参数下仿真10s无线传感器网络的信息传递和信号处理过程，能耗和延时随时间的变化曲线分别如图4(a)和图4(b)所示。图4 C/S模型与移动代理模型的能耗和延时比较由图4(a)可知，随时间推移，无论是C/S模型还是移动代理模型其能耗都呈线性增长，但C/S模型的能耗无论是增长率还是总能耗都远高于移动代理模型。在相同时刻，C/S模型的能耗约为移动代理模型能耗的10倍。其主要原因在于C/S模型传输数据量大，同时集中式信号处理模式增加了中心处理节点邻域的网络通信量，加重了网络拥塞，导致网络重传次数增加，从而增加了网络传输能耗。而对比网络延时实验结果可知，C/S模型的延时随仿真进行迅速增长，而移动代理模型的延时则相对稳定。由此可见，移动代理模型由于传输数据量小，传输规划合理，因此更适合于无线传感器网络的实时监测、数据传输和信号处理的要求。4.3 移动代理顺序调度和GA-TS调度对比实验为验证GA-TS混合优化方法的有效性，比较GA-TS混合优化方法和纯GA优化方法7的性能，分别采用顺序调度方法、GA调度方法和GA-TS调度方法规划移动代理的派遣次序，分析移动代理测量调度方法对无线传感器网络性能的影响。利用3种不同调度方法在相同参数下进行10s仿真，网络能耗和延时比较结果如图5(a)和图5(b)所示。图5 顺序调度、GA调度和GA-TS调度的能耗和延时比较如图5(a)所示，随时间推移，3种调度方法下移动代理的派遣能耗都近似呈线性增长。但同一时刻，GA-TS调度方法的能耗最低，GA调度方法的能耗次之。由此说明，经优化后的调度方法能通过规划移动代理派遣顺序有效降低网络能耗。同时，由于GA-TS调度方法的全局优化能力比GA调度方法强，因此经GA-TS调度方法优化后的移动代理派遣次序能效性更好。图5(b)显示了经调度后各移动代理派遣时的延时情况。由结果可知，顺序调度方法将导致各移动代理的派遣延时剧烈波动，部分移动代理可能由于延时过长无法在指定时限内完成操作，从而导致网络失效。对于某些具有时限要求的应用（如目标跟踪）而言，顺序调度方法将降低无线传感器网络的测量可靠性。相比于顺序调度方法，GA调度方法的延时变化则平稳许多，而GA-TS调度方法的优化效果则更为明显。由此可见，经优化后的移动代理派遣机制能够根据各代理派遣的先后次序和优先程度合理地安排各移动代理的派遣次序，使各移动代理的延时更加稳定、均衡，从而确保无线传感器网络的测量过程也能稳定而有效地实现。单纯比较GA调度方法和GA-TS调度方法的优化效果可知，GA-TS调度方法具有更好的顽健性和优化效果，经优化后的移动代理延时更低。4.4 无线传感器节点数目对最长时间延迟的影响实验最长延时指10s仿真过程中所有请求的延时最大值。将无线传感器节点数目从5递增到100，保持其他参数不变，分别进行10s仿真，记录最长延时，结果如图6所示。随着无线传感器节点数目增加，GA调度方法和GA-TS调度方法的最长延时也逐渐增加。当发送请求的无线传感器节点数目相同时，GA-TS调度方法的最长延时都低于GA调度方法。且GA调度方法在节点数目较多（本实验中节点数量超过80个）时，最长延时将随请求节点数目的增加迅速增长，而此时GA-TS调度方法的增长速率并未发生剧烈改变。可见，GA-TS调度方法具有更好的顽健性，也更适合于解决大规模无线传感器网络的移动代理测量调度规划问题。图6 无线传感器节点数目对最长时间延迟的影响5 结束语移动代理技术能有效改善无线传感器网络的协作能力，降低网络能耗，增强网络的动态性和适应能力。同时，移动代理的派遣规划将直接影响网络测量性能、能耗和延时。针对无线传感器网络带宽有限的特点，提出一种基于遗传算法和禁忌搜索算法混合优化的移动代理测量调度方法，以解决多移动代理派遣次序规划问题。该机制综合考虑了请求产生顺序、请求优先级和能耗3个因素，利用综合评价指标将代理测量调度转化为多参数寻优问题。所采用的遗传算法禁忌搜索混合优化方法改善了遗传算法的全局寻优能力，弥补了“早熟”问题对优化过程的影响。仿真实验结果表明，所提出的移动代理测量调度方法可以更好地调度移动代理的派遣次序，降低无线传感器网络的能耗增长速度和时间延迟，从而延长网络寿命，提高网络实时性。与仅采用遗传算法完成优化的派遣机制相比，混合优化方法具有更好的优化效果和鲁棒性，更适合于大规模无线传感器网络的移动代理测量调度规划。参考文献：1XU Y, QI H, KURUGANTI P T. Distributed computing paradigms for collaborative processing in sensor networksA. Proceedings of IEEE Conference on Global Telecommunications, 2003.3531-3535.2LANGER D B, OSHIMA M. Seven good reasons for mobile agentsJ. Communications of the ACM, 1999, 42(3): 88-89.3LIU J. Agent-based load balancing on homogeneous minigrids: macroscopic modeling and characterizationJ. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(7): 586-598.4WU, Q, RAO N S V, Barhen J, et al. On computing mobile agent