基于群體智能和遺傳算法的WSNs能耗優化關鍵技術研究

羅劍

摘要：節點能耗是決定無線傳感器網絡（WSNs）生存期的重要參數，設計良好的網絡通信協議可以很大程度上減少和平衡能量消耗。網絡協議設計簇頭和簇間路由的計算過程是多項式時間無法解答的NP問題，該文討論了5種自然元啟發算法，既4種群體智能算法和遺傳算法應用于WSNs能耗優化的關鍵技術，給出了不同網絡能量結構模型的簇間單跳和多跳場景的設計建議，旨在為搭建大規模WSNs網絡提供參考和借鑒。

關鍵詞：群體智能;遺傳算法;WSNs;能耗優化;多目標優化

中圖分類號：TP393? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）07-0190-02

Abstract： Node energy consumption is an important parameter to determine the lifetime of wireless sensor networks （WSNs）. A good network communication protocol can greatly reduce and balance energy consumption. The calculation process of cluster head and inter cluster routing in network protocol design is a NP problem that cannot be solved by polynomial time. This paper discusses five kinds of natural element heuristic algorithms， namely four kinds of swarm intelligence algorithm and genetic algorithm， which are the key technologies of energy consumption optimization of WSNs， and gives the design suggestions of single hop and multi hop scenarios between clusters with different network energy structure model. The purpose is to provide reference for building large-scale WSNs network.

Key words： Swarm intelligence; genetic algorithm; WSNs; energy consumption optimization; multi-objective optimization

群體智能 （Swarm Intelligence，SI）和遺傳算法（Genetic Algorithm，GA）[1]都屬于人工智能領域研究的范疇。SI是一類分散自組織系統的集體智能行為的總稱，即基于個體群成員的聚集表現出獨立的智能，適合求解優化問題，有助于實現多項式時間復雜度無法解決的NP問題。GA是模擬自然界生物進化過程與機制求解最優問題的一類自組織、自適應人工智能技術。通過編碼組成初始群體后，遺傳操作的任務是按照群體中個體的環境適應度對個體施加一定的操作，從而實現優勝劣汰的進化過程。

無線傳感器網絡（Wireless Sensor Networks， WSNs），是由隨機投放在監測區域內的大量低成本且擁有傳感、計算、數據處理和通信能力的微型傳感器節點構成的多跳自組織網絡。通過感知、收集和融合環境范圍中目標對象的測量數據，將預處理后的消息發送回基站（Base Station， BS），擴展了人們洞悉和操控外部世界的能力。

許多WSNs應用中數目巨大分布廣泛的傳感器節點基于電池供電且難于補充能量， 存在嚴重的能量限制。減少和平衡節點能耗， 最大化網絡生存期成為WSNs的首要設計目標。節點能耗與WSNs網絡協議密切相關，設計良好的路由算法可以在很大程度上降低和平衡節點能耗，延長網絡生存期。利用SI和GA等自然元啟發智能算法實現WSNs路由協議對各類在網傳感節點數據通信和計算處理的綜合協調調度，優化網絡能耗意義重大。

1 5種自然元啟發算法

