[發明專利]一種基于概率比較的無線傳感網拓撲構建方法

有效

• 申請號: 201410062068.2
• 申請日: 2014-02-24
• 公開（公告）號: CN103945508B
• 公開（公告）日: 2017-09-05
• 發明（設計）人: 洪榛;李喜樂;王瑞;谷銀銀;陳本永
• 申請（專利權）人: 浙江理工大學
• 主分類號: H04W52/02
• 分類號: H04W52/02;H04W84/18
• 代理公司: 杭州斯可睿專利事務所有限公司33241
• 代理人: 王利強

技術領域

本發明涉及無線傳感網領域，尤其涉及的是一種基于概率比較的無線傳感網拓撲構建方法。

背景技術

無線傳感器網絡(Wireless Sensor Networks,WSNs)是一個無線自組織網絡，它由大量資源受限的傳感器節點組成。基于WSNs的特性，可用較低的成本靈活地解決大量監測問題，尤其是一些危險區域的監測問題。節點在網絡通信、數據處理等方面需要消耗大量能量，且節點能量不易得到及時補充。因此如何降低能耗，盡可能延長網絡生存時間是WSNs急需解決的問題。而拓撲控制是解決此類問題的有效手段之一，其中拓撲構建則是拓撲控制的首要過程

自Ephremides A和Guha S提出利用近似算法計算連通支配集(Connected Dominating Set,CDS)尋找虛擬骨干網(Virtual Backbone)，基于CDS的拓撲控制技術成為WSNs中構建精簡拓撲的一個最普遍方法。現有文獻中構建CDS的方法主要有三種：1)剪枝方法，先選擇一個含有較多節點的連通集，再基于這個節點集將冗余節點刪除。2)最大獨立集(Maximal Independent Set,MIS)方法，尋找一個能夠覆蓋全面區域的獨立集，該獨立集無法再包含其它任一節點，然后選擇最少的節點作為網關節點，連接各個獨立節點。如EECDS通過四色著色方法，利用著色機制將不同狀態的節點區分，以此來判斷出MIS節點和non-MIS節點；尋到MIS后，再利用著色機制尋找網關節點，將網絡中所有的MIS節點連接，而這些網關節點和MIS節點便是整個網絡的活動節點。利用EECDS方法構造的樹活動節點數較多，能量消耗較快。3)樹構造方法，先選擇一個初始點(sink節點)，通過廣播信息尋找CDS的支配節點，直到節點覆蓋整個網絡。如A3算法，通過節點間信息的廣播、回復和確認，構建一個次優連通支配集。它的消息復雜度和計算復雜度都較低，且在它的構建過程中，能耗比和發送的消息數都呈線性關系。該算法延長了網絡的生命周期，但它在二次喚醒這一過程中，卻有不必要的消息發送和能量損耗。二次喚醒在節點較少的情況下，能夠保證網絡連通性和覆蓋性，但在節點較多或節點密度較大的情況下，將消耗不必要的能量。這對只能依靠自身攜帶能量工作的傳感器節點很重要。

因此，對于無線傳感網中節點能耗問題，急需一種更優方法來解決。

發明內容

為了克服現有無線傳感網拓撲控制方法中的能耗問題，尤其是節點二次喚醒的能耗問題，本發明提供了一種節省網絡能量消耗延長網絡生命的適用于無線傳感網的樹型拓撲構建方法。

本發明解決其技術問題所采用的技術方案是：

一種基于概率比較的無線傳感網拓撲控制方法，所述構建方法包括以下步驟：1)初始情況下，無線傳感網的各個節點隨機分布且連通，選擇sink節點為初始節點，發送hello消息給其鄰居節點，并根據消息到達的先后將其標記；

2)鄰居節點收到hello消息后，根據節點剩余能量和節點間距離，計算權值，并向sink節點發送一消息，該消息包含自身節點的標記號和權值，權值的計算公式為：

其中，x是候選者節點，y是它的父節點，ω表示能量權重，(1-ω)則為距離權重，E_x是節點x的剩余能量，E_max是節點最大的初始能量，D_x,y是節點x和y之間的距離，D*是兩個節點間能夠通信的最大距離；

3)Sink節點接收到消息之后，按照權值大小降序排列，形成排序表，并計算子節點個數；之后sink節點廣播含有該表的確認消息，節點根據排序表順序知道自身優先度，則在表中有優先特權的節點首先標定為active節點，并向其鄰居節點發送消息；該消息含有發送消息節點的標記號與權值，通知接收消息的節點暫時沒有資格成為active節點，而成為reserving節點；在這一階段只有未收到該消息的節點才有可能競爭成為active節點；

4)節點競爭過程：成為reserving節點后，節點將會根據同層競爭機制選擇最優父節點；

5)節點數計算比較過程：父節點接收子節點的個數值之后，進行累加計算，并將計算值發送給前一跳父節點，迭代執行該過程，直至發送到sink節點。Sink節點將當前計算層的總節點數統計之后，將其代入對應層的公式，計算該統計值對應出現的概率，確定節點是否需要二次喚醒，所述概率的計算公式為：