无线传感器网络中移动数据收集器的移动路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106658539A(43)申请公布日2017.05.10(21)申请号201611213916.0(22)申请日2016.12.23(71)申请人苏州工业职业技术学院地址215104江苏省苏州市苏州国际教育园致能大道1号(72)发明人刘文军何福男罗颖孙伟朱东(74)专利代理机构上海汉声知识产权代理有限公司31236代理人邵晓丽胡晶(51)Int.Cl.H04W16/22(2009.01)H04W40/02(2009.01)H04W40/12(2009.01)H04W84/18(2009.01)权利要求书2页说明书6页附图3页(54)发明名称无线传感器网络中移动数据收集器的移动路径规划方法(57)摘要本发明公开了一种无线传感器网络中移动数据收集器的移动路径规划方法，网络中任意节点分布式执行，且任意节点到支配节点的路由跳数不超过中继跳数k，包括：网络初始化与ID分配；成员节点确定；重复上述步骤至多k次，完成第一轮节点状态确定；支配节点确定与消息传播；重复上述步骤，完成第二轮节点状态确定，直至网络中所有状态未确定的节点要么是MN，要么是DN；计算所述移动数据收集器的移动轨迹。本发明的无线传感器网络中移动数据收集器的移动路径规划方法，网络中节点到支配节点的跳数不超过k，降低了数据收集的延迟，通过对支配节点负载和分布的有效调整，移动数据收集器的移动轨迹长度得到有效缩短，在延迟方面进一步提升。CN106658539ACN106658539A权利要求书1/2页1.一种无线传感器网络中移动数据收集器的移动路径规划方法，其特征在于，网络中任意节点分布式执行，且任意节点到支配节点的路由跳数不超过中继跳数k，其包括以下步骤：S11：网络初始化与ID分配初始时，按照确定的节点通信范围R，整个网络构成通信拓扑G(V，E)，网络中节点x的邻居记为N(x)，按照节点距离移动数据收集器的初始位置π的距离大小为每个节点分配一个ID，距离所述移动数据收集器越远的节点的ID越大，反之，则ID越小，所有节点的状态均为状态未确定，记为UN，其中，V表示网络中的所有节点集合，E表示通信范围R内节点间存在的通信链路集合；S12：成员节点确定如果当前节点x的ID大于其所有邻居N(x)的ID，则节点x变为成员节点，记为MN，并从原网络中剪除，节点x记录ID号最小的邻居为其路由树的父节点，记为i-PN；如果当前节点x与其所有邻居N(x)构成完全图，且x∪N(x)的ID比其所有邻居N(x∪N(x))中节点的ID更大，则除了ID号最小的邻居外均变为MN，节点x记录ID号最小的邻居为其路由树的父节点，记为i-PN；S13：重复步骤S11～S12至多k次，完成第一轮节点状态确定，具体包括以下流程：S131：对满足步骤S12中的条件的当前节点x，如果其自身为父节点i-PN，则节点x选择新父节点记为(++i)-PN，其自身变为成员节点；不足k次，为单独节点，则该节点为支配节点，记为DN，终止循环；S132：如果算法提前结束，状态未确定且其邻居的状态为成员节点的节点变为支配节点，记为DN，此时所述网络中DN和路由树构建完成；S133：对于每一次循环，如果节点x的i-PN选择一个新父节点，则该节点记为(++i)-PN，且初始的i-PN变为其成员节点；S14：支配节点确定与消息传播将上述所确定的网络中的父节点的状态变为支配节点，记为DN，所有的DN节点向k跳未确定父节点的邻居发送或转发DN声明消息，最先收到DN声明消息的节点变为该DN节点的成员节点，并从网络中剪除，此时形成第一批k-hop支配节点及受其支配的成员节点；S15：重复步骤S11～S14，完成第二轮节点状态确定，直至网络中所有状态未确定的节点要么是MN，要么是DN；S16：计算所述移动数据收集器的移动轨迹，具体包括：S161：构建以π为根连接所有支配节点最小生成树TR基于构建的支配节点，应用PRIM算法，构建以π为根连接所有支配节点最小生成树TR；S162：对TR应用近似算法产生所述移动数据收集器的移动轨迹。2.根据权利要求1所述的无线传感器网络中移动数据收集器的移动路径规划方法，其特征在于，所述步骤S162具体为：对TR应用Christofides-1.5近似算法产生所述移动数据收集器的移动轨迹，令U为所述移动数据收集器的移动轨迹，LEN为其长度，则有：LEN(U)≤1.5LEN(TR)2CN106658539A权利要求书2/2页利用上述两公式，得到移动数据收集器的移动轨迹长度界如下：其中，表示生成树TR的边集。3.根据权利要求1所述的无线传感器网络中移动数据收集器的移动路径规划方法，其特征在于，所述步骤S14中的所有的DN节点向k跳未确定父节点的邻居发