PSO算法[2]是由Kennedy和Eberhart在研究鳥類和魚類的群體行為基礎上于1995年提出的一種SI算法，模仿鳥群飛行覓食行為，通過鳥之間的集體協作使群體達到最優。傳統PSO算法具有局部搜索能力較差，搜索精度不高，搜索性能對參數依賴，后期易震蕩等缺點。通過引入慣性權重、調整加速系數、混合拓撲結構、結合GA算子等改進措施，可以增加局部搜索能力，獲得更快的收斂速度和更好的求解精度。ABC算法[3]由土耳其學者Karaboga在2005年提出，基本思想受蜂群通過個體分工和信息交流，相互協作完成采蜜任務的啟發，強調群體之間互相協作。FA算法[4]是2008年由劍橋學者Yang提出，自然界里的螢火蟲總是會向著比較亮的螢火蟲移動，吸引力的大小跟螢火蟲自身亮度成正比關系，與螢火蟲之間的距離成反比關系。該算法易“陷入局部最優”的固有缺陷，通過增加慣性權重、加強個體協作和信息共享、引入混沌策略、步長levy化、融合其他智能算法等方式可以改進收斂速度，避免早熟。GA是由Holland于1969年提出的一類模擬進化算法，強調群體的進化能力。GA具有易于并行、自組織、自適應、搜索過程無連續可導要求等優點，但是在初始解群分布不均勻時易趨于未成熟收斂，陷入局部次優，其原因在于GA中基于適應度的多樣性保持策略沒能保持群體的多樣性。AIA算法[5]將被求解問題視為抗原，抗體對應問題解，從隨機生成的初始抗體出發，采用選擇、克隆超變異、變異等算子進行操作，產生優越于父代的子代?？寺∵x擇算法（Clonal selection principle， CLONALG）是該類算法的典型代表。5種算法的特點如表1所示，分別模擬了生物種群適應自然的不同行為過程，目標在于以最小的計算代價獲取無限地接近全局最優解。因為算法自身的局限性，在有限次迭代的探索中獲取全局最優是一個概率問題，通常得到的是局部次優解。

2 WSNs能耗優化關鍵技術

WSNs分簇協議綜合考慮節點發送、接收數據的固定能耗和跟隨傳輸距離遠近改變的發送端無線功放能耗，將網絡劃分為若干本地簇。每個簇中的簇頭節點消耗額外能量負責接收簇成員數據并發往基站。分簇結構使得網絡整體擴展性良好，相比節點與基站直接通信和節點間最小傳輸能量路由性能更優，已經成為WSNs路由算法的研究重心。分簇協議的兩個核心問題是：①形成簇;②建立簇頭和基站之間的數據多跳轉發路徑。小面積監測環境基站通信范圍覆蓋整個監測區域，簇頭和基站不需要經過中繼節點轉發數據，只需要考慮“形成簇”，隨后簇頭與基站單跳通信;中等面積和大面積監測環境基站通信范圍無法覆蓋整個監測區域，簇頭和基站通過中繼節點轉發數據，需要綜合考慮上述2個問題。

2.1 建立基于節點剩余能量指標的WSNs數學模型和能耗模型

一階無線電模型是WSNs的通用能耗模型，在該模型框架內定義了數據發送、接收、融合、計算、感知的能耗公式用來模擬網絡真實能耗。將WSNs劃分為節點初始能量相等的同構WSNs和節點初始能量不同的異構WSNs。借助于對節點剩余能量和分輪次（round）建簇的深入分析，把各種WSNs數學模型均映射到多級異構模型。WSNs節點通常情況下隨機散布在監測區域內且靜止不動，節點位置、節點度、與其他節點距離、與基站距離等指標隨機分布。盡管同構WSNs節點的初始能量相等，采用的網絡協議也意圖保持每個輪次各個節點能耗一致，但是因為上述指標的差異，每輪各節點實際耗能不可能相同，故同構WSNs在本質上是異構WSNs的特例。在建立網絡協議的過程中，只要充分考慮節點剩余能量，即能將同構和異構WSNs統一于多級能量異構WSNs數學模型。

2.2 簇間單跳路由場景的最優簇頭數量

在本場景中成員節點與所在簇頭、簇頭與基站之間均是直接通信，鏈路跳數為2，網絡拓撲結構相對固定，如圖1所示。影響簇間單跳路由場景中最優簇頭數量計算公式的因素包括基站相對監測區域的位置、主副簇頭機制、控制包、自由空間模型和多路徑衰減模型等，綜合運用微積分、極坐標、概率分布等數學工具和概念，可以計算16種因素組合的最優簇頭數量和一個輪次網絡總能耗的數學公式，如表2所示。

2.3 簇間單跳路由場景中基于自然元啟發的分簇算法

