WSN中约束移动轨迹的数据汇聚路由协议设计与仿真.doc

1、CIVILAVIATIONUNIVERSITYOFCHINA毕业设计论文专业计算机科学与技术学号070341418学生姓名所属学院计算机学院指导教师二一一年六月中国民航大学本科生毕业设计论文WSN中约束移动轨迹的数据汇聚路由协议设计与仿真DESIGNINGANDSIMULATINGOFEFFICIENTDATAGATHERINGROUTINGPROTOCOLSWITHCONSTRAINTPATHOFWSN专业计算机科学与技术学生姓名学号070341418学院计算机学院指导教师2011年6月中国民航大学本科毕业设计（论文）创见性声明本人声明所呈交的毕业论文是本人在指导教师的指导下进行的工作和取得

2、的成果，论文中所引用的他人已经发表或撰写过的研究成果，均加以特别标注并在此表示致谢。与我一同工作的同志对本论文所做的任何贡献也已在论文中作了明确的说明并表示谢意。毕业论文作者签名签字日期年月日本科毕业设计（论文）版权使用授权书本毕业设计（论文）作者完全了解中国民航大学有关保留、使用毕业设计（论文）的规定。特授权中国民航大学可以将毕业设计（论文）的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交毕业设计（论文）的复印件和磁盘。（保密的毕业论文在解密后适用本授权说明）毕业论文作者签名指导教师签名签字日期年月日签字日期年

3、月中国民航大学本科毕业设计（论文）摘要无线传感器网络WIRELESSSENSORNETWORKS，简称WSNS是由能量及资源有限的大量节点构成具有数据采集、检测、控制的强有力的自组织网络形式，在有限的能量约束下，降低无线传感器能量消耗，提高数据采集效率是研究和应用无线传感器网络的热点。在SINK移动轨迹固定的传感器网络中，由于SINK有限的通信时间和节点的随机分布，使得很难兼顾数据采集量的提高和整体能耗的降低。为了解决该问题，提出了一种最大数据量最短路径MAXIMUMAMOUNTSHORTESTPATH，简称MASP数据采集方法。MASP对网络中成员节点与SUBSINK节点之间的匹配关系进行集

4、中式优化。采用01线性规划方法对MASP问题进行形式化描述，提出了一种基于二维染色体编码的遗传算法进行求解，并给出了相应的数据通信协议设计。另外，MASP可以扩展支持低密度网络和多SINK点网络。基于MATLAB分析的数据结果表明，MASP在能耗利用率方面要远远优于最短路径树方法SHORTESTPATHTREE，简称SPT。关键词WSN；传感器网络；移动SINK轨迹固定；数据采集；能耗利用率中国民航大学本科毕业设计（论文）ABSTRACTWIRELESSSENSORNETWORKSWIRELESSSENSORNETWORKS,REFERREDTOASWSNSISASELFORGANIZINGN

5、ETWORKWITHDATACOLLECTION,DETECTIONANDCONTROL，THENETWORKISCONSTITUTEDBYALARGENUMBEROFNODESOFLIMITEDENERGYANDRESOURCESITISAHOTSPOTOFRESEARCHINGANDAPPLYINGWIRELESSSENSORNETWORKTHATREDUCETHEENERGYCONSUMPTIONOFWIRELESSSENSORANDPROLONGSURVIVALTIMEANDNETWORKTRANSMISSIONNETWORKRELIABILITY，STABILITYINSENSORN

6、ETWORKSWITHAPATHFIXEDMOBILESINK,DUETOTHELIMITEDCOMMUNICATIONTIMEOFTHEMOBILESINKANDRANDOMDEPLOYMENTOFTHESENSORNODES,ITISQUITEDIFFICULTTOINCREASETHEAMOUNTOFDATACOLLECTEDANDREDUCEENERGYCOMSUMPTIONSIMULTANEOUSLYTOADDRESSTHEPROBLEM,THISPAPERPROPOSESADATACOLLECTIONSCHEMECALLEDMAXIMUMAMOUNTSHORTESTPATHMASP

7、,WHICHISALSOAPPLICABLEINSENSORNETWORKSWITHLOWDENSITYANDMULTIPLESINKSDATAANALYSISUNDERMATLABSHOWSTHATMASPOUTPERFORMSSHORTESTPATHTREESPTANDSTATICSINKMETHODSINTERMSOFENERGYUTILIZATIONEFFICIENTLYKEYWORDSWSNSENSORNETWORKPATHCONSTRAINTMOBILESINKDATACOLLECTIONENERGYUTILIZATIONEFFICIENTY中国民航大学本科毕业设计（论文）目录引言

