一种基于移动Sink数据收集的低能耗路由树枝剪方法

摘要

本发明提供一种基于移动Sink 数据收集的低能耗路由树枝剪方法，首先建立能耗模型,然后建立基于路由树的移动Sink数据收集网络模型，在此基础上提出一种基于贪心策略的低能耗路由树枝剪方法。该方法将整个网络划分成若干个路由树,树根为汇聚节点,其余节点将数据转发至其汇聚节点,初始时默认移动Sink 通信半径范围内的节点为汇聚节点，通过广播消息建立路由树，此时移动Sink 的时延达到最优，而传感器网络的整体能耗最大。本发明通过贪心策略寻求当前最佳枝剪位置，枝剪初始路由树，使其枝剪节点成为新的汇聚节点，降低传感器网络的整体能耗。相对于传统的经典基于分层拓扑的移动Sink 数据收集方法，该方法在Sink收集数据移动路径长度受限情况下，能有效降低全网能耗。

主权项

一种基于移动Sink 数据收集的低能耗路由树枝剪方法，其特征在于，在建立和优化网络拓扑路由树时的步骤如下：步骤一：移动Sink 根据消息格式MSG广播消息，通信半径范围内的传感器节点收到消息后，反馈确认消息ACK，成为初始汇聚节点，初始汇聚节点继续广播消息；步骤二：汇聚节点通信半径范围内的传感器节点收到汇聚节点的广播消息后，反馈确认消息ACK，成为该汇聚节点的子节点，子节点继续广播消息；步骤三：子节点附近的传感器节点收到消息后，反馈确认消息ACK，成为广播消息的子节点的后继，子节点的后继继续广播消息；步骤四：重复步骤三, 直到某个传感器节点广播消息之后,在T时间后没有收到确认消息ACK，则此传感器节点成为叶子节点；当全网没有落单的传感器节点之后,Sink节点开始收集全网传感器节点信息，通过叶子节点逐层反馈的形式，将每个节点的信息MSG_ACK转发到Sink节点，以顺序存储的方式存储在Sink节点中；步骤五：将Sink节点中存储的每个节点信息依次读取出来，按照构造二叉平衡树的步骤构建二叉平衡树链表存储结构，将顺序存储改为链式存储；步骤六：根据构建的二叉平衡树查找Q值最大的节点，记录其节点信息，并且根据节点信息中记录的上一跳节点，逐个查找，寻找一条枝剪链路；步骤七：根据枝剪链路，通过移动Sink广播数据链路节点信息寻找网络拓扑路由树中的枝剪节点，将此枝剪节点做为新的汇聚节点；步骤八：计算Sink节点与汇聚节点（除初始汇聚节点外）和汇聚节点（除初始汇聚节点外）之间的距离，汇聚节点之间形成一个无向图；步骤九：通过旅行商算法计算移动Sink到各个汇聚节点（除初始汇聚节点外）收集数据的最短路径，如果<，对Sink节点中顺序存储的现有的传感器节点的信息进行调整，包括节点信息中被枝剪节点的层数，子节点个数等；重复步骤六至步骤九，重新生成平衡二叉树，再次进行枝剪操作；否则，放弃本次枝剪操作，路由树优化完成，形成移动Sink收集数据的移动轨迹。