簇間單跳路由場景只需要考慮分簇過程，自然元啟發智能算法搜索空間的一個粒子對應優化問題的一個解，既映射為監測區域內的全體簇頭集合，解的質量由多目標適應度函數評估。PSO、ABC和FA三種SI算法分別將解稱為粒子、螢火蟲和蜜蜂對應的蜜源位置（以下統稱粒子），通過粒子間的互相協作、學習和吸引，尋找更優的解。上述過程必須建立連續量的粒子到離散量的簇頭集合的映射關系，當粒子代表的解的位置在連續空間內移動時，需要按照一定的規則找到對應的離散化的簇頭集合。GA算法的解稱為染色體，通過染色體的選擇、交叉和變異操作不斷進化，從而搜索解空間尋找更優解。CLONALG算法模擬人體免疫機理，引入抗體的選擇、復制、克隆增值超變異、變異等操作保留和搜索優質抗體，快速尋找更優解。在算法實現過程中，如何確定Pareto多目標適應度函數及其權重系數是一個難點，對于算法的性能影響較大，還需要考慮簇頭和基站距離對成簇規模的影響。

2.4 簇間多跳路由場景中基于自然元啟發的分簇和路由算法

簇間多跳路由場景成員節點和簇頭直接通信，簇頭視距離基站遠近選擇0～n個中繼節點轉發數據到基站。在簇建立過程中與簇間單跳路由場景有三點不同的處理策略：①因為簇頭和基站間的跳數無法事先確定，所以不可能形式化地數學推導最優簇頭數量。為了生成動態數量的優選簇頭集合，在染色體或抗體初始化時將全部節點納入簇頭的候選集合進行計算極大地增加了運算負載，并不可取?？梢砸罁欢ǖ倪^濾規則，有條件地確定簇頭候選節點集合，該集合元素數量遠小于全體節點數量。②靠近基站的簇頭相比遠離基站的簇頭更有可能成為中繼節點，因而能量消耗更快，極大地影響網絡生存期，這種現象稱為熱區問題?？梢酝ㄟ^不相等分簇和多跳路由組織網絡，簇范圍隨著節點到基站距離的減小而減小，從而平衡簇頭的簇內和簇間總負載。③隨著監測面積的擴大，增加了簇頭通信范圍無法覆蓋全部非簇頭節點的概率，必須考慮在網節點的連通度指標。簇間路由算法中每個簇頭擁有自己的下跳候選簇頭集合，PSO、ABC和FA算法必須映射連續變化的粒子到離散化的下跳簇頭，GA或CLONALG算法容易建立離散化的染色體或抗體到離散化的下跳簇頭的映射關系。選擇Pareto多目標適應度函數及其權重系數仍然極大地影響算法性能。分簇算法常見參數有：簇內通信距離、簇頭與基站通信距離、節點剩余能量、節點度、簇頭生存期、每輪總能耗、網絡連通度、簇頭占比、簇頭剩余能量標準差等，路由算法常見參數有：下跳節點剩余能量、下跳節點距離、下跳節點與基站距離、沿路徑每跳距離平方和、下跳節點度、最大跳數等。

3 總結

本文分析了5種自然元啟發算法的優缺點，將其應用到WSNs能耗優化設計。利用節點剩余能量，可以將不同結構的WSNs統一于多級能量異構模型，從而計算單跳路由場景的最優簇頭數量和分簇結果。對于簇間多跳路由場景的分簇和路由，必須綜合選擇Pareto多目標適應度函數及其權重系數，才能平衡節點能量消耗，延長網絡生存期。

參考文獻：

[1] 葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計算機應用研究，2008，25（10）：2911-2916.

[2] 黃少榮.粒子群優化算法綜述[J].計算機工程與設計，2009，30（8）：1977-1980.

[3] 秦全德，程適，李麗，等.人工蜂群算法研究綜述[J].智能系統學報，2014，9（2）：127-135.

[4] 臧睿，李輝輝.基于標準螢火蟲算法的改進與仿真應用[J].計算機科學，2016，43（S2）：113-116，132.

[5] 李茂軍，羅安，童調生.人工免疫算法及其應用研究[J].控制理論與應用，2004，21（2）：153-157.

【通聯編輯：代影】