8、11应用场景模型22最大数据量最短路径问题421数据采集总量最大化422系统能耗最小化423最大数据量最短路径优化问题53基于遗传算法和局部搜索的启发式算法731染色体编码与初始群体生成732适应函数与不适应函数833种群选择与交配规则834局部搜索增强算法935群体更新与算法终止条件1036算法复杂度分析104基于MASP的数据采集通信协议1141初始化阶段1142数据采集阶段125基于低密度网络和多个SINK点扩展1451支持低密度网络1452支持多移动SINK点146性能仿真1661应用场景的抽象与初始化16中国民航大学本科毕业设计（论文）62单SINK点SPT性能评估1763单SINK

9、点MASP性能评估1964多SINK点MASP性能评估23结论27参考文献28致谢30附录31附录A程序清单（见光盘）31附录B外文资料翻译31中国民航大学本科毕业设计（论文）1引言无线传感器网络WIRELESSSENSORNETWORK,简称WSNS融合了传感器技术、嵌入式计算技术、分布式信息处理和通信技术，能够实时检测、感知和采集网络分布区域内的各种环境或检测对象的数据，并对这些数据进行处理，从而获得相近而准确的信息。感知和采集各种环境或检测对象的信息，通过无线方式发送，并以自组多跳的网络方式传送到用户终端。能量受限和网络拓扑动态变化是无线网络传感器主要的特点。能耗问题是困扰无WSNS实际

10、应用的主要障碍之一。在WSNS中，SINK周围的节点由于需要转发更多的数据导致能量过早耗尽，容易形成WSNS能耗瓶颈。近年来，人们提出各种SINK移动方案使得全网能量消耗在更多的节点之间均衡，从而缓解能耗问题。本文应用场景主要针对SINK移动轨迹固定的无线传感器网络，其中，SINK点沿着固定轨迹周期移动，大量传感节点分布在轨道周围并采用多跳通信方式将数据传送到移动SINK点。在此类网络中，SINK点的移动性会带来其通信时间的限制，从而极大地约束了系统数据采集能力。因此，如何提高能耗利用率，利用有限的能量采集尽可能多的数据成为该系统一个重要评价指标。在已有文献中，最短路径树算法SHORTESTP

11、ATHTREE，简称SPT经常被用于寻找传感节点到移动SINK的路径。SPT能够有效降低系统能耗，却经常无法采集到预期的数据量，能耗利用率较低。针对SINK移动轨迹固定的大规模密集型传感器网络，本文根据国际顶级期刊IEEETRANSACTIONSONMOBILECOMPUTING中的论文EFFICIENTDATACOLLECTIONINWIRELESSSENSORNETWORKSWITHPATHCONSTRAINEDMOBILESINKS提出的一种高效的数据采集机制MAXIMUMAMOUNTSHORTESTPATH，简称MASP进行了仿真计算，根据SINK点的有效通信时间去优化各传感节点到SI

12、NK的传输路径，从而使系统数据采集量最大化，同时降低网络总能耗，提高系统能耗利用率1。中国民航大学本科毕业设计（论文）21应用场景模型本文考虑一种SINK点移动轨迹固定的大规模密集型无线传感器网络，实际应用场景包括野外生态环境检测、智能农业监测、大型建筑物健康结构监测等。图11给出一个应用场景模型示例。移动SINK点M安装在机器或者汽车等运动载体上，这些运动载体通常沿着已有的道路设施进行反复移动，因而SINK点移动轨迹固定。每当SINK点M移动到终点并返回起点时，称其完成一“轮”移动。传感器节点随机、均匀散布在移动轨道L两侧。当SINK点M移动到节点附近时，节点开始向M发送数据。根据移动SIN

13、K点M的通信范围R，可以将全部监测区域划分为两部分直接通信区域DIRECTCOMMUNICATIONAREA，简称DCA和多跳通信区域MULTIHOPCOMMUNICATIONAREA，简称MCA。图11中，L1和L2两条曲线之间的区域即为DCA，该区域内的节点简称SUBSINK距离轨道较近，因而能够向SINK点M直接传送数据。而对于MCA中的节点（简称成员），需要采用多跳中继方式将数据传送给SUBSINK，后者缓存来自各成员的数据并最终发送给移动SINK点。图11SINK轨迹固定无线传感器网络应用场景本文对该应用场景的特点进行如下假设（1）移动SINK点具有固定的能量资源，存储资源和计算能力

