GEAR协议中贪婪算法及查询消息传播的优化方法

摘要

本发明公开一种GEAR协议中贪婪算法及查询消息传播的优化方法，包括：在节点邻居列表中增加sum域用来记录比本节点估计代价小的邻居节点数，若某节点所有小于其估计代价的邻居节点的sum域值均为零，该节点将被纳入查询消息中添加的黑名单域中；sum域值不为零且未被纳入黑名单的邻居节点中代价最小的将被选中为下一跳节点；事件区域内的节点寻找估计代价最小的邻居节点作为自己的唯一母节点，母节点会将其记录为自身子节点，当查询消息在事件区域中传播时，当前节点的所有子节点将被选中为路径的下一跳节点。本发明有助于躲避一跳内的空洞节点，同时子节点和唯一母节点的设置减少了事件区域内传送查询消息的能耗。

说明书

技术领域

本发明涉及无线传感器网络路由协议，特别涉及地理位置路由协议GEAR中贪婪算法造成的路由空洞问题和查询消息传播问题，属于无线传感器网络通信技术领域。

背景技术

路由协议负责将数据分组从源节点通过网络转发到目的节点，基于地理位置信息的路由协议是把节点的位置信息作为路由选择的依据，不仅能够完成节点路由功能，还可以降低系统专门维护路由协议的能耗。

基于地理位置信息的路由协议的目标是在诸如目标跟踪类应用中，能够根据需要唤醒距离跟踪目标最近的传感器节点，以得到关于目标的更精确位置等相关信息。

无线传感器网络中GEAR地理位置路由协议传送查询消息到事件区域中所有节点的过程分为两个阶段：事件区域传送和域内传送。事件区域传送阶段为汇聚节点发送查询消息到达事件区域代表节点的过程，域内传送阶段为查询消息在事件区域内传播的过程。在事件区域传送查询消息阶段，从汇聚节点开始采用贪婪算法建立路径，即根据公式                                                计算自己距离事件区域的估计代价，其中，为节点N到事件区域R代表节点的估计代价，为节点N到事件区域R代表节点的距离，为节点N的剩余能量，为比例参数，选择最小估计代价的邻居节点作为传送的下一跳节点。在域内传送查询消息阶段，可通过以下两种方式让查询消息在域内扩散：当节点密度比较小时，直接采用洪泛转发机制，节点密度较大时，则采用迭代转发机制，直到域内剩下唯一的节点。

GEAR路由协议传送查询消息到事件区域过程中存在两个关键问题：路由空洞问题和查询消息传播问题。经过近十几年的发展，涌现出大量的研究成果，针对路由空洞问题主要提出了遇到空洞路由区域，改变自身节点代价并反馈给邻居节点即反馈避免的改进方法，但是该方法无法在第一次传递查询消息时使传输路径有效避开空洞节点从而也造成的能耗的浪费，还有的从理论上分析了路由空洞在规则部署和随机部署情况下的存在概率，但是其改进方法在邻居节点数大于10的情况下才有效。（1、张耀，贾振红.求解路由空洞问题的GEAR改进算法[J].计算机工程,2008,34(12):94-96. 2、蒋阳,孙柳林,袁敏,etc.一种解决GEAR路由空洞问题的新方案[J].传感器与微系统, 2011, 30 (4) : 44-47. 3、田乐,谢东亮,任彪,张雷,etc.无线传感器网络贪婪转发方法中的路由空洞问题[J].电子与信息学报,2007,29(12):2996-3000.）对于查询消息传播问题，目前提出的方法除了洪泛传播方式之外，还有通过将网络分区域选举簇首节点，通过簇首节点来传递查询消息，该方法需要网络选举簇首节点，增加了网络开销。（1、Yu Y, Govindan R, Estrin D. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks. UCLA Computer Science Department Technical Report UCLA /CSD-TR-01-0023, May 2001.2、孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005.3、王艳琴.地理位置路由协议GEAR的分析与改进[J].单片机与嵌入式系统应用,2011,(08):1-5.）。

发明内容

本发明的目的在于提供一种GEAR协议中贪婪算法路由空洞问题和查询消息传播开销过大的解决方法，使查询消息在传播到事件区域中的每个节点的过程中，能够有效避开路由空洞，同时减少查询消息在事件区域中的传播能耗。

实现本发明目的的技术解决方案为：GEAR协议中贪婪算法及查询消息传播的优化方法，主要内容如下：

汇聚节点在查询消息中添加黑名单域用以记录网络中所有小于其距离事件区域估计代价的邻居节点全为空洞节点的节点，网络中所有节点在其邻居列表中增加sum域用以记录小于其距离事件区域估计代价的邻居节点数量。节点将比自己距离事件区域估计代价小的邻居节点的数量添加到节点邻居列表中新增加的sum域中，sum域值为零表示该节点没有比其距离事件区域代表节点更近的邻居节点。

