基于足迹的无线传感网位置服务算法研究.doc

基于足迹的无线传感网位置服务算法研究 一编祗知七受孝水嗖碛士研究值（卑此；讼式，？，、？”？基于足迹的无线传感网位置服务算法研究）、学科专业控制理论与控制工程研究方向无线传感器网络研究生姓名刘广仑指导教师、职称徐哲壮副教授所在学院电气工程与动化学院答辩委员会主席签名二一八年三月一遒守学术行为规范承诺本人已熟知并愿意自觉遵守福州大学研宄生和导师学术行为规范实施办法和福州大学关于加强研宄生毕业与学位论文质量管理的规定的所有内容，承诺所提交的毕业和学位论文是终稿，不存在学术造假或学术不端行为，且论文的纸质版与电子版内容完全一致。 ？二独创性声明本人声明所提交的论文是我个人在导师指导下进行的研宄工作及取得的研宄成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研宄成果，也不包含为获得福州大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研宄所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 本人完全意识到本声明的法律结果由本人承担。 三关于论文使用授权的说明本人完全了解福州大学有关保留使用学位论文的规定，即学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 （保密的论文在解密后应遵守此规定）本学位论文属于（必须在以下相应方框内打“”，否则一律按“非保密论文”处理）、保密论文本学位论文属于保密，在年解密后适用本授权书。 、非保密论文本学位论文不属于保密范围，适用本授权书。 研究生本人签名签字曰期年月上曰研究生导师签名签字日期￥年月炒日基于足迹的无线传感网位置服务算法研究中文摘要在无线传感网中，当有事件信息被传感器检测到时，传感器需要生成一个包含有事件信息的数据包并向传感网中的汇聚节点传输。 汇聚节点可以是任何形式的有通信终端的智能设备或人员，当汇聚节点移动时传感器便难以获知其当前位置。 如何向移动的汇聚节点进行数据包的传输成为一个具有挑战性的问题。 位置服务算法是解决汇聚节点移动性的常用算法，其通过在网络中选取部分传感器作为位置服务节点完成汇聚节点与传感器节点的连接。 但是，汇聚节点需要频繁地向位置服务节点更新自身位置信息以使传感器能够获取其最新的位置。 在以事件为驱动的网络场景中只有事件发生才会有数据的传输，当事件发生频率较低时，大量汇聚节点的位置更新是没有必要的，从而会造成大量的能耗浪费。 为解决位置服务算法中能耗浪费的问题，本文提出一种基于足迹的位置服务算法（，）。 该算法的基本思想是汇聚节点在移动过程中可以留下由连续的足迹点构成的一条足迹。 当任意一个足迹点被数据包发现，数据包便可以沿着这条足迹到达汇聚节点。 通过引入足迹信息，使现有位置服务算法中位置更新的周期得以延长，从而能够减少更新部分的能量消耗。 具体而言，本文包括以下研宄内容、汇聚节点生成的足迹信息是的基础，本文首先设计了低能耗的足迹生成算法以降低引入足迹的能耗代价，并推导了保证足迹连通性的充分条件，使在引入足迹信息后能够保证传输路径的连续性，从而保证传输的成功率。 、分为三个阶段更新阶段、查询阶段和追逐阶段。 在更新阶段，汇聚节点以不同的周期同时进行位置更新以及足迹更新；在查询阶段，源节点生成的数据包向位置服务节点查询，在到达位置服务节点后传输至汇聚节点的一个足迹点；在追逐阶段，数据包沿足迹传输至汇聚节点。 理论分析与仿真实验结果显示，通过延长位置更新的周期可以大幅降低位置服务算法的能耗。 、针对事件驱动的传输特性，本文将足迹信息与在事件发生频率低时更加适用的算法，算法结合，设计了基于足迹的搜索算法，通过增加搜索到冃标信息的概率减少的搜索尝试次数，从而进一步降低能耗与时延。 、在引入足迹信息后，基于足迹的算法在追逐阶段存在不可忽视的传输冗余度，从而降低了算法的能效性。 因此本文设计了消除冗余度的机制，利用汇聚节点的足迹信息使数据包能够自主判断选择每一跳的传输终点，从而消除了传输部分的冗余度，使算法的能耗性能进一步提升。 关键词位置服务算法；足迹信息；搜索算法；传输冗余度；无线传感网（），（），（），（目录中文摘要绪论无线传感器网络的特性面对突发事件的无线传感网相关工作位置服务算法虚拟架构算法搜索算法足迹算法本文的主要工作第二章无线传感网移动性管理算法弓言无线传感网网络模型位置服务算法基于分组的位置服务算法基于区域的位置服务算法搜索算法本文设计目标第三章足迹更新算法弓目足迹的生成与维持！足迹的连通性网络模型足迹服务节点之间连续性足迹服务节点与位置服务节点的连通足迹上数据传输的冗余度本章小结第四章基于足迹的位置服务算法！引言基于足迹的位置服务算法介绍更新阶段查询阶段追逐阶段基于足迹的位置服务算法扩展性冗余度减少机制冗余度问题分析冗余度减少机制本章小结第五章基于足迹的位置服务算法性能分析引言基于足迹的位置服务算法理论分析更新能耗传输时延基于足迹的位置服务算法仿真实验足迹有效寿命的影响足迹连通性的分析冗余度减少机制分析位置更新周期的影响与位置服务算法的对比本章小结第六章基于足迹的搜索算法引言基于足迹的搜索算法介绍搜索阶段追逐阶段基于足迹的搜索算法性能理论分析基于足迹的搜索算法传输时延基于足迹的搜索算法能量消耗基于足迹的搜索算法仿真实验传输成功率能量消耗传输时延多个汇聚节点的场景本章小结总结与展望参考文献麵个人简历、在学期间的研究成果及发表的学术论文基于足迹的无线传感网位置服务算法研宄第一章绪论无线传感器网络的特性无线传感网丨，】（，简称）是由大量的传感器节点与部分汇聚节点组成的。 传感器节点包括数据感知、数据处理和通信模块，通常固定在所部署的网络中，能量和硬件资源有限，其通过无线通信的方式自组织丨地形成传感器网络，可以进行数据的收集与处理，检测网络部署区域的物理环境信息；汇聚节点可以是任何形式的有通信终端的设备或人员，能量供给充足，在网络中可以自由移动并负责收集传感器网络检测到的数据并作出相应处理。 无线传感网搭建了连接物理世界与信息世界之间的桥梁，使人们在感知物理环境的基础上可以进一步与环境进行互动，被视为构建物联网的重要基础。 目前无线传感网己经应用在许多网络场景中，比如环境监测、应急救援、工业控制等，通过传感器节点的配置完成对整个网络的控制，并将所需信息传输给汇聚节点进行收集处理。 无线传感网通常有以下特性？（）低事件发生频率？在大多数网络场景中，传感器节点需要监测的事件发生频率较低，频率变化区间为历到历，即平均事件间隔为数秒到数天时间。 （）高成功率要求在无线传感网中，汇聚节点需要根据传感器节点发送的包含事件信息的数据包对事件作出有效反应。 因此需要保证网络中进行数据传输的成功率。 （）低时延要求在大多数网络场景中不仅需要保证汇聚节点能够接收到传感器节点发送的数据包，而且事件信息具有很高的时效性，比如病人生命体征的变化或军事上监测敌情的变化等信息需要汇聚节点作出迅速的反应。 因此，当网络中有事件发生时，传感器节点生成的数据包需要在低时延内传输至汇聚节点。 （）低能耗要求无线传感网中当传感器节点配置完成后，如果节点能耗耗尽，通常难以对传感器节点进行更换，从而影响网络的拓扑结构，降低数据传输的成功率。 因此网络中的数据传输需要较低的能量捎耗。 （）汇聚节点的移动性无线传感网中的汇聚节点通常可以在网络中自由移动以执行具体的任务。 传感器节点通常无法获知汇聚节点的当前位置。 福州大学硕士学位论文面对突发事件的无线传感网无线传感网由于其自组织的特性，在不需要网络基站的情形下便能够进行数据的传输，因此目前在面对突发事件的网络场景中有广泛应用。 本节以地震灾后救援场景为例，分析无线传感网在面对突发事件的场景中的应用。 地歧害监测，爹、巧生命体征监测二；汇聚节点图地震灾后救援场景的无线传感网图是以地震灾后的救援场景为例的面对突发事件时无线传感网的示意图。 在此网络场景中需要收集的信息概括为以下几方面（）生命体征的监测在灾后对受灾人员进行搜索是灾后工作的首要任务，需要在整个受灾地区进行幸存人员的搜索。 （）伤员伤情的变化【】对于伤员需要进行实时监控，以使受伤人员能够得到及时的救治。 （）次生灾害险情的监测在地震灾害发生后灾区内通常伴随有滑坡、泥石流等多种次生灾害，需要对灾害隐患点进行实时监测，及时排除发生次生灾害的可能。 （）灾情评估在灾害发生后需要对灾区的受灾信息加以统计，进行灾情评估，为之后提供防灾支持。 通过对灾后所需信息的概括，可以发现首先灾害区域面积广阔，而且交通不便，同时有次生灾害等隐患，难以通过人力对灾区进行搜索和监控。 另外，由于灾害对于该区域的破坏，电力供应难以保证，并通常难以进行通信基站的建设，基于足迹的无线传感网位置服务算法研宄因此以通信基站为支持的移动通信网络和网络在此场景下难以应用。 而且，在灾后初期，救援人员紧缺，无法对所有伤员进行实时监控，如果伤员伤情发生变化，难以对其进行及时就诊。 最后，对灾区受灾信息的收集需要在网络中配置大量的节点，移动通信网络、网络或卫星通信网络都难以在短时间内进行大规模的构建的管理。 土这种情形下，无线传感网以其自组织的特性可以作为处理突发事件的有效方案。 具体地，首先可以通过空投的方式在整个受灾区域配置大量传感器节点，传感器节点在配置后不需要通过通信基站便能够进行相互之间的通信，因此在不需要人力进入灾区的情况下组成无线传感网从而对整个灾区进行监测与数据收集。 不同类型的传感器可以分别进行生命体征搜索、次生灾害隐患点监测等不同任务。 另外，医疗传感器节点可以配置在每个伤员身上，在伤员出现伤情变化时可以实时收集到伤情变化的信息。 在无线传感网中配置有汇聚节点对传感器节点收集到的信息进行收集并作出相应反应动作，汇聚节点可以是任何形式的具有通信终端的设备或人员。 汇聚节点在收到某区域传感器节点发送的搜索到生命体征信息时可以前往该区域进行营救，在收到某节点发送的伤员病情变化的信息时可以前往该伤员进行及时救治等等。 通过对无线传感网运行的描述，无线传感网的优势可以总结为以下几个方面（）采用自组织的方式，不需要电力支持和通信基站的建设，能够快速地大规模地构建无线传感网。 （）网络配置范围大，可以对整个网络区域进行大面积的小时的实时监测。 （）汇聚节点可以根据传感器节点发送的事件信息，及时到达准确区域并作出相应反应。 传感器节点可以有效地对网络区域进行实时监测，但是网络中的汇聚节点通常在网络中进行移动以执行具体的任务。 传感器节点在收集到有关信息后需要向移动的汇聚节点进行数据传输，但是通常难以获知汇聚节点的当前位置，而且传输过程对成功率、能耗、时延等参数均有较高要求。 因此需要对在无线传感网中解决汇聚节点移动性的数据传输协议进行研宄福州大学硕士学位论文相关工作目前己经有一些关于无线传感网中解决汇聚节点移动性的数据传输协议的研究。 这些传输协议通常分为三类位置服务算法、虚拟架构算法以及搜索算法。 本节对这些传输协议以及现有的关于足迹的算法进行简要的介绍。 位置服务算法在位置服务算法中，汇聚节点向一部分传感器节点更新其位置信息，检测到事件信息的源节点可以向这些所选传感器节点进行查询来获知汇聚节点的位置。 文献中，作者提出了一种基于本地更新的路由协议。 当汇聚节点在一个有限的圆形区域中移动时，此区域被定义为目标区域，区域内所有节点接收汇聚节点的位置信息。 当汇聚节点移动到另一个区域时，建立另一个目标区域。 文献中作者针对算法进行改进，当汇聚节点在目标区域中移动时可以自主调整位置更新的范围。 文献中，作者提出在大多数网络场景中，汇聚节点可以获知自身的移动策略，比如其目的地、移动轨迹、速度等。 因此，汇聚节点可以在更新的位置信息中加入其移动策略以提升数据传输的效率。 文献中的作者将基于分组的位置服务算法应用在现实中的不规则的网络区域中，将网络中没有传感器节点的空白区域以及非长方形区域加以考虑，提出了一种能耗平衡的汇聚节点位置服务算法来在网络中进行数据传输。 文献中介绍了一种基于区域的位置服务算法。 在中，所有传感器节点以及汇聚节点使用一个共用的哈希函数在网络中选取一个汇聚区域。 哈希函数的输入是节点的，输出可以是某些特定节点的或者事先决定的地理区域。 传感器节点和汇聚节点的数据传输与查询均经过此汇聚区域。 另一种类似于传统位置服务算法的传输方式是检测到事件信息的源节点将包含事件信息的数据包传输给网络中选定的部分传感器节点。 汇聚节点可以向这些选取的传感器节点查询是否有事件发生。 文献中作者提出了机制，在中源节点将数据包传输给事先决定的区域，此区域定义为汇聚区域。 这些数据包储存在汇聚区域的传感器节点中，直到有汇聚节点经过并收集。 位置服务算法的优点是通过位置服务节点将源节点与汇聚节点相联系，源节点可以通过位置服务节点获知汇聚节点的位置从而避免了盲目地进行广播，提升了数据传输的效率。 但位置服务算法的个明显的问题是位置服务节点需要吋刻储存汇聚节点的最新位置，因此汇聚节点需要频繁地进行位置更新。 在以事件为驱动的传感器网络中，只有当有事件被检测到时网络中才会有数据传输。 当事件发生的频率较低时，大量的位置更新是没有必要的，从而带来了大量的能耗浪费。 基于足迹的无线传感网位置服务算法研宄另外，数据包需首先经由位置服务节点再传输至汇聚节点，传输的路径得以延长，从而传输时延也有所增加。 虚拟架构算法虚拟架构算法是数据传输协议的重要组成部分。 文献中作者提出的算法在网络的中心构建了一个虚拟的垂直区域或条形区域，从而将整个网络分为两个相等的部分。 源节点将数据包传输至此虚拟区域，同时当汇聚节点需要查询事件报告时也向此虚拟区域查询，到达此区域后汇聚节点的查询数据包沿此区域直线传输，直到查询到储存有事件信息的传感器节点。 文献采用了类似于的算法，在网络中选取一个虚拟的四边形区域。 在这个四边形区域中的传感器节点作为源节点数据传输以及汇聚节点查询的终点连接源节点与汇聚节点。 虚拟架构算法与位置服务算法一样为数据传输预先设置了特定的路径从而提升了传输的效率。 但是虚拟架构算法通常使用固定的虚拟区域以协助数据传输，此区域内传感器节点相较其他区域的节点更加频繁地进行数据传输。 在无线传感网中，所有的传感器节点通常被配置相同的能量资源，因此虚拟架构算法会导致网络中能够不平衡，从而破坏网络的拓扑结构。 搜索算法搜索算法通常使用地理路由的方式向整个网络或网络中的某个方向进行泛洪查询最基础的搜索算法是当源节点检测到事件信息时，向自身所有邻节点发送数据包。 收到数据包的邻节点再作为数据传输的起点向自身的邻节点发送。 在源节点为中心一层层的泛洪中以最快的速度找到汇聚节点。 文献中，作者在源节点进行网络泛洪时对传输的最大跳数加以限制，将传输的范围加以限制，使每次事件发生不必向整个网络发送数据包从而减少了查询的代价。 在此有限的传输范围内如果汇聚节点收到该数据包，将会向源节点反馈一个确认信息。 当源节点在一定等待时间后没有收到汇聚节点确认信息，会再次发送包含事件信息的数据包，在一个更大的范围内再次搜索汇聚节点。 文献中作者提出了一种基于迭代的搜索算法，用于解决在传感器节点通过分簇进行数据传输的场景中每步传输首节点的选择问题。 在事先设置的传输路径中如果一跳传输失败，传输起点会在一个更大的广播范围内尝试，直到寻找到在此范围内的最佳路径进行传输。 考虑到数据拥塞或过度负荷会影响到整个网络性能的情况，文献中的作者考虑在应用休眠唤醒机制的无线传感网中，环境再污染问题会导致数据包的丢失，进而提出了算法，在泛洪传输过程中通过设福州大学硕士学位论文置可阻挡的能延伸的搜索范围以保证传输的成功率。 考虑到数据拥塞以及过度负荷等问题会影响到无线传感网的整体性能，文献中的作者提出了一种方法论，用于发现最近的邻节点以及最近路径来减少网络中泛洪带来的能量消耗。 搜索算法基于网络中进行泛洪的方式搜索汇聚节点，虽然能快速地寻找到汇聚节点，但每次搜索均需较大的能耗代价，从而不具备良好的扩展性，应用场景冶限。 算法虽然通过限制传输范围降低了每次搜索汇聚节点的能量消，但是一旦有失败的搜索尝试，便会带来网络中的重复搜索，能耗与时延性能均会有所下降。 足迹算法在无线传感网中汇聚节点留下足迹信息的算法也己有相关研究。 在文献中，作者利用了汇聚节点留下的足迹信息提升搜索效率。 当汇聚节点在网络中移动时通过广播含有自身位置的数据包形成一条连续的足迹，源节点发送的数据包在网络中传输以寻找汇聚节点本身或者汇聚节点留下的足迹信息，当足迹信息被数据包查询到，该数据包便会沿着这条足迹找到汇聚节点。 但是，足迹信息的搜索过程以及留足迹的挑战在这篇文章中并没有进行系统地研宄。 为了保证足迹上的数据传输，文献中的作者提出了一种基于足迹协议基础的增强准确性的方法，能够确认足迹上的数据传输。 文献中，作者提出了一种分簇的基于足迹的算法。 当汇聚节点广播位置信息时，向一个大于自身一次传输距离的范围内广播，此广播范围内的节点形成一个簇，簇内的传输路径在汇聚节点广播时同时确定。 源节点发送的数据包查询到一个簇时，便能够在簇与簇之间进行传输，最终找到汇聚节点。 但是，当汇聚节点以随机的模式移动时，大多数的本身存有位置信息的节点需要频繁更新汇聚节点发送的新的位置信息，这会造成大量的能耗浪费。 本文的主要工作通过对无线传感网中相关工作的分析，现有的算法都存在着算法不可避免的缺陷，影响了算法的扩展性。 另外，关于汇聚节点的足迹信息现有工作并没有进行进一步深入的研宄。 因此在本文中首先介绍一些典型的现有算法作为本文算法的基础框架；然后针对汇聚节点的足迹信息进行研宄分析，包括汇聚节点足迹信息的生成与维持，足迹的连通性，以及引入足迹信息带来的在足迹上进行数据传输的传输冗余度问题；之后，本文将足迹信息与位置服务算法相结合，提出基于足迹的位置服务算法，通过延长位置服务算法中位置更新的周期，提升现有位置服务算法的性能；最后，考虑到网络中事件发生频率进一步降低的场景，选取更基于足迹的无线传感网位置服务算法研究加适用于低事件频率特性的算法为基础框架，提出基于足迹的搜索算法，通过增加搜索到目标节点的概率，提升了现有搜索算法的性能，使基于足迹的算法具有良好性能的同时也具备良好的扩展性，能够应用在广泛的网络场景中。 本文具体安排如下第一章绪论，主要介绍了无线传感网的基本特性，之后对在无线传感网中进行数据传输的现有算法，包括位置服务算法、虚拟架构算法、搜索算法以及足迹算法进行了简单介绍，并分析了现有工作存在的缺陷，最后对本文的研宄思路进行概括描述。 第二章首先介绍无线传感网的网络模型，之后选择现有算法作为本文研宄基础框架，包括基于分组的位置服务算法、基于区域的位置服务算法、搜索算法并选取各自的代表算法进行算法描述，最后介绍本文的设计目标。 第三章在本章中对本文引入的足迹信息进行研宄分析，首先介绍了一种低能耗的足迹生成与维持的方式。 之后通过理论分析得出保证足迹的连通性需要满足的条件，得出对算法参数设置的参考。 最后阐述引入足迹会带来的在足迹上进行数据传输的冗余度问题。 第四章首先选取基于分组的位置服务算法中的一种典型算法，算法作为基础框架提出了基于足迹的位置服务算法，算法。 对的三个阶段，更新阶段、搜索阶段以及追逐阶段作出详细描述。 之后将扩展到与基于区域的位置服务算法中的一种典型算法，算法相结合，使本文提出的算法能够应用在所有现有的位置服务算法中，并且在有良好扩展性的同时具有良好的性能。 最后，通过仿真实验分析了引入足迹信息带来的足迹上进行数据传输的冗余度问题，并提出减少冗余度的机制消除传输冗余度，进一步提升了算法的能效性。 第五章通过理论