14、；（2）各节点具有相同的属性，连续采集并发送数据，SUBSINK点有足够的存储空间缓存中国民航大学本科毕业设计（论文）3数据；（3）各成员仅选择一个SUBSINK作为目的；（4）考虑密集型网络，所有节点之间可以通过单跳或多跳方式互相连通；（5）所有成员节点沿着最短路径向其所属的SUBSINK点发送数据。在图11场景中，固定的移动轨迹和速度限定了移动SINK点和各SUBSINK点之间的通信时间长度。因此，在每个SINK运行周期内，各SUBSINK点能发送的最大数据量是固定的。另一方面，SUBSINK所发送的数据主要来自于成员节点，因此各SUBSINK包含成员节点的数量决定了其所缓存的数据量的大小

15、。实际缓存数据量和所能发送最大数据量的比较将直接影响到移动SINK点单个周期内的数据采集量。即图11中系统数据采集量与各SUBSINK所包含的成员节点数量共有关，可以通过调整成员数量来提高数据采集量。另一方面，成员节点数量将影响网络中的数据流向，从而直接影响到网络整体能耗。本文所做的工作是如何控制成员数量，即如何优化成员节点在各SUBSINK点之间的分配使得在最大化系统数据采集量的同时能够尽可能地降低能耗。根据已有文献，最短路径树SHORTESTPATHTREE，简称SPT方法选择SUBSINK点，各成员选择距离其跳数最短的SUBSINK作为目的，成员采集的数据沿着多条源于各SUBSINK选择

16、标准仅仅根据跳数信息而不考虑各SUBSINK点的数据发送能力，因而可能会造成SUBSINK的成员数量与其数据发送能力不匹配。例如，某些SUBSINK点与移动SINK的通信时间较长，但其成员数量较少，导致没有足够的数据可以发送；而另一方面，某些SUBSINK点与移动SINK的通信时间很短，但成员数量很大，导致无法完全发送缓存的大量数据信息。此外，大量数据流向“饱和”的节点还会导致网络能耗的不均匀，缩短网络生存时间2,3。中国民航大学本科毕业设计（论文）4最大数据量最短路径问题本文的主要目标是，针对SINK移动轨迹固定的无线传感器网络，综合考虑数据采集量和能耗两项技术指标，提出一种优化的SUBSI

17、NK选择机制，提高系统能耗利用率，具体包括两个优化目标（1）系统数据采集总量最大化；（2）在目标1的基础上系统整体能耗最小化。为便于表述，用TOTALN表示传感节点总量，SSN和MEMBERN分别表示SUBSINK数量和成员数量。那么，TOTALSSMEMBERNNN。11数据采集总量最大化系统数据采集总量TOTALQ由来自各SUBSINK的数据量组成，即1SSIINTOTALSSIQQ。其中ISSN表示选择SUBSINKI作为目的成员节点数量。对于任意SUBSINKI，实际所发送的数据总量ISSQ取决于其缓存数据量与最大发送数据量之间的比较，如公式21所示MIN,1IIISSTSSSSSQD

18、TDNT21公式21中，TD和SD分别表示数据传输速率和数据采集速率。T为SINK点的运行周期，ISST表示SUBSINKI与SINK点的通信时间长度。公式21中，除ISSN外的所有参数都是固定不变的。因此，系统数据采集总量最大化的充要条件为MIN1IIITSSSSSSSDTNNDT22公式22表明，只要各SUBSINK点的成员数量不小于最小成员需求MINISSNMINIMUMREQUIREMENT，简称MINREQ，则移动SINK就可以采集到理论上的最大数据量。12系统能耗最小化在传感器网络研究中，FIRSTRADIOORDER能耗模型4经常用于计算节点发送和接收能耗。在FIRSTRADIO

19、ORDER能耗模型中，节点发送能耗与传播距离的平方成正比。本文不考虑功率控制问题，假定所有节点采用固定的发射和接受功率，节点能耗与节点之间的实际距离无关。为此，本文采用公式23所示的简化能耗模型5。RTPEKK23在公式23所表示的能耗模型中，节点总能耗P由接收和发送的数据总量RK和TK来中国民航大学本科毕业设计（论文）5决定。E为常数，表示发送和接收单位比特数据的能耗。在移动SINK单个运行周期内，任意节点I接收数据量IRK和发送数据量ITK之间的关系为IITRKKQ，Q表示节点I在单个运行周期内所采集到的数据总量。根据假设5，所有成员节点沿着最短路径向其所属的SUBSINK点发送数据，故可

