羅劍

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

關(guān)鍵詞：群體智能;遺傳算法;WSNs;能耗優(yōu)化;多目標(biāo)優(yōu)化

中圖分類號：TP393? ? ? ? 文獻(xiàn)標(biāo)識碼：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]都屬于人工智能領(lǐng)域研究的范疇。SI是一類分散自組織系統(tǒng)的集體智能行為的總稱，即基于個體群成員的聚集表現(xiàn)出獨(dú)立的智能，適合求解優(yōu)化問題，有助于實(shí)現(xiàn)多項(xiàng)式時間復(fù)雜度無法解決的NP問題。GA是模擬自然界生物進(jìn)化過程與機(jī)制求解最優(yōu)問題的一類自組織、自適應(yīng)人工智能技術(shù)。通過編碼組成初始群體后，遺傳操作的任務(wù)是按照群體中個體的環(huán)境適應(yīng)度對個體施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks， WSNs），是由隨機(jī)投放在監(jiān)測區(qū)域內(nèi)的大量低成本且擁有傳感、計算、數(shù)據(jù)處理和通信能力的微型傳感器節(jié)點(diǎn)構(gòu)成的多跳自組織網(wǎng)絡(luò)。通過感知、收集和融合環(huán)境范圍中目標(biāo)對象的測量數(shù)據(jù)，將預(yù)處理后的消息發(fā)送回基站（Base Station， BS），擴(kuò)展了人們洞悉和操控外部世界的能力。

許多WSNs應(yīng)用中數(shù)目巨大分布廣泛的傳感器節(jié)點(diǎn)基于電池供電且難于補(bǔ)充能量， 存在嚴(yán)重的能量限制。減少和平衡節(jié)點(diǎn)能耗， 最大化網(wǎng)絡(luò)生存期成為WSNs的首要設(shè)計目標(biāo)。節(jié)點(diǎn)能耗與WSNs網(wǎng)絡(luò)協(xié)議密切相關(guān)，設(shè)計良好的路由算法可以在很大程度上降低和平衡節(jié)點(diǎn)能耗，延長網(wǎng)絡(luò)生存期。利用SI和GA等自然元啟發(fā)智能算法實(shí)現(xiàn)WSNs路由協(xié)議對各類在網(wǎng)傳感節(jié)點(diǎn)數(shù)據(jù)通信和計算處理的綜合協(xié)調(diào)調(diào)度，優(yōu)化網(wǎng)絡(luò)能耗意義重大。

1 5種自然元啟發(fā)算法

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

2 WSNs能耗優(yōu)化關(guān)鍵技術(shù)

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

2.1 建立基于節(jié)點(diǎn)剩余能量指標(biāo)的WSNs數(shù)學(xué)模型和能耗模型

一階無線電模型是WSNs的通用能耗模型，在該模型框架內(nèi)定義了數(shù)據(jù)發(fā)送、接收、融合、計算、感知的能耗公式用來模擬網(wǎng)絡(luò)真實(shí)能耗。將WSNs劃分為節(jié)點(diǎn)初始能量相等的同構(gòu)WSNs和節(jié)點(diǎn)初始能量不同的異構(gòu)WSNs。借助于對節(jié)點(diǎn)剩余能量和分輪次（round）建簇的深入分析，把各種WSNs數(shù)學(xué)模型均映射到多級異構(gòu)模型。WSNs節(jié)點(diǎn)通常情況下隨機(jī)散布在監(jiān)測區(qū)域內(nèi)且靜止不動，節(jié)點(diǎn)位置、節(jié)點(diǎn)度、與其他節(jié)點(diǎn)距離、與基站距離等指標(biāo)隨機(jī)分布。盡管同構(gòu)WSNs節(jié)點(diǎn)的初始能量相等，采用的網(wǎng)絡(luò)協(xié)議也意圖保持每個輪次各個節(jié)點(diǎn)能耗一致，但是因?yàn)樯鲜鲋笜?biāo)的差異，每輪各節(jié)點(diǎn)實(shí)際耗能不可能相同，故同構(gòu)WSNs在本質(zhì)上是異構(gòu)WSNs的特例。在建立網(wǎng)絡(luò)協(xié)議的過程中，只要充分考慮節(jié)點(diǎn)剩余能量，即能將同構(gòu)和異構(gòu)WSNs統(tǒng)一于多級能量異構(gòu)WSNs數(shù)學(xué)模型。

2.2 簇間單跳路由場景的最優(yōu)簇頭數(shù)量

在本場景中成員節(jié)點(diǎn)與所在簇頭、簇頭與基站之間均是直接通信，鏈路跳數(shù)為2，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對固定，如圖1所示。影響簇間單跳路由場景中最優(yōu)簇頭數(shù)量計算公式的因素包括基站相對監(jiān)測區(qū)域的位置、主副簇頭機(jī)制、控制包、自由空間模型和多路徑衰減模型等，綜合運(yùn)用微積分、極坐標(biāo)、概率分布等數(shù)學(xué)工具和概念，可以計算16種因素組合的最優(yōu)簇頭數(shù)量和一個輪次網(wǎng)絡(luò)總能耗的數(shù)學(xué)公式，如表2所示。

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

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

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

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

3 總結(jié)

本文分析了5種自然元啟發(fā)算法的優(yōu)缺點(diǎn)，將其應(yīng)用到WSNs能耗優(yōu)化設(shè)計。利用節(jié)點(diǎn)剩余能量，可以將不同結(jié)構(gòu)的WSNs統(tǒng)一于多級能量異構(gòu)模型，從而計算單跳路由場景的最優(yōu)簇頭數(shù)量和分簇結(jié)果。對于簇間多跳路由場景的分簇和路由，必須綜合選擇Pareto多目標(biāo)適應(yīng)度函數(shù)及其權(quán)重系數(shù)，才能平衡節(jié)點(diǎn)能量消耗，延長網(wǎng)絡(luò)生存期。

參考文獻(xiàn)：

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

[2] 黃少榮.粒子群優(yōu)化算法綜述[J].計算機(jī)工程與設(shè)計，2009，30（8）：1977-1980.

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

[4] 臧睿，李輝輝.基于標(biāo)準(zhǔn)螢火蟲算法的改進(jìn)與仿真應(yīng)用[J].計算機(jī)科學(xué)，2016，43（S2）：113-116，132.

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

【通聯(lián)編輯：代影】