[發(fā)明專利]一種基于集合最大流算法的WSN柵欄修復(fù)方法

在審

• 申請?zhí)枺?/td>: 201611080748.2
• 申請日: 2016-11-30
• 公開（公告）號: CN106792742A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計）人: 錢麗萍;李鵬歡;黃亮;吳遠
• 申請（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W24/04;H04W84/18
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司33241
• 代理人: 王利強

1.一種基于集合最大流算法的WSN柵欄修復(fù)方法，其特征在于：包括如下步驟：

步驟1:柵欄間隙計算；

步驟1.1:根據(jù)已知位置節(jié)點計算得到柵欄間隙集合Gap；

步驟2:柵欄修復(fù)；

步驟2.1:可修復(fù)柵欄間隙的數(shù)量統(tǒng)計；

步驟2.1.1:以步驟1.1得到的柵欄間隙集合Gap為輸入，修復(fù)間隙所需要的移動節(jié)點數(shù)量如公式(1)所示：

式(1)中L表示間隙長度，R表示傳感器節(jié)點的感知半徑，mnum表示需要的移動節(jié)點數(shù)量，對間隙均勻分為mnum段，每段中點為移動節(jié)點的待修復(fù)點，得到整條柵欄待修補點的集合GD；

步驟2.1.2：以步驟2.1.1得到的待修補點集合GD為輸入和移動節(jié)點集合為條件，以距離D為閾值建立待修補點的鄰居移動節(jié)點，得到各修補點的鄰居移動節(jié)點集合NG；

步驟2.1.3：基于移動鄰節(jié)點集合的最大流算法解決間隙修復(fù)問題，具體步驟如下所示：

步驟2.1.3.1：分別計算出專屬于待修補點的鄰居移動節(jié)點集合，剔除公共集合，得到對應(yīng)的所有待補點的移動鄰居節(jié)點集合NG’；

步驟2.1.3.2：以步驟2.1.3.1得到的待補點和其對應(yīng)的集合NG’為輸入，集合元素的數(shù)量為權(quán)重值建立有向圖G；

步驟2.1.3.3：采用最大流算法計算圖G的最大流，最大流等于待修復(fù)點的數(shù)量，柵欄間隙能被全部修復(fù)，否則間隙不能被修復(fù)；

步驟2.2：柵欄間隙修復(fù)；

步驟2.2.1，以步驟2.1.3.1得到待補點的移動鄰居節(jié)點集合NG’為輸入，利用移動節(jié)點修復(fù)柵欄的間隙，并且使得移動節(jié)點的移動距離最小，集合NG’中的可移動節(jié)點到它的鄰居薄弱點的距離集合為MD＝{md₁,md₂,md₃,...md_num|md_i≤md},md_i(i∈{1,2,…,num})為鄰節(jié)點集合到待修復(fù)點的距離，num為所有移動節(jié)點的個數(shù)，對集合MD升序排序得到集合MD'，采用二分查找法搜索md_optimum，md_min＜md_optimum＜md_max，md_min和md_max為升序得到的最小值和最大值，使得滿足集合ED＝{MD'|md_i≤md_optimum}的移動節(jié)點恰好能強化所有的薄弱點，則此時移動節(jié)點移動的距離總和最小，二分法算法具體步驟為：

步驟2.2.1.1：初始化L＝0，

步驟2.2.1.2：更新薄弱點的鄰居子集合NG’，將距離待修復(fù)點大于md_optimum的節(jié)點從鄰居集合NG’中移除，并更新有向圖G的權(quán)重和拓撲；

步驟2.2.1.3：計算有向圖G的最大流，如果最大流小于n，n為待修補點集合GD元素數(shù)量，則L＝optimum，如果最大流等于n，且|L-optimum|≤ε，輸出md_optimum；

步驟2.2.1.4，算法結(jié)束，否則執(zhí)行步驟2.2.1.2。