20、以得到全网所有节点接收数据总量与跳数之间的关系，见公式2411TOTALTOTALNNIRIIIKHQ24在公式24中，IH表示节点I到其所属SUBSINK点的最短跳数。如果就节点I为SUBSINK，则IH为0。根据公式24，可以将单轮系统总能耗TOTALP表述为最小跳数的形式，如1111221TOTALTOTALTOTALTOTALNNNNIIITOTALIRTRIIIIIPPEKKEKQEHQ25公式25中，IP为任意节点I的单轮总能耗。根据公式25，系统总能耗最小化问题等价于全网节点距离其所属SUBSINK点跳数和最小化问题。13最大数据量最短路径优化问题第31节和第32节分别对达到能耗

21、最小化和数据量最大化两个优化目标的条件进行了分析，这里给出如下最优化问题描述目标函数1MINTOTALNIIH26满足约束条件MINIISSSSNN271SSINSSMEMBERINN28优化目标函数26最小化最短跳数和，也意味着全网整体能耗最小化。约束条件27将确保移动SINK点数据采集量最大化，而约束条件28则对各SUBSINK点成员数量的总和进行约束。上述最优化问题可以描述为寻找最佳的成员分配机制或SUBSINK选择机制，建立各成员与SUBSINK之间优化的映射关系，使得在确保系统数据采集量最大的前提下最小化全网整体能耗。因此，该最优化问题成为最大数据量最短路径问题MASPMAXIMUM

22、AMOUNTSHORTESTPATH。根据前述假设，在MASP中，各成员必须且仅能选择一个SUBSINK作为目的，且SUBSINK点对所含有的成员数量有下边界约束。根据这一特征，为了便于求解，可以将MASP问题转中国民航大学本科毕业设计（论文）6化为01整数线性规划问题。矩阵MEMBERSSANN由IJA元素组成1,1,MEMBERSSINJN。IJA为二进制变量，1IJA表示成员I选择SUBSINKJ作为目的；0IJA表示SUBSINKJ不是成员I的目的；矩阵MEMBERSSHNN由IJH元素组成1,1,MEMBERSSINJN。IJH表示成员节点I到SUBSINKJ的最短跳数。目标函数11

23、MINMEMBERSSNNIJIJIJAH29满足约束条件11,SSNIJJAI210MIN1,MEMBERJNIJSSJANJ211MIN1SSJNMEMBERSSJNN212新目标函数29等价于目标函数26。约束条件210确保每个成员必须且仅选择一个SUBSINK，约束条件211确保各SUBSINK的成员数量大于最小需求量MINREQ。约束条件212与前述的假设条件24一致，即考虑高密集型网络，成员总量大于最小需求量的总和1。关于节点密度较低的网络，即成员总量小于最小需求量总和的情况将在后面进行讨论。中国民航大学本科毕业设计（论文）72基于遗传算法和局部搜索的启发式算法最优化问题29是一类

24、广义指派问题，而广义指派问题是一类NP完全组合优化问题1。遗传算法是一种有效解决组合优化问题的启发式算法。本文利用遗传算法的基本原理，结合局部搜索的优势，给出了集中式MASP问题解决，实现了成员数量的最优分配。21染色体编码与初始群体生成遗传算法中常用的染色体CHROMESOME编码都是一维编码。在目标优化函数29中，解的形式是MEMBERSSNN二维矩阵。为了便于表述和计算，这里采用解的原始形式作为染色体编码方式，即二进制二维编码方式。图31给出了染色体二维编码的示例。图31左图为一个简单网络拓扑，S1,S2,S3表示3个SUBSINK点，N1N10表示10个成员节点。SUBSINK点内的数

25、字表示最小成员需求量MINREQ，成员节点内的数字表示其所选择的SUBSINK编号，对应左图的SUBSINK选择结果，可以得到如表31的二维染色体编码格式。首先，通过为所有成员节点随机选择一个SUBSINK点作为目的，随机产生N个初始个体组成初始群体POPULATION。初始群体内的个体将满足约束条件210，但可能不满足约束条件211。因此，初始群体有可能包含一系列不可行解。在遗传算法设计中，首先需要将初始群体的不可行解进化为可行解，然后在此基础上进一步提高种群内染色体的质量，从而达到最优。根据染色体编码规则，初始群体中的每个个体是一个MEMBERSSNN二维矩阵1,2,3,LALN，这里用1

