[發明專利]無線傳感器網絡中移動數據收集器的移動路徑規劃方法

在審

• 申請號: 201611213916.0
• 申請日: 2016-12-23
• 公開（公告）號: CN106658539A
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 劉文軍;何福男;羅穎;孫偉;朱東
• 申請（專利權）人: 蘇州工業職業技術學院
• 主分類號: H04W16/22
• 分類號: H04W16/22;H04W40/02;H04W40/12;H04W84/18
• 代理公司: 上海漢聲知識產權代理有限公司31236
• 代理人: 邵曉麗,胡晶

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：構建以π為根連接所有支配節點最小生成樹T_R

基于構建的支配節點，應用PRIM算法，構建以π為根連接所有支配節點最小生成樹T_R；

S162：對T_R應用近似算法產生所述移動數據收集器的移動軌跡。

2.根據權利要求1所述的無線傳感器網絡中移動數據收集器的移動路徑規劃方法，其特征在于，所述步驟S162具體為：對T_R應用Christofides-1.5近似算法產生所述移動數據收集器的移動軌跡，令U為所述移動數據收集器的移動軌跡，LEN為其長度，則有：

LEN(U)≤1.5LEN(T_R)

利用上述兩公式，得到移動數據收集器的移動軌跡長度界如下：

其中，表示生成樹TR的邊集。

3.根據權利要求1所述的無線傳感器網絡中移動數據收集器的移動路徑規劃方法，其特征在于，所述步驟S14中的所有的DN節點向k跳未確定父節點的鄰居發送或轉發DN聲明消息，最先收到DN聲明消息的節點變為該DN節點的成員節點具體為：

任意的DN節點首先向其直接鄰居發送DN聲明消息，且DN聲明消息在網絡中至多傳播k跳，網絡中任一節點收到來自不同節點發送的DN聲明消息，僅記錄首先收到的節點為父節點，并轉發至其余鄰居，后續收到的DN聲明消息被丟棄。