[發明專利]基于二進制粒子群算法的無線傳感器網絡節點分層調度方法

無效

• 申請號: 201310171940.2
• 申請日: 2013-04-25
• 公開（公告）號: CN103249055A
• 公開（公告）日: 2013-08-14
• 發明（設計）人: 張軍;詹志輝
• 申請（專利權）人: 中山大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W72/12;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域：

本發明涉及無線傳感器網絡和計算智能兩大領域，具體涉及一種基于二進制粒子群算法的無線傳感器網絡節點分層調度方法。

技術背景：

無線傳感器網絡(wireless?sensor?networks，WSN)是一項新興的技術并且已經成為了當今社會熱門而富有挑戰性的研究領域。在眾多應用領域，例如戰場監視，動物棲息地監測，環境觀察，家庭健康呵護等，需要對現場進行全方位的監控。但是在很多情況下，這些應用的環境通常都不是非常友好，甚至是惡劣的，因此一般很難通過精確部署的方式在需要監測的區域內布置傳感器節點，并且很難在確定的位置部署傳感器。在這種情況下，一般的解決方法是通過在被監測區域隨機投放大量的傳感器節點，通過冗余覆蓋的方式保證被監控區域的完全覆蓋。然而，大量的傳感器節點可能會由于節點之間的通信干擾而導致節點壽命減少，因此研究如何有效地對無線傳感器網絡的傳感器節點進行調度，節省網絡能耗，延長網絡壽命，已經成為了無線傳感器網絡領域一個重要的研究課題。

在現有的很多研究中，已經出現了將延長網絡使用壽命節省能源的問題轉化為最佳覆蓋問題的技術。最佳覆蓋問題解決技術的出發點在于：鑒于網絡中存在大量冗余的傳感器節點，通過關閉一部分多余的節點，在剩余被激活的節點滿足對監視區域的完全覆蓋的前提下，可以節約能源，延長網絡壽命。最佳覆蓋問題的目標在于找到一個滿足對監控區域完全覆蓋的最少數量的節點子集。這樣，可以在滿足全范圍覆蓋需求的前提下關閉其他的多余的節點，不但可以節省由節點沖突或者鄰近交流而引發的能源消耗，而且由于能夠將部分節點處于休眠狀態，同樣可以節省能耗。

雖然最佳覆蓋問題可以在一定程度上節省網絡的能耗，延長網絡壽命，但是如果能夠在最佳覆蓋問題的解決技術上更進一步，將可以更加有效地延長網絡的壽命。本發明的基本出發點在于：通過對最佳覆蓋問題的解決，找到能夠對監視區域完全覆蓋的最少節點數量的子集；通過不斷解決最佳覆蓋問題，可以找到盡可能多的可以滿足對監視區域完全覆蓋的多個子集；這些子集形成了無線傳感器網絡的多個層次，這些不同的節點層進行輪流的調度，將可以直觀而有效地延長網絡的壽命。因此，本發明解決的問題是無線傳感器網絡的節點分層調度問題。

為了解決無線傳感器網絡的最優分層調度，本發明采用了一種二進制的粒子群算法。二進制粒子群算法屬于計算智能領域的一種具有全局搜索能力的優化算法。雖然粒子群算法由于其概念簡單、流程簡潔而被廣泛應用于多個領域的優化問題中，但是這種優化算法存在一個缺陷就是容易落入具備最優。因此，在本發明中，在采用二進制粒子群算法對無線傳感器網絡的節點進行分層調度優化的時候，將結合問題的特點設計一個基于反轉策略的變異算子，用于增強算法的多樣性，避免算法容易落入局部最優的缺陷。

在本發明中，針對無線傳感器網絡中存在的大量的冗余傳感器節點，循環使用二進制粒子群算法，在每次循環中尋找網絡中的最優傳感器節點子集(滿足對監視區域完全覆蓋的最少數量的傳感器節點子集)。該方法將二進制粒子群算法的粒子編碼為長度等于傳感器節點數量的0/1二進制串，1表示選擇該節點進入子集，0表示不選擇；通過二進制粒子群算法的更新公式和一種反轉策略的變異方法，實現在滿足網絡完全覆蓋前提下的節點子集傳感器數量的最小化。通過不斷調用“最優節點子集傳感器數量最小化的方法”，將網絡中的節點劃分為盡可能多的不相交子集，進而解決了網絡節點分層調度的優化問題。本發明設計的變異操作能夠增強算法多樣性，避免算法容易落入局部最優的缺陷。結合變異操作，本發明使用的二進制粒子群算法能夠高效地對無線傳感器網絡的節點進行最大化的分層優化調度，對延長網絡壽命有重要的作用。

發明內容：

本發明將二進制粒子群算法用于無線傳感器網絡的節點分層調度中，具體的內容步驟介紹如下：

(1)對于給定的網絡Netw，設置其最大層數K＝0，然后檢查網絡中的傳感器節點集S是否能夠對網絡區域100％覆蓋。如果能，則進行以下的步驟；如果不能，則輸出最大可分層數K＝0，終止程序。

(2)使用二進制粒子群算法從網絡Netw的傳感器節點集S中找出一組能夠對網絡區域進行100％覆蓋的最優節點子集S*，具體的流程如下：