26、,1,LIJMEMBERSSAINJN表示矩阵LA的元素。图31SUBSINK选择和网络拓扑图中国民航大学本科毕业设计（论文）8将网络拓扑图进行二维染色体编码如表31。表31二维染色体编码10001010000101000110000101010022适应函数与不适应函数适应函数的定义通常综合考虑目标函数和个体不可行度，当个体为不可行解时，给予适应值一定的惩罚。这里，采用将目标函数值和个体可行度分开处理的方式，分别定义适应函数和不适应函数用于计算个体的适应值FITNESS和不适应值UNFITNESS，如公式213、公式214所示，可以看出，适应函数与目标函数29相同，反应最短跳数之和，适应值较

27、小的个体较优。不适应函数反映了当前解的不可行度，即当前解偏离可行解的程度。不适应值越小，说明当前解接近可行解。11MEMBERSSNNLLIJIJIJFAAH31MIN11MIN0,SSMEMBERJNNLLIJSSJIUFAAN3223种群选择与交配规则关于种群选择，采用随机联赛选择模型，从当前群体中随机选择两对个体，每对个体中适应值较小的个体被选为双亲之一，用于交配生成子代个体。适应值是种群选择的唯一标准，而不适应值将被用于双亲交配过程去提高子代基因的质量。遗传算法中交配规则通常选择一个或多个交配位，然后对换交配位之间的基因以获取更高质量的子代。本文采用二维染色体编码，为了确保子代个体继续

28、满足约束条件210，这里采用逐行交配的模式。交配算法见表31。中国民航大学本科毕业设计（论文）9表31基于不适应值的交配规则对任意成员I1初始化12,SSNVVV0。2FORJ1TOSSN,1PJIJVAAND2PIJA3IF11SSNKKV41,1,2,PCIJIJSSAAJN5ELSE61PCIJIJAAWITHPOSSIBILITY212,1,2,PPPSSUFAUFAUFAJN72PCIJIJAAWITHPOSSIBILITY112,1,2,PPPSSUFAUFAUFAJN表31所示算法中，矩阵1PA，2PA和CA表示两个父代个体，分别由元素1PIJA，2PIJA和CIJA构成。临时变

29、量12,SSNVVV用于存储父代个体之间逐行进行交配的临时信息。算法1中，AND为二进制变量的逻辑与运算符。对任一成员，如果两个父代个体的SUBSINK选择相同，则子代个体将继承双亲的选择；如果父代的SUBSINK选择不同，则不适应值较小的父代将以较高的概率被继承，从而有利于寻找可行解，提高子代基因质量，图32给出了交配过程的一个实例。图32中，父代具有较低的不适应值。根据算法1，子代个体继承父代1较多的特点，因此看起来“更像”父代1。在变异过程中，随机选择两个成员并交换其SUBSINK选择，既保证子代个体满足约束条件210，又完成基因的变异。1001001000100100101001001

30、00001001001010010010001001001100100100001001001010010010100100100PARENT1CROSSOVERPARENT2CHILD图32交配规则实例24局部搜索增强算法为了进一步提高子代个体基因的质量，本文采用基于局部搜索的增强算法来降低子代个体的适应值和不适应值。中国民航大学本科毕业设计（论文）10提出增强算法可以缩减遗传代数，加速遗传算法的运行。局部搜索增强算法共分两个阶段。阶段1用于降低子代个体的不可行度，有助于寻找可行解；阶段2则用于降低目标函数值，有助于寻找最优解。阶段1基本思想是将部分成员从某些“饱和”SUBSINK点转移到“

31、饥饿”SUBSINK点。阶段2基本思想是让选择“饱和”SUBSINK点的部分成员重新选择距离其最近的SUBSINK点。25群体更新与算法终止条件每一代双亲交配后，根据如下规则更新当前群体如果子代个体与当前群体中某个个体相同，则丢弃子代个体；如果当前群体包含不可行解，且子代个体的不适应值小于当前群体中的最高不适应值，则更新群体；如果当前群体不包含不可行解，且子代个体的适应值小于当前群体中的最高适应值，则更新群体。算法终止条件为循环执行第43节第45节的步骤，直到产生STOPC个不同的子代个体为止。26算法复杂度分析图33所示的算法整体流程中，局部搜索增强算法之外的步骤均比较简单，因此，算法每次循