在事件区域传送阶段即查询消息从汇聚节点传送到事件区域代表节点的阶段中，节点选择下一跳节点时，查询邻居节点中是否存在满足不在黑名单中、比自己距离事件区域估计代价小且sum域值不为0的节点，如果存在则选择同时满足上述三个条件且估计代价最小的邻居节点为下一跳节点。如果不存在，即说明该节点的邻居节点是由空洞节点和高估计代价节点所组成，那么则选择高估计代价邻居节点中估计代价最小的作为下一跳节点，并将本节点纳入黑名单中，以避免再次被选中为传输路径节点。依次选择下一跳节点，直到节点的邻居节点中出现事件区域的代表节点，则最后一跳的节点成功找到，完成路由第一阶段转发查询消息的任务。

在域内传送阶段即查询消息在事件区域内传播阶段中，事件区域中的所有节点在小于其距离事件区域估计代价的邻居节点中选择估计代价最小的节点作为自己的唯一母节点，如果其所有邻居节点的估计代价均比自己的估计代价大，则选择已经寻找到母节点且母节点非自己的邻居节点中估计代价最小的作为自己的唯一母节点，如果上述条件均不满足，则选择估计代价最小的邻居节点作为自己的唯一母节点，并通过Hello消息告知母节点自己选择其为唯一母节点的消息，同时母节点将其纳入子节点列表，在事件区域内传递查询消息时，获得查询消息的节点将根据自身的子节点列表传播查询消息到子节点。

本发明与现有技术相比，其显著优点：（1）在传播查询消息到事件区域代表节点的过程中，传输路径可以有效避开一跳内的空洞节点，避免了能量浪费。（2）黑名单随着查询消息传输下去，跟随采集数据发送回汇聚节点，汇聚节点在下一次发送查询消息到同一片事件区域时，可以结合黑名单选择传输路径，有效节省了计算黑名单节点估计代价的能耗；（3）在事件区域内广播查询消息过程中，采用唯一母节点的方法，可以避免洪泛方式导致的同一节点重复接收同一查询消息，节约能量的同时也为接下来传送监测数据开辟有效路径节省了传输能耗。

下面结合附图对本发明作进一步详细描述。

附图说明

图1是本发明关于查询消息发往事件区域代表节点的算法流程图。

图2是本发明关于事件区域中为广播查询消息各节点寻找自己唯一母节点的算法流程图。

图3是本发明关于查询消息传播到事件区域内各个节点的算法流程图。

具体实施方式

结合图1，GEAR协议中贪婪算法及查询消息传播的优化方法，传播查询消息到达事件区域代表节点的步骤如下：

第一步，查询汇聚节点所有邻居节点是否都存在于黑名单中，如果均存在于黑名单中，则清空黑名单，重新开始查询消息的传播，然后进行第二步。否则，直接进行第二步。

第二步，当前节点遍历自己的邻居节点，如果邻居节点中存在事件区域代表节点，则直接选择其为下一跳节点，结束查询消息传送到事件区域代表节点过程。否则，进行第三步。

第三步，当前节点在邻居节点中查找是否存在比自己估计代价小、sum域不为零且不存在于黑名单中的节点，如果存在，则选择其为下一跳节点，将下一跳节点选为当前节点，从第二步开始继续下一跳节点的选择。如果不存在，则进行第四步。

第四步，当前节点的邻居节点中，所有小于其估计代价的邻居节点的sum域均为零或部分为零部分存在于黑名单中甚至全部存在于黑名单中，则将当前节点列入黑名单中，然后在大于其估计代价的邻居节点中选择最小估计代价的邻居节点作为下一跳节点，再将该下一跳节点选为当前节点，从第二步开始，继续路径的下一跳查找。

结合图2，GEAR协议中贪婪算法及查询消息传播的优化方法，查询消息在事件区域中传播的步骤如下：

第一步，当前节点在小于其估计代价的邻居节点中选取距离事件区域估计代价最小的节点作为自己的唯一母节点，如果存在，则选择其作为自己的母节点，并通过Hello消息传递信息告知母节点，母节点同时标记其为子节点。如果不存在，则进行第二步。

第二步，查找是否存在已经找到母节点且母节点不为当前节点的邻居节点，如果存在，则选择其中估计代价最小的为当前节点的母节点。如果不存在，则进行第三步。

第三步，选择估计代价最小的邻居节点作为自己的唯一母节点，同时从第一步开始重新查找该邻居节点的唯一母节点。

结合图3，GEAR协议中贪婪算法及查询消息传播的优化方法，查询消息从汇聚节点到达事件区域内各个节点的传播步骤为：

第一步，查询消息从汇聚节点按照图1所示步骤传播到事件区域代表节点。

第二步，按照图2所示步骤事件区域内的各个节点均寻找到自己的唯一母节点，其母节点也记录好自己的子节点，其子节点不唯一。

第三步，查询消息从事件区域代表节点开始，依次被广播到当前所在节点的子节点上，直至节点没有子节点则传播结束。