[發明專利]一種基于導向粒子群算法的節點部署方法

有效

• 申請號: 201611240453.7
• 申請日: 2016-12-29
• 公開（公告）號: CN106792750B
• 公開（公告）日: 2019-11-12
• 發明（設計）人: 陳侃松;沈超;戴磊;葉波;郭琳
• 申請（專利權）人: 湖北大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W84/18
• 代理公司: 北京高沃律師事務所 11569
• 代理人: 王加貴

本發明公開了一種基于導向粒子群算法的節點部署方法，所述節點部署方法包括：步驟一：將多個傳感器在待監測區域內隨機部署；步驟二：在節點虛擬力與網格虛擬力的作用下，帶動節點移動，獲得對應節點的更新位置和更新速度；步驟三：計算在待監測區域內各節點的網絡覆蓋率及全局最優覆蓋率；步驟四：通過重復交叉操作，生成新的節點群；步驟五：計算所述新的節點群的覆蓋率；步驟六：判斷所述新的節點群的覆蓋率是否大于所述全局最優覆蓋率，如果是，則根據所述新的節點群的覆蓋率更新全局最優覆蓋率；否則，執行步驟二。本發明節點部署方法可快速確定全局最優覆蓋率，以實現對傳感器的節點部署。

技術領域

本發明涉及傳感器網絡監測技術領域，特別是涉及一種基于導向粒子群算法的節點部署方法。

背景技術

無線傳感器網絡(wireless sensor networks,WSN)由部署在待監測區域內的大量微型、廉價、低功耗的傳感器節點集合成，通過Ad-hoc方式形成一個多跳的網絡系統，目的是協作的感知、采集和處理網絡覆蓋地理區域中感知對象的信息，并發布給觀察者。為了增強無線傳感器網絡的監測質量、提高網絡可靠性，必須保證傳感器節點的部署能夠有效地覆蓋目標區域。然而，由于傳感器節點的能量有限特性及其應用區域的特殊性，無線傳感器網絡大多通過飛機布撒等方式在待監測區域拋放高密度節點以消除覆蓋盲區。然而，傳感器節點的高密度部署通常會使得大量節點的待監測區域相互交疊，這種覆蓋冗余直接導致共享無線信道的節點之間相互競爭和通信干擾，不僅影響數據傳輸的可靠性，而且會引發較大的能量開銷。如何通過有效的覆蓋控制與節點重部署策略改善網絡的初始部署成為無線傳感網絡的研究中的關鍵問題。

虛擬力算法是由密歇根大學的Koren和Borenstein在20世紀80年代提出的可以讓移動機器人在未知的環境中規避障礙物的算法。Zou等人首先將虛擬力算法應用于傳感器網絡。虛擬力算法是有關多目標的自組織算法。

單獨將原始虛擬力算法應用于傳感器網絡部署問題上，由于傳感器節點之間存在力的作用,不可避免的使區域覆蓋中受力平衡的一些節點之間存在覆蓋盲區,從而不能實現完全覆蓋待監測區域，只能達到比較滿意的覆蓋要求。有些傳感器節點按照算法在執行的時候可能在一定范圍內來回移動，從而消耗大量不必要的能量。

此外，目前還有將PSO粒子算法應用待傳感器網絡中。其中，PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己：第一個就是粒子本身所找到的最優解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優解，這個極值是全局極值。另外也可以不用整個種群而只用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。假設在一個D維的目標搜索空間中，有N個粒子組成一個群落，其中第i個粒子為一個D維的向量X_i＝(x_i1,x_i2,...,x_iD),i＝1,2,...,N，第i個粒子的“飛行”速度也是一個D維的向量，記為V_i＝(v_i1,v_i2,...,v_iD),i＝1,2,...,N，第i個粒子迄今為止搜索到的最優位置稱為個體極值，記為P_best＝(p_i1,p_i2,...,p_iD),i＝1,2,...,N，整個粒子群迄今為止搜索到的最優位置為全局極值，記為g_best＝(p_g1,p_g2,...,p_gD)，在找到這兩個最優值時，粒子根據如下的公式來更新自己的速度和位置：

v_id＝w×v_id+c₁ r₁(p_id-x_id)+c₂r₂(p_gd-x_id)