32、环操作的整体复杂度取决于局部搜索增强算法。其中，阶段1的时间复杂度为2SSMEMBERONN，阶段2的时间复杂度为SSMEMBERONN，故遗传算法单个循环全部操作的时间复杂度为2SSMEMBERONN。值得注意的是，上述分析基于最坏情形来考虑。算法实际执行过程中，随着遗传代数的增加，当前群体中的不可行解数量减少，阶段1的处理必须加快。当群体全部由可行解组成时，就没有必要执行阶段1的增强处理了。中国民航大学本科毕业设计（论文）113基于MASP的数据采集通信协议考虑到移动SINK能量资源，存储资源和计算资源不受限制，数据采集通信协议中复杂的集中式优化计算将由SINK点完成。通信协议主要分为两个

33、阶段初始化阶段和数据采集阶段。31初始化阶段初始化阶段主要用于获取全网拓扑信息、信息SUBSINK节点、为各成员节点指派SUBSINK等。完成上述任务，需要移动SINK点运行3个周期，即3轮。（1）第1轮首先，定义广播消息帧格式_,BROADMSGTYPESRCNETWADDRHOP，用于选择SUBSINK和建立最短路径树。第1轮中，移动SINK点不断广播TYPE为0的_0,0,0BROADMSG，所有接收到该消息的节点被自动选择为SUBSINK点。SUBSINK点广播TYPE为1的BROAD_MSG消息，其他成员节点会继续广播该消息，用于建立多个SUBSINK为根的最短路径树。TYPE为1的

34、BROAD_MSG中，SRCNETWADDR为树根SUBSINK的地址，HOP为节点距离其当前最短路径树树根SUBSINK的跳数。表41给出了第1轮中SUBSINK选择和最短路径树建立的具体算法。在表41所示算法运行结束后，所有节点获得了距离各SUBSINK的最短跳数信息，并将相关信息发送给相应的SUBSINK点，后者将于第2轮将最短跳数信息发送给移动SINK点。此外，第1轮中SUBSINK点需要记录移动SINK点首次进入及最后离开其通信范围的时间。对于移动SINK而言，起点到终点的正向移动与反向过程是完全对称的。所以，这里仅需要记录SINK正向移动过程的通信时间即可。（2）第2轮SUBSIN

35、K点第1轮中收集的最短跳数信息及通信时间信息发送给移动SINK。根据这些信息，移动SINK将计算分配给SINK点的通信时间。在节点密集分布的场景中，SUBSINK与移动SINK的通信时间可能会发生重叠，即同时存在两个及以上的SUBSINK位于移送SINK的通信范围内。这里采用一种简单的切换方法来分割时间，即一旦有新的SUBSINK进入移动SINK点通信范围，则移动点立即断开与当前SUBSINK的通信，开始与新的SUBSINK通信。通信时间计算完毕后，移动SINK点运行MASP算法为各成员选择优化的SUBSINK点。这里，通信时间计算和MASP计算都由计算和存储能力较强的移动SINK点在离线状态

36、下完成。故即使遗传算法的计算时间中国民航大学本科毕业设计（论文）12可能稍长，也不会对系统整体性能造成影响。表41SUBSINK选择及最短路径树建立算法1初始化路由表2WHILETRUEDO3侦听数据包4IF接收到BROAD_MSG0,0,05被选为1个SUBSINK6发送BROAD_MSG1,SNA,0/SNAISTHENETWORKADDRESSOFCURRENTNODE7ELSEIFRECEIVEBROAD_MSG1,SRCNETWADDR,HOP8在路由表中寻找目标地址是SRCNETWADDR的项,9IF未搜索到相应的路由项10添加新的项到路由表DESTINATIONSRCNETWAD

37、DR,METRICHOP111广播BROAD_MSG1,SRCNETWADDR,HOP112ELSEIFMETRICHOP113更新路由项METRICHOP114广播BROAD_MSG1,SRCNETWADDR,HOP115ELSE16忽略当前广播消息17ENDIF18ENDIF（3）第3轮移动SINK点通过广播消息将第2轮的计算结果扩散到网络中，广播消息由一系列成员节点和SUBSINK点之间的匹配关系列表构成。每个接收到该广播消息的节点将获得其目的SUBSINK信息，然后该节点将删除广播消息中与自身相关的条目并继续广播，从而完成SUBSINK优化选择结果在全网的扩散。32数据采集阶段初始化结

38、束后，全网节点连续采集数据并沿着初始化阶段建立的最短路径树向目的SUBSINK发送。考虑到节点故障或新节点加入造成的网络拓扑变化，当某些节点无法成功地将数据发送给SUBSINK时，可以采用现有的按需路由协议6帮助其获得跳数距离最近的可用SUBSINK作为临时目的。各SUBSINK在移动SINK点到来之前缓存其自身来自其成员节点的传感信息。如前所述，在移动SINK和SUBSINK的通信中，新SUBSINK总是具有较高优先级，为确保各成员之间信息的均衡，SUBSINK则采用轮盘赌方式7向移动SINK发送数据。之前介绍的遗传算法是一种离线集中式算法，无法实时感知网络拓扑的动态变化。当SUBSINK发

39、生变化或成员信息发生变化时，MASP的计算结果将随之失效，考虑到初始化阶段中国民航大学本科毕业设计（论文）13中的复杂计算均由功能强大的移动SINK点完成，故可以通过周期性重复初始化阶段使MASP感知系统发生变化，而不影响系统性能。中国民航大学本科毕业设计（论文）144基于低密度网络和多个SINK点扩展41支持低密度网络网络节点密度是一个相对的概念，没有绝对的定义。为了方便起见，这里将成员数量与各SUBSINK点最小成员需求量MINREQ之和的比较作为衡量网络节点密度高低的分界线1。如果成员数量不小于最小需求量之和MIN1SSJNMEMBERSSJNN，则认为是高密度网络；反之，为低密度网络。

40、前面有关MASP问题的分析与解法均基于高密度网络。在高密度网络中，由于成员数量过大，单个运行周期内所有节点采集的数据总量要大于移动SINK点数据采集量的上限，因此总会存在一部分数据无法被传送到移动SINK点。然而在低密度网络中，由于成员数量小于最小需求量之和，移动MIN1SSJNMEMBERSSJNN点有可能收集到全部节点采集的数据，使得数据采集量最大化。在低密度网络中，SINK点数据采集量最大化的充要条件将不再是不等式22，而是必须确保每个SUBSINK点的数据缓存量不超过其数据发送能力的上限。因此，第33节中最优化问题的约束条件211和约束条件212需要修改为MIN1,MEMBERJNIJ

41、SSIANJ51MIN1SSJNMEMBERSSJNN52根据约束条件51和约束条件52，可以得到一个新的MASP最优化问题。为便于区分，将高密度网络中的MASP标记为MASPHD，将低密度网络中的MASP标记为MASPLD。第4节给出的遗传算法依然可以用于求解MASPLD问题，但需要做相应调整，例如不适应函数的定义需要修改公式为53。此外，局部搜索增强算法也应作类似调整。MIN11MAX0,SSMEMBERJNNLLIJSSJIUFAAN5342支持多移动SINK点多移动SINK点能够有效解决因网络规模扩大引起的可扩展性问题。在本文所述的应用环境中，可以引入多个移动SINK点来提高网络整体性

42、能，如提升数据采集量、降低网络能耗等。在MASP中，移动SINK与SUBSINK点进行直接通信，而成员节点则仅仅需要选择合适的SUBSINK中国民航大学本科毕业设计（论文）15点并连续不断地将所采集的传感信息传送到相应的SUBSINK点。也就是说，对于众多节点而言，移动SINK点是一个“透明”设备，成员节点无须了解移动SINK点的数量信息和位置信息。据此，本文提出的MASP数据采集方案可以直接应用于移动SINK点的应用场景，具有良好的可扩展性。在多个移动SINK点沿着不同固定轨道移动的环境下，随着SINK点数量的增加，网络中的SUBSINK点也会增加，而最小成员需求量之和MIN1SSJNSSJ

43、N也会随之增加。由于节点总量固定不变，随着SINK点的增多，网络节点密度可能会发生相对变化，即可能会从密度网络转变为低密度网络。在实际应用中，需要关注网络节点密度的相对变化，如果成员数量小于最小需求量之和MIN1SSJNMEMBERSSJNN，则使用MASPHD方法；反之，则使用MASPLD方法。中国民航大学本科毕业设计（论文）165性能仿真本文利用MATLABR2009A构建仿真平台，模拟SINK点移动轨迹固定的无线传感器网络应用场景。首先基于SPT方法进行分析，然后对所提的基于遗传算法的MASP机制进行性能分析，并且针对单SINK点和多SINK点两种不同的情景。仿真环境主要参数设定如下传感

44、器节点均匀分布在400M350M的矩形检测区域内，SINK点以5M/S的速度匀速移动，SUBSINK与移动SINK之间的数据传输速率为20KB/S；在数据采集阶段，各节点在SINK点运行周期内以200B/S的速度进行连续数据采集，同时将传感信息即时发送给相应目的SUBSINK；考虑同构网络，所有节点具有相同的初始能量20J和相同的最大通信距离52M；能耗模型3中的常量E设为05J/BIT。51应用场景的抽象与初始化将检测的矩形区域抽象成二维矩阵A，初始0IJA。随机产生SINK点的初始位置，假设矩阵相邻列相邻点或者相邻行相邻点之间的距离为5M，即SINK每秒向上或者向下移动一格，设定1IJA为

45、SINK点每秒移动过的位置。在矩阵的非SINK点移动轨迹的位置上随机产生NUMBER_NODE个节点，设定2IJA。按照设定的通信范围，搜索出与SINK点轨迹上的点小于52M的节点，即为SUBSINK点，设定1IJA。按照先行后列的顺序，分别依次对SUBSINK和MEMBER节点编号。画出的随机产生的场景图如图61。图61随机产生的场景图中国民航大学本科毕业设计（论文）1752单SINK点SPT性能评估对每个SUBSINK点搜索出在其通信范围内的MEMBER节点，即可与对应SUBSINK单跳通信。利用二维矩阵SUB_SINK_TO_MEMBER存储，若第I个SUB_SINK点能与第J个MEMB

46、ER节点单跳通信，则SUB_SINK_TO_MEMBERI,J1；否则，SUB_SINK_TO_MEMBERI,J0。对每个MEMBER节点搜索在其通信范围内的MEMBER节点，即可与其对应MEMBER节点单跳通信。在单跳通信的基础上，即可求出各可多跳通信的MEMBER节点之间的最短跳数关系。利用二维矩阵MEMBER_TO_MEMBER存储，如第I个MEMBER节点到第J个MEMBER节点，搜索所有第J个MEMBER节点能通信的MEMBER节点K，若MEMBER_TO_MEMBERI,KMEMBER_TO_MEMBERI,JMEMBER_TO_MEMBERJ,K，则更新MEMBER_TO_ME

47、MBERI,K。在矩阵SUB_SINK_TO_MEMBER和MEMBER_TO_MEMBER的基础上，求出各SUB_SINK点到各MEMBER节点的最短跳数，存储在矩阵HOP中。HOP初始化为SUB_SINK_TO_MEMBER矩阵，通过搜索MEMBER_TO_MEMBER矩阵确定最短跳数，如第I个SUB_SINK点到第J个MEMBER节点，搜索所有第J个MEMBER节点能通信的MEMBER节点K，若HOPI,KHOPI,JMEMBER_TO_MEMBERJ,K，则更新HOPI,K。根据上述方法建立的最短路径树如图62。图62最短路径树的场景图中国民航大学本科毕业设计（论文）18根据SINK点

48、的通信范围，搜索每个单位时间点在其通信范围内的SUBSINK点。从而确定每个SUBSINK点进入和离开通信范围的时间，分别用一维数组START_TIME和END_TIME存储。根据一旦有新的SUBSINK点进入SINK点通信范围，则移动点立即断开与当前SUBSINK的通信，开始与新SUBSINK通信的原则，确定每个时间点SINK点对应通信的SUBSINK点，存储在一维数组ON_SUB_SINK中。图63和图64给出了SPT算法的运行结果。图63中，SPT仅仅能够采集到大约理论最大值一半的数据。图64给出了图63中在150个节点的情况下，各SUBSINK点所含成员数量与最小成员需求量的比较，而后

49、者则是根据各SUBSINK点的最大数据发送能力计算得到。从前面的分析可知，如果最小成员需求量无法满足，将导致移动SINK通信时间的浪费和数据采集量的减少，例如图64中的SUBSINK15。总之，SPT方法虽然能够有效降低能耗，但是由于数据采集效率较低，因而导致能耗利用率低下。图63移动SINK单轮数据采集总量比较中国民航大学本科毕业设计（论文）19图64各SUBSINK所属成员在150个节点情况下的数量比较53单SINK点MASP性能评估对于MASP问题，利用遗传算法求解步骤如图65。为保证各SUBSINK点对应的MEMBER节点数量不小于最小成员需求量，利用公式22求出各SUBSINK的最小成员需求量。利用一维数组MINREQ存储。遗传算法终止条件中的CSTOP设为5000，初始种群个体数量大小N为100，利用三维矩阵ARR