戚 攀，包開(kāi)陽(yáng)，馬皛源

(1.中國(guó)科學(xué)院 上海高等研究院，上海 201210； 2.中國(guó)科學(xué)院大學(xué)，北京 100049)(*通信作者電子郵箱maxy@sari.ac.cn)

0 引言

當(dāng)前，無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network， WSN)在很多領(lǐng)域得到了大量的應(yīng)用，比如環(huán)境監(jiān)控、病患管理、工業(yè)自動(dòng)化[1]。它的主要功能是借助大量部署具有無(wú)線通信能力的傳感器節(jié)點(diǎn)并自組織形成網(wǎng)絡(luò)，最終將傳感器節(jié)點(diǎn)感知到的信息進(jìn)行處理后通過(guò)無(wú)線通信方式發(fā)送至基站，從而使監(jiān)測(cè)者了解監(jiān)測(cè)區(qū)域的信息。然而廉價(jià)微型的傳感器節(jié)點(diǎn)的存儲(chǔ)、計(jì)算能力通常非常有限，特別是由于使用電池供電，節(jié)點(diǎn)自身能量有限，在戰(zhàn)場(chǎng)火場(chǎng)等應(yīng)用環(huán)境下又不可能及時(shí)地更換電池進(jìn)行能量補(bǔ)充[2]，因此，在能量有限的前提下，要有效地延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間就需要一個(gè)能量高效的無(wú)線傳感網(wǎng)路由算法。在已有的眾多能量高效路由算法當(dāng)中，基于分簇的分層路由已經(jīng)被證明是提高網(wǎng)絡(luò)能量利用效率最有效的技術(shù)之一[3]。

現(xiàn)有的分層路由算法大部分都借鑒了低功耗自適應(yīng)分簇(Low Energy Adaptive Cluster Hierarchy， LEACH)路由算法[4]的思想。LEACH的核心思想是將傳感網(wǎng)進(jìn)行分區(qū)，每個(gè)分區(qū)內(nèi)所有傳感器節(jié)點(diǎn)成為一簇，每簇選取一個(gè)節(jié)點(diǎn)作為簇頭。每次收集信息時(shí)先由普通節(jié)點(diǎn)將感知到的信息發(fā)送至所屬分簇的簇頭，簇頭將接收到的數(shù)據(jù)進(jìn)行融合去除冗余后通過(guò)單跳或者多跳的方式發(fā)送至基站。這樣一次完整的數(shù)據(jù)采集過(guò)程稱為一輪，網(wǎng)絡(luò)的生存時(shí)間通過(guò)運(yùn)行輪數(shù)來(lái)計(jì)算，稱為生命周期。

基于分層路由算法的機(jī)制，設(shè)計(jì)一個(gè)能量高效分層路由算法需要解決三個(gè)關(guān)鍵問(wèn)題：1)分簇；2)簇頭選??；3)消息發(fā)送路徑。LEACH算法采用的“簇頭隨機(jī)，就近入簇，單跳至基站”的解決方案。由于簇頭是隨機(jī)選取的，完全沒(méi)有考慮節(jié)點(diǎn)的剩余能量和簇頭的個(gè)數(shù)，LEACH算法有可能選取低能量的節(jié)點(diǎn)作為簇頭，簇頭節(jié)點(diǎn)相對(duì)于普通節(jié)點(diǎn)要消耗更多的能量，這樣就容易導(dǎo)致低能量節(jié)點(diǎn)過(guò)快地死亡，形成“死區(qū)”。LEACH算法在成簇的時(shí)候是通過(guò)普通節(jié)點(diǎn)就近入簇的方式完成的，這樣就容易形成不均勻的“極大、極小簇”，其中的“極大簇”的簇頭節(jié)點(diǎn)負(fù)載過(guò)大，容易死亡。在LEACH算法中簇頭通過(guò)單跳的方式直接與基站通信，在距離較遠(yuǎn)的情況下簇頭的能量消耗會(huì)急劇地增加。此外，LEACH算法每輪都需要重選簇頭，新簇頭被選出來(lái)后都需要進(jìn)行廣播告知新簇頭信息，浪費(fèi)了大量能量。針對(duì)LEACH算法存在的這些問(wèn)題，后續(xù)出現(xiàn)的分層路由算法提出了很多解決方案。改進(jìn)的低功耗自適應(yīng)分簇(Improved Low Energy Adaptive Cluster Hierarchy， I-LEACH)路由算法[5]將檢測(cè)區(qū)域均勻地分為五個(gè)分區(qū)，每個(gè)分區(qū)內(nèi)的所有節(jié)點(diǎn)成為一簇，在一定程度解決了成簇不均勻的問(wèn)題，但分區(qū)方式過(guò)于簡(jiǎn)單，沒(méi)有考慮網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)具體的分布情況和相對(duì)于基站的位置。能量高效的非均勻分簇(Energy-Efficient Uneven Clustering， EEUC)路由算法[6]在選取簇頭時(shí)考慮了節(jié)點(diǎn)相對(duì)于基站的位置，離基站近的節(jié)點(diǎn)有更大概率擔(dān)任簇頭；但是沒(méi)有考慮簇頭相對(duì)于簇內(nèi)普通節(jié)點(diǎn)的位置，沒(méi)有優(yōu)化簇內(nèi)通信的能量消耗。能量負(fù)載均衡的簇頭選取(Leader Election with Load balancing Energy， LELE)路由算法[7]在選取簇頭時(shí)考慮了節(jié)點(diǎn)的剩余能量，剩余能量大的節(jié)點(diǎn)更容易當(dāng)選簇頭?；谧顑?yōu)簇?cái)?shù)和改進(jìn)引力搜索的(Optimal Number of Clusters and Improved Gravitational Search, ONCIGS)路由算法[8]在簇頭與基站的通信過(guò)程中采用簇頭間多跳轉(zhuǎn)發(fā)的方法，避免了簇頭與基站距離過(guò)大時(shí)單跳通信造成的巨大發(fā)射能耗。經(jīng)過(guò)修改的低功耗自適應(yīng)分簇(MODified Low Energy Adaptive Cluster Hierarchy， MODLEACH)路由算法[9]為了避免每輪都需重選簇頭的問(wèn)題，使用了一種使用閾值控制簇頭重選的方法，只有當(dāng)簇頭節(jié)點(diǎn)的剩余能量下降到設(shè)定的閾值以下時(shí)才會(huì)觸發(fā)簇頭重選。

以上的這些研究針對(duì)分簇路由算法的三個(gè)關(guān)鍵問(wèn)題提出了一些非常值得參考的解決方法，但是也還存在一些問(wèn)題。比如LELE算法和EEUC算法的分簇結(jié)果不夠合理，ONGIGS算法對(duì)簇頭選取的考慮還不夠全面。經(jīng)過(guò)分析后，為了盡可能地降低網(wǎng)絡(luò)能耗并延長(zhǎng)其生命周期，本文提出一種基于模糊C-均值(Fuzzy C-Means， FCM)聚類和群體智能算法(人工蜂群(Artificial Bee Colony, ABC)算法、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法)的WSN分層路由算法(WSN hierarchical routing algorithm based on Fuzzy C-Means clustering and Swarm Intelligence， FCM-SI)。在分簇階段，針對(duì)網(wǎng)絡(luò)的實(shí)時(shí)情況動(dòng)態(tài)地確定最優(yōu)分區(qū)數(shù)量，并通過(guò)FCM實(shí)現(xiàn)網(wǎng)絡(luò)動(dòng)態(tài)均衡的分簇；在簇頭選取階段，使用節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到基站的距離、節(jié)點(diǎn)到所在分簇內(nèi)其他節(jié)點(diǎn)的平均距離三個(gè)特征作為參數(shù)構(gòu)造適應(yīng)函數(shù)，采用人工蜂群算法計(jì)算每個(gè)分簇內(nèi)最適合擔(dān)任簇頭的節(jié)點(diǎn)的位置；在簇間路由階段，將最小能量消耗作為目標(biāo)函數(shù)，采用最擅長(zhǎng)執(zhí)行路徑的蟻群優(yōu)化算法搜索最小消耗的簇間多跳數(shù)據(jù)轉(zhuǎn)發(fā)路徑。仿真結(jié)果顯示，F(xiàn)CM-SI可以明顯地降低網(wǎng)絡(luò)能量消耗，延遲第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)的死亡時(shí)間，有效地延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文對(duì)傳感網(wǎng)網(wǎng)絡(luò)作出如下假設(shè)：

1)節(jié)點(diǎn)隨機(jī)分布在監(jiān)測(cè)區(qū)域內(nèi)，所有節(jié)點(diǎn)靜止不動(dòng)，基站位于監(jiān)測(cè)區(qū)域外；

2)節(jié)點(diǎn)數(shù)為N，監(jiān)測(cè)區(qū)域面積為M×M；

3)所有節(jié)點(diǎn)的能量相等并且有限，基站能量無(wú)限；

4)節(jié)點(diǎn)可以感知自身位置，且可以根據(jù)相互間的距離控制發(fā)射功率；

5)所有節(jié)點(diǎn)具有相同屬性和性能，都可以擔(dān)任普通節(jié)點(diǎn)或者簇頭，簇頭節(jié)點(diǎn)會(huì)進(jìn)行數(shù)據(jù)融合去除冗余。

1.2 能量模型

本文使用了和經(jīng)典的LEACH算法相同的一階無(wú)線電模型。設(shè)Eelec為節(jié)點(diǎn)每發(fā)送或接收1比特消息消耗的能量；εfree為節(jié)點(diǎn)放大器在自由空間模型下的傳輸增益，εmulti-path為放大器在多徑衰落模型下的傳輸增益；l為消息長(zhǎng)度,單位為比特；d為消息傳輸距離；dgate為傳輸距離閾值，當(dāng)消息傳輸距離小于dgate時(shí)采用自由空間模型,否則使用多徑衰落模型。一個(gè)節(jié)點(diǎn)經(jīng)過(guò)距離d的發(fā)送l比特?cái)?shù)據(jù)的傳輸功耗為：

(1)

接收l(shuí)比特?cái)?shù)據(jù)功耗為：

Erx(l)=lEelec

(2)

由式(1)可知：

(3)

設(shè)定Eelec=50 nJ/b，εfree=10 pJ/(b·m2)，εmulti-path=0.001 3 pJ/(b·m4)。簇頭進(jìn)行數(shù)據(jù)融合消耗的能量為n·m·EDA。其中n為分區(qū)的節(jié)點(diǎn)數(shù)；m為每個(gè)節(jié)點(diǎn)發(fā)送的消息長(zhǎng)度,單位為比特，EDA=5 nJ/(b·signal)。

2 FCM-SI

2.1 動(dòng)態(tài)分簇

為了降低簇內(nèi)普通節(jié)點(diǎn)與簇頭通信的能耗，本文使用了模糊C均值聚類進(jìn)行分簇，成簇均勻并優(yōu)化了簇內(nèi)節(jié)點(diǎn)與簇頭間的距離。由于網(wǎng)絡(luò)狀態(tài)隨著運(yùn)行不斷變化，存活節(jié)點(diǎn)數(shù)會(huì)逐步減少，導(dǎo)致最佳簇頭數(shù)也是動(dòng)態(tài)變化的。為了取得最佳的網(wǎng)絡(luò)性能，在網(wǎng)絡(luò)運(yùn)行的過(guò)程中根據(jù)網(wǎng)絡(luò)當(dāng)前狀態(tài)動(dòng)態(tài)地控制簇頭數(shù)。

2.1.1 模糊C均值聚類

模糊C均值(FCM)聚類是一種無(wú)監(jiān)督聚類算法，這個(gè)聚類方法由Dunn在1973年首次提出[10]，并在1981年由Bezdek[11]改進(jìn)之后已經(jīng)成為了一種常用的模式識(shí)別方法。FCM的目標(biāo)是使得數(shù)據(jù)點(diǎn)到所屬分類中心的距離的和最小化，利用FCM的這一特性將其應(yīng)用到無(wú)線傳感網(wǎng)的分簇當(dāng)中，就可以將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為幾個(gè)最緊密的簇，優(yōu)化簇內(nèi)節(jié)點(diǎn)到簇頭間的相互距離，有效地降低簇內(nèi)通信消耗的能量。不同于常見(jiàn)的C-均值和K-均值聚類這種非此即彼的硬劃分方法，F(xiàn)CM是一種模糊劃分方法，這使得FCM能處理復(fù)雜的數(shù)據(jù)分布情況[12]。該聚類算法的目標(biāo)函數(shù)為：

(4)

其中：xi為第i個(gè)數(shù)據(jù)點(diǎn)；cj為第j個(gè)聚類中心；uij為數(shù)據(jù)點(diǎn)xi相對(duì)于分類j的歸屬度；m為權(quán)重系數(shù)，一般按照經(jīng)驗(yàn)值取為2；N為數(shù)據(jù)點(diǎn)數(shù)量；C為分類數(shù)量；‖xi-cj‖為數(shù)據(jù)點(diǎn)xi到聚類中心cj的距離，一般采用歐氏距離。聚類的過(guò)程就是通過(guò)迭代使目標(biāo)函數(shù)最小化的過(guò)程。每次迭代，歸屬度矩陣的更新公式為：

(5)

聚類中心坐標(biāo)的更新公式為：

(6)

迭代結(jié)束條件為：

(7)

其中：k為迭代步數(shù)，ε為迭代終止閾值。算法的具體步驟描述如下：

1)輸入數(shù)據(jù)點(diǎn)集合X={x1,x2,…,xi,…,xN}T和分類數(shù)量K,并初始化歸屬度矩陣U(0)。

2)第k次迭代：按式(6)使用歸屬度矩陣計(jì)算聚類中心坐標(biāo)C(k)。

3)按式(5)更新歸屬度矩陣U(k)、U(k+1)。

4)如果滿足式(7)的條件則停止迭代算法完成；否則轉(zhuǎn)到第2)步繼續(xù)迭代。

2.1.2 基于FCM的動(dòng)態(tài)分簇

由于FCM需要先確定分類數(shù)量，應(yīng)用到網(wǎng)絡(luò)分簇就需要在分簇之前根據(jù)網(wǎng)絡(luò)特征確定最合理的簇頭數(shù)量。根據(jù)上面介紹的網(wǎng)絡(luò)模型和能量模型，整個(gè)網(wǎng)絡(luò)運(yùn)行一輪消耗的能量[13]為：

Eone_round≈N(E·l+εfree·l·M2/(2πk))+

(8)

其中k為簇頭數(shù)。對(duì)k求偏導(dǎo)，并令其值為零，可求得使得功耗最低的最優(yōu)簇頭數(shù)為：

(9)

由式(9)可知，最優(yōu)簇頭數(shù)與存活節(jié)點(diǎn)數(shù)的開(kāi)方成正比。在初始節(jié)點(diǎn)數(shù)為100、監(jiān)測(cè)區(qū)域長(zhǎng)寬為100 m的初始條件下可求得最優(yōu)簇頭數(shù)為5。然而隨著網(wǎng)絡(luò)的不斷運(yùn)行，開(kāi)始出現(xiàn)死亡節(jié)點(diǎn)，存活節(jié)點(diǎn)數(shù)開(kāi)始下降，最優(yōu)簇頭數(shù)也對(duì)應(yīng)減少，需要再次分簇；例如當(dāng)存活節(jié)點(diǎn)數(shù)減少到81時(shí)，最優(yōu)簇頭數(shù)變?yōu)?，直到最終整個(gè)網(wǎng)絡(luò)只有一個(gè)簇。

另外，不同于很多分層路由算法每一輪都需要重新分簇，在本文提出的FCM-SI規(guī)定一個(gè)節(jié)點(diǎn)的剩余能量大于最小簇頭能量ECH_min才有可能當(dāng)選為簇頭：

ECH_min=Eone_round+Eselect+Edivide

(10)

其中：Eone_round為簇頭運(yùn)行一輪所需的能量，Eselect為廣播一次重新選擇簇頭的控制包的能量，Edivide為廣播一次重新分簇的控制包的能量。在FCM-SI中，當(dāng)某個(gè)簇頭節(jié)點(diǎn)的能量達(dá)到動(dòng)態(tài)閾值時(shí)，該簇頭(編號(hào)i)會(huì)向其他所有簇頭廣播一個(gè)控制包，通知其他簇頭運(yùn)行三參數(shù)人工蜂群(ABC)算法重新選擇簇頭。Eselect就是廣播這個(gè)控制包需要的能量。在新的簇頭被選取出來(lái)后，如果這些新的簇頭都和原來(lái)的都是同一批就說(shuō)明當(dāng)前網(wǎng)絡(luò)中某個(gè)分簇內(nèi)部已經(jīng)沒(méi)有節(jié)點(diǎn)適合成為簇頭,那么簇頭(編號(hào)i)需要向其他所有節(jié)點(diǎn)廣播一個(gè)控制包，通知所有節(jié)點(diǎn)開(kāi)始重新分區(qū)。Edivide就是廣播這個(gè)控制包需要的能量，所以，只有剩余能量大于最小簇頭能量ECH_min的節(jié)點(diǎn)才能當(dāng)選為簇頭。然而一旦FCM完成一次分簇后，那么直到下一次分簇之前每個(gè)簇包含的節(jié)點(diǎn)都不再變化。這樣就有可能出現(xiàn)某個(gè)簇內(nèi)的所有節(jié)點(diǎn)的剩余能量都不足以擔(dān)任簇頭的情況，這種情況下也需要再次分簇。

所以觸發(fā)網(wǎng)絡(luò)重新分簇的條件是出現(xiàn)以下兩種情況之一：1)存活節(jié)點(diǎn)數(shù)下降到最優(yōu)簇頭數(shù)需要變化時(shí)；2)某個(gè)簇內(nèi)的所有節(jié)點(diǎn)的剩余能量都小于擔(dān)任節(jié)點(diǎn)的最小能量時(shí)。當(dāng)觸發(fā)重新分簇后，再次運(yùn)行FCM生成新的分簇，這樣就完成了整個(gè)網(wǎng)絡(luò)生命周期內(nèi)的動(dòng)態(tài)分簇過(guò)程。

2.2 簇頭選取

在網(wǎng)絡(luò)的初始化階段，最初由基站在每個(gè)分簇內(nèi)隨機(jī)選取一個(gè)候選簇頭。同一分簇內(nèi)的每個(gè)節(jié)點(diǎn)都可以相互感知對(duì)方的位置和能量信息。隨后，由候選簇頭采用ABC算法選取正式的簇頭。候選簇頭完成簇頭選取后要廣播一短信息，將簇頭的坐標(biāo)、簇頭所屬的分簇編號(hào)以及簇頭的ID告知所有節(jié)點(diǎn)。普通節(jié)點(diǎn)收到廣播信息后通過(guò)自身所屬的分簇編號(hào)與簇頭進(jìn)行匹配入簇，簇頭節(jié)點(diǎn)也需要相互存儲(chǔ)其他簇頭節(jié)點(diǎn)的位置和編號(hào)，用于簇頭間消息傳遞路徑的計(jì)算。

2.2.1 人工蜂群算法

人工蜂群(ABC)算法[14]是一種受自然界中蜜蜂采蜜行為啟發(fā)的群體智能算法，蜂群中的蜜蜂分為不同的幾個(gè)工種，每個(gè)工種承擔(dān)不同的工作，在工作的過(guò)程中完成信息的交流和分享，從而在有限的時(shí)間復(fù)雜度內(nèi)大概率找到問(wèn)題的最優(yōu)解。這個(gè)算法在解決全局優(yōu)化問(wèn)題方面展現(xiàn)出了非常強(qiáng)的能力。

ABC算法將人工蜂群中的蜜蜂分為三種：雇傭蜂、跟隨蜂和偵察蜂。雇傭蜂搜索蜜源并與跟隨蜂分享蜜源信息，比如蜜源的花蜜量，蜜量大的蜜源代表具有更大的適應(yīng)值，代表更好的解。完成和所有雇傭蜂的蜜源信息分享后，跟隨蜂會(huì)按照一定概率挑選一個(gè)蜜源并基于這個(gè)蜜源尋找新的蜜源，蜜源的蜜量越大被跟隨蜂選擇的概率也就越大。偵查蜂的作用是隨機(jī)地尋找新的蜜源，一旦偵查蜂和跟隨蜂找到了新的高質(zhì)量蜜源就會(huì)轉(zhuǎn)換成雇傭蜂。

在算法的初始化階段，ABC首先生成包括三種蜜蜂的種群和它們的蜜源位置。雇傭蜂的數(shù)量和跟隨蜂的數(shù)量相同，每個(gè)雇傭蜂對(duì)應(yīng)一個(gè)蜜源。每個(gè)蜜源的位置稱為一個(gè)解，蜜源的蜜量是這個(gè)解的適應(yīng)值。每個(gè)解xi(i=1,2,…,n)是一個(gè)d維的解向量，n是蜜源的數(shù)量。每只雇傭蜂會(huì)記住當(dāng)前對(duì)應(yīng)蜜源的位置并生成一個(gè)新的蜜源，如果新發(fā)現(xiàn)的蜜源的適應(yīng)值要好于舊蜜源，雇傭蜂將會(huì)存儲(chǔ)新蜜源的位置坐標(biāo)并刪除舊蜜源的位置坐標(biāo)；否則繼續(xù)保持舊蜜源的位置坐標(biāo)不變。雇傭蜂尋找新蜜源的公式如下：

xij′=xij+rij(xij-xkj);i≠k,r∈[-1,1],

j∈[1,2,…,d]

(11)

其中rij是一個(gè)隨機(jī)系數(shù)，也就是用另一個(gè)蜜源對(duì)當(dāng)前蜜源的第j維分量作用，從而完成在當(dāng)前蜜源周圍的搜索。當(dāng)所有的雇傭蜂完成一次發(fā)現(xiàn)和位置更新后，就會(huì)與跟隨蜂分享蜜源信息。跟隨蜂得到蜜源信息后會(huì)按照一定概率選擇一個(gè)蜜源，具體的概率計(jì)算公式如下：

(12)

其中fitnessi是解xi的適應(yīng)值，可以看到一個(gè)適應(yīng)值更大的蜜源將會(huì)吸引更多數(shù)量的跟隨蜂。選擇蜜源之后，跟隨蜂同樣要按照式(11)搜索新的蜜源。如果經(jīng)過(guò)多次發(fā)現(xiàn)后，在規(guī)定的有限的步驟內(nèi)某一個(gè)蜜源的適應(yīng)值沒(méi)有改善，那么將丟棄這個(gè)蜜源，蜜源對(duì)應(yīng)的雇傭蜂身份改為偵察蜂。新出現(xiàn)的偵查蜂按照如下公式發(fā)現(xiàn)新的蜜源：

?i∈(1,2,…,n)

(13)

其中：lb,ub分別為解的第j分量的上下界，r是一個(gè)-1到1之間的隨機(jī)數(shù)。如果新產(chǎn)生的解的分量超過(guò)了上下界，那么直接取值為被超過(guò)的界值。

綜上，ABC算法的流程如下：

1)初始化蜜源和雇傭蜂的位置坐標(biāo)xi(i=1,2,…,n)。

2)雇傭蜂根據(jù)式(11)發(fā)現(xiàn)新蜜源，并計(jì)算適應(yīng)值，執(zhí)行貪婪算法更新蜜源位置。

3)跟隨蜂根據(jù)雇傭蜂分享的信息按照一定概率選擇蜜源，并使用雇傭蜂同樣的方式發(fā)現(xiàn)新蜜源。

4)如果某個(gè)解達(dá)到廢棄條件即達(dá)到最大發(fā)現(xiàn)次數(shù)(本文定義為20)后解沒(méi)有改善，則根據(jù)式(13)產(chǎn)生新解。

5)判斷是否達(dá)到終止條件即達(dá)到最大迭代次數(shù)(本文定義為20)，如果達(dá)到輸出最終解；否則返回步驟2)。

使用ABC算法的關(guān)鍵在于適應(yīng)函數(shù)的定義，也就是怎樣去衡量一個(gè)解的優(yōu)劣，將ABC應(yīng)用到簇頭的選取需要結(jié)合無(wú)線傳感網(wǎng)的具體特征去定義適應(yīng)函數(shù)。下面將介紹FCM-SI定義適應(yīng)函數(shù)并完成簇頭選取的過(guò)程。

2.2.2 基于ABC的簇頭選取

FCM-SI在選取簇頭時(shí)主要考慮了節(jié)點(diǎn)的三個(gè)特征：節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到基站的距離、節(jié)點(diǎn)與其所在簇內(nèi)的普通節(jié)點(diǎn)之間的緊密程度。由于簇頭節(jié)點(diǎn)需要擔(dān)任更多的數(shù)據(jù)收發(fā)和融合任務(wù)，相對(duì)普通節(jié)點(diǎn)需要消耗更多的能量，所以一般情況下選擇剩余能量多的節(jié)點(diǎn)作為簇頭能有效地改善網(wǎng)絡(luò)能量均衡性能。另外，簇頭到基站的距離越小，簇頭將數(shù)據(jù)發(fā)送至基站消耗的能量也相應(yīng)越小；簇頭到所在分簇其他節(jié)點(diǎn)的平均距離越小，擔(dān)任簇頭后普通節(jié)點(diǎn)發(fā)送數(shù)據(jù)給它時(shí)消耗的能量就會(huì)越小，所以簇頭的選取問(wèn)題就是一個(gè)通過(guò)改變節(jié)點(diǎn)位置(選取不同的節(jié)點(diǎn))來(lái)改善上述三個(gè)參數(shù)指標(biāo)的多參數(shù)優(yōu)化問(wèn)題，針對(duì)多參數(shù)優(yōu)化求解，ABC算法是一種低復(fù)雜度的高效的求解方法。一個(gè)簇內(nèi)包括的每個(gè)節(jié)點(diǎn)都是一個(gè)可能解，基于上述三個(gè)參數(shù)構(gòu)造一個(gè)適應(yīng)函數(shù)，計(jì)算節(jié)點(diǎn)擔(dān)任簇頭的適應(yīng)值并將每個(gè)節(jié)點(diǎn)都建模為一個(gè)ABC算法中的蜜源模型，就可以采用ABC算法在簇內(nèi)搜索最適合擔(dān)任簇頭的節(jié)點(diǎn)，從而完成簇頭選取。基于以上分析，本文將簇頭選取的適應(yīng)函數(shù)定義如下：

fitness(i)=af1(i)+bf2(i)+cf3(i)

(14)

(15)

(16)

(17)

其中：a,b,c為權(quán)重因子，控制三個(gè)參數(shù)的重要程度；f1是候選節(jié)點(diǎn)的剩余能量與所屬簇內(nèi)所有節(jié)點(diǎn)的平均能量的比值，體現(xiàn)了剩余能量對(duì)簇頭選取的影響；f2為候選節(jié)點(diǎn)到基站的距離與所屬簇內(nèi)所有節(jié)點(diǎn)到基站距離的平均值的比值；f3為候選節(jié)點(diǎn)到所屬簇內(nèi)其他節(jié)點(diǎn)距離的平均值與其他節(jié)點(diǎn)擔(dān)任候選節(jié)點(diǎn)到其他節(jié)點(diǎn)距離平均值的比值，體現(xiàn)了簇頭節(jié)點(diǎn)在區(qū)間內(nèi)與普通節(jié)點(diǎn)的緊密程度。f2、f3體現(xiàn)了節(jié)點(diǎn)位置對(duì)簇頭選取的影響。其他參數(shù)中：n為節(jié)點(diǎn)i所在分簇的節(jié)點(diǎn)總數(shù)，Eres(i)為節(jié)點(diǎn)i的剩余能量，dtoBS(i)為節(jié)點(diǎn)i到基站的距離，d(j,k)為節(jié)點(diǎn)j到節(jié)點(diǎn)k的距離。在網(wǎng)絡(luò)的初始化階段定義a=b=c=1/3，也就是三個(gè)參數(shù)的重要程度相同。然后隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)能量不斷地降低，成為更加重要的瓶頸參數(shù)，所以隨著網(wǎng)絡(luò)的運(yùn)行將f1的權(quán)重動(dòng)態(tài)增大。本文將a、b、c定義為：

(18)

b=c=(1-a)/2

(19)

可以看到，經(jīng)過(guò)以上的定義之后，隨著網(wǎng)絡(luò)的運(yùn)行f1的權(quán)重從1/3動(dòng)態(tài)增加到2/3,剩余能量大的節(jié)點(diǎn)有更大概率成為簇頭，有利于優(yōu)化整個(gè)網(wǎng)絡(luò)的能量負(fù)載均衡。

2.3 簇間多跳路徑搜索

為了降低簇頭能耗并均衡簇間負(fù)載，采用改進(jìn)的蟻群優(yōu)化算法搜索簇頭至基站的最優(yōu)路徑，簇頭與基站通信時(shí)，會(huì)沿著搜索到的最優(yōu)路徑簇間多跳將數(shù)據(jù)轉(zhuǎn)發(fā)至基站。

2.3.1 蟻群優(yōu)化算法

和人工蜂群算法相同，蟻群優(yōu)化(ACO)算法[15]也是一種啟發(fā)式群體智能算法，該算法主要是受到螞蟻種群的覓食行為的啟發(fā)。自然界中的螞蟻在自身沒(méi)有視覺(jué)也沒(méi)有其他外界信息的情況下可以通過(guò)個(gè)體間釋放信息素進(jìn)行消息傳遞，協(xié)作搜索蟻巢到食物源之間的最短路徑，構(gòu)成了一種典型的集體尋優(yōu)行為。該算法尤其擅長(zhǎng)解決路徑搜索類問(wèn)題，已經(jīng)被成功地應(yīng)用于求解旅行商問(wèn)題這類NP(Non-deterministic Polynomial)問(wèn)題，取得了非常好的實(shí)驗(yàn)效果。經(jīng)過(guò)研究發(fā)現(xiàn)，螞蟻在搜尋食物源時(shí)，會(huì)在經(jīng)過(guò)的路徑上釋放信息素，沒(méi)有視覺(jué)能力的螞蟻通過(guò)感知周圍的信息素決定行動(dòng)的方向，并有更大概率向信息素濃度高的方向移動(dòng)。信息素會(huì)隨著時(shí)間逐步揮發(fā)，一般情況下，在單位時(shí)間內(nèi)越短的路徑經(jīng)過(guò)的螞蟻越多，該路徑上的信息素濃度也越大，吸引更多的螞蟻。由于這種正反饋機(jī)制，經(jīng)過(guò)一段時(shí)間后所有的螞蟻都將選擇這條最短的路徑[16]。

初始化時(shí)，所有路徑的信息素濃度初始化為τ0，螞蟻種群數(shù)量為m。螞蟻被隨機(jī)地投放在某個(gè)起點(diǎn)位置，然后開(kāi)始逐個(gè)遍歷位置點(diǎn)，直到將所有位置點(diǎn)遍歷完畢。位于位置點(diǎn)i的螞蟻下一步向位置點(diǎn)j移動(dòng)的概率為：

(20)

其中：τij(t)表示i、j之間路徑的信息素濃度，等于i、j之間的距離的倒數(shù)；α表示信息素的相對(duì)重要程度；β表示啟發(fā)式因子的相對(duì)重要程度；Jk為下一步可以選擇的目的地合集，起到禁忌表的作用。所有的m只螞蟻都完成一次遍歷后，找出其中最短的路徑，按照路徑長(zhǎng)度更新信息素，信息素更新公式為：

τij(t+1)=(1-ρ)·τij(t)+Δτij

(21)

(22)

(23)

其中：Q為正常數(shù)，Lk表示本次遍歷到的最短路徑的長(zhǎng)度，ρ為揮發(fā)因子。也就是只有屬于最短路徑的邊上的信息素會(huì)得到加強(qiáng)，正是這個(gè)正反饋機(jī)制使得ACO有著比模擬退火和遺傳算法更快的收斂速度。

2.3.2 基于ACO的多跳路徑搜索

在無(wú)線傳感網(wǎng)中節(jié)點(diǎn)的發(fā)射功率與發(fā)射距離成正相關(guān)關(guān)系，簇頭間多跳轉(zhuǎn)發(fā)路徑長(zhǎng)度越短，一般情況下消耗的能量也越小，所以ACO非常適合用于搜索最小能耗簇間轉(zhuǎn)發(fā)路徑，降低網(wǎng)絡(luò)能耗。此外，為了使得網(wǎng)絡(luò)的能量負(fù)載更加均衡，同時(shí)將簇頭節(jié)點(diǎn)的剩余能量也考慮到路徑搜索的過(guò)程中，使得搜索到的路徑有更大概率經(jīng)過(guò)剩余能量高的簇頭節(jié)點(diǎn)，避免低能量簇頭承擔(dān)過(guò)多轉(zhuǎn)發(fā)任務(wù)過(guò)快死亡。將簇頭節(jié)點(diǎn)的剩余能量考慮進(jìn)ACO的信息素項(xiàng)中后，信息素項(xiàng)的形式為：

(24)

其中Eres(j)為簇頭j的剩余能量，那么ACO融合剩余能量參數(shù)后的轉(zhuǎn)移概率計(jì)算公式為：

(25)

螞蟻通過(guò)改進(jìn)后的轉(zhuǎn)移概率公式搜索簇間多跳路徑，簇間通信通過(guò)搜索到的路徑進(jìn)行，在減少能耗的同時(shí)也兼顧了能量負(fù)載均衡。

3 實(shí)驗(yàn)仿真與結(jié)果分析

為了驗(yàn)證FCM-SI對(duì)網(wǎng)絡(luò)性能的改善，本文采用了Windows平臺(tái)下的Matlab 2012a版本對(duì)FCM-SI、基于蟻群優(yōu)化的LEACH(LEACH based on ANT， ANT-LEACH)算法、基于人工蜂群優(yōu)化的LEACH(LEACH based on ABC， ABC-LEACH)算法和I-LEACH算法進(jìn)行仿真分析。仿真網(wǎng)絡(luò)環(huán)境設(shè)定如下：網(wǎng)絡(luò)覆蓋面積為100 m×100 m，節(jié)點(diǎn)數(shù)為100，基站位置位于(50,175)。網(wǎng)絡(luò)環(huán)境參數(shù)如表1，其他算法參數(shù)如表2。

表1 網(wǎng)絡(luò)環(huán)境參數(shù)

3.1 成簇結(jié)果

FCM-SI與其他三個(gè)算法的成簇結(jié)果對(duì)比如圖1所示?？梢钥吹?，ABC-LEACH算法使用了ABC算法選擇簇頭，使得簇頭的位置比較合理；但是，由于ANT-LEACH是通過(guò)先隨機(jī)產(chǎn)生簇頭，普通節(jié)點(diǎn)再入簇的方法成簇，簇的數(shù)量和大小都不確定，不均勻的分簇容易導(dǎo)致網(wǎng)絡(luò)的負(fù)載不均衡。I-LEACH算法使用了均勻分區(qū)的方法進(jìn)行分簇，使得簇的大小比較均勻，數(shù)量也更加合理；但是，由于該算法在選擇簇頭時(shí)只考慮了節(jié)點(diǎn)的剩余能量，導(dǎo)致選出的簇頭的位置不夠合理。ABC-LEACH對(duì)LEACH算法的主要改進(jìn)是在簇間路由階段使用ACO搜索多跳路徑，在成簇階段的表現(xiàn)則沒(méi)有進(jìn)行優(yōu)化，成簇的均勻性和簇頭的位置都不夠合理。本文提出的FCM-SI使用了FCM聚類算進(jìn)行分簇和三參數(shù)的ABC算法選取簇頭，成簇的均勻性和簇頭的位置比起三個(gè)比較算法都更加合理。

表2 算法參數(shù)

圖1 成簇結(jié)果對(duì)比

3.2 動(dòng)態(tài)分簇

網(wǎng)絡(luò)的動(dòng)態(tài)分簇過(guò)程如圖2所示。很多算法通過(guò)計(jì)算的最優(yōu)簇頭數(shù)在初始化確定簇的數(shù)量并在后面的運(yùn)行過(guò)程中一直沿用不再改變；但是隨著網(wǎng)絡(luò)的運(yùn)行，開(kāi)始出現(xiàn)死亡節(jié)點(diǎn)，存活的節(jié)點(diǎn)數(shù)也就是網(wǎng)絡(luò)規(guī)模是不斷變化的，與網(wǎng)絡(luò)規(guī)模直接相關(guān)的最優(yōu)簇頭數(shù)也應(yīng)該是動(dòng)態(tài)變化的，所以，F(xiàn)CM-SI采取了動(dòng)態(tài)分簇的策略，根據(jù)網(wǎng)絡(luò)的實(shí)時(shí)情況，動(dòng)態(tài)地調(diào)整最優(yōu)的簇頭數(shù)量。圖2顯示了隨著網(wǎng)絡(luò)運(yùn)行，存活節(jié)點(diǎn)數(shù)開(kāi)始減少，簇頭的數(shù)量從最初的5個(gè)動(dòng)態(tài)地調(diào)整為1個(gè)的過(guò)程。

3.3 網(wǎng)絡(luò)生命周期

一般將從網(wǎng)絡(luò)開(kāi)始運(yùn)行到最后一個(gè)節(jié)點(diǎn)死亡(Last Node Dies， LND)期間的運(yùn)行輪數(shù)稱為網(wǎng)絡(luò)的生命周期，此定義下的FCM-SI與另外三個(gè)算法的生命周期對(duì)比結(jié)果如圖3所示。由圖3可知，ABC-LEACH、ANT-LEACH、I-LEACH、FCM-SI的生命周期分別為624輪、689輪、799輪、1 031輪。相比三個(gè)比較算法，F(xiàn)CM-SI分別延長(zhǎng)了65.2%、49.6%和29.0%的生命周期。

圖2 動(dòng)態(tài)分簇過(guò)程

除了將網(wǎng)絡(luò)生命周期定義為L(zhǎng)ND之外，根據(jù)網(wǎng)絡(luò)的具體應(yīng)用要求，也有研究將網(wǎng)絡(luò)運(yùn)行截止到出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)(First Node Dies， FND)的運(yùn)行輪數(shù)或者網(wǎng)絡(luò)運(yùn)行截止到一半節(jié)點(diǎn)死亡(Half Node Dies， HND)的運(yùn)行輪數(shù)定義為網(wǎng)絡(luò)生命周期。FCM-SI與三個(gè)對(duì)比算法在FND、HND和LND三種定義下的生命周期表現(xiàn)如圖4所示?？梢钥吹?，在三種生命周期定義下，F(xiàn)CM-SI都大幅度地延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖3 生命周期對(duì)比

上面的數(shù)據(jù)表明，相比其他三個(gè)算法，F(xiàn)CM-SI可以有效地延長(zhǎng)網(wǎng)絡(luò)的生命周期。這是因?yàn)镕CM-SI基于最優(yōu)簇頭數(shù)和FCM聚類算法實(shí)現(xiàn)了比較均勻的分簇，使得簇頭的負(fù)載比較均衡。而且由于簇頭與基站之間的通信是通過(guò)蟻群優(yōu)化算法搜索到的最優(yōu)路徑多跳完成的，進(jìn)一步節(jié)省了簇頭節(jié)點(diǎn)的能量，在搜索路徑時(shí)還考慮了簇頭間的負(fù)載均衡，避免了某個(gè)簇頭承擔(dān)過(guò)多轉(zhuǎn)發(fā)任務(wù)能量下降過(guò)快，這些能量均衡方法在很大程度上延遲了第一個(gè)節(jié)點(diǎn)的死亡時(shí)間。在選擇簇頭時(shí)考慮了簇頭節(jié)點(diǎn)到普通節(jié)點(diǎn)的距離，減少了普通節(jié)點(diǎn)發(fā)送數(shù)據(jù)到簇頭消耗的能量，從而在整體上減少了網(wǎng)絡(luò)的能耗，使得FCM-SI在FND、HND和LND三種生命周期定義下的表現(xiàn)都是最優(yōu)的，這說(shuō)明FCM-SI相比三種對(duì)比算法具有更好的通用性。

圖4 三種生命周期對(duì)比

3.4 網(wǎng)絡(luò)能量消耗

FCM-SI與另外三個(gè)算法的網(wǎng)絡(luò)能量消耗情況對(duì)比結(jié)果如圖5所示。從圖5可以看出，在網(wǎng)絡(luò)的整個(gè)運(yùn)行過(guò)程中，F(xiàn)CM-SI的網(wǎng)絡(luò)能量下降都是最慢的。這就說(shuō)明，相對(duì)于其他三個(gè)算法，F(xiàn)CM-SI能明顯地降低網(wǎng)絡(luò)的能量消耗。這得益于在分簇階段由FCM算法形成的分簇中節(jié)點(diǎn)到簇中心的距離是最小的，在選取簇頭的時(shí)候又考慮了簇頭到簇中心的距離，使得普通節(jié)點(diǎn)與簇頭間簇內(nèi)通信的能量消耗有效地降低。而簇間通信的最優(yōu)路徑搜索又進(jìn)一步降低了網(wǎng)絡(luò)的能量消耗。

3.5 網(wǎng)絡(luò)數(shù)據(jù)量

無(wú)線傳感網(wǎng)的主要功能就是感知并發(fā)送環(huán)境數(shù)據(jù)，網(wǎng)絡(luò)的數(shù)據(jù)量是衡量網(wǎng)絡(luò)性能的一個(gè)重要指標(biāo)。FCM-SI與其他三個(gè)算法的數(shù)據(jù)發(fā)送總量比較結(jié)果如圖6所示?？梢钥吹剑呵捌谝?yàn)榇婊罟?jié)點(diǎn)數(shù)都相同，四個(gè)算法的數(shù)據(jù)發(fā)送量曲線重合；后期得益于存活節(jié)點(diǎn)數(shù)比較多的優(yōu)勢(shì)，F(xiàn)CM-SI的信息發(fā)送總量明顯多于其他三個(gè)算法?；窘邮諗?shù)據(jù)總量比較結(jié)果如圖7所示?；咀罱K接收到的數(shù)據(jù)量直接影響網(wǎng)絡(luò)對(duì)其監(jiān)測(cè)區(qū)域的感知的有效程度。可以看到，從網(wǎng)絡(luò)開(kāi)始運(yùn)行到最后一個(gè)節(jié)點(diǎn)死亡，F(xiàn)CM-SI的基站接收數(shù)據(jù)總量也始終多于其他三個(gè)算法。

圖5 網(wǎng)絡(luò)能量消耗對(duì)比

圖7 基站接收數(shù)據(jù)總量對(duì)比

4 結(jié)語(yǔ)

針對(duì)已有的一些WSN分層路由算法在分簇、簇頭選取和簇間路由搜索等方面的不完善導(dǎo)致網(wǎng)絡(luò)生命周期受限、網(wǎng)絡(luò)能量高效性不夠的問(wèn)題，本文提出了一種基于模糊C均值聚類和群體智能的分層路由算法(FCM-SI)。首先根據(jù)實(shí)時(shí)的網(wǎng)絡(luò)環(huán)境計(jì)算最優(yōu)簇頭并利用FCM聚類算法實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)的分簇；然后，采用三參數(shù)的ABC算法選取合理的簇頭；最后，在簇間路由階段采用綜合考慮能量高效和能量均衡的ACO算法搜索最優(yōu)簇間多跳路徑。仿真結(jié)果表明，F(xiàn)CM-SI能有效地降低網(wǎng)絡(luò)能耗，并改善網(wǎng)絡(luò)能量負(fù)載均衡，明顯地延長(zhǎng)網(wǎng)絡(luò)生命周期。雖然本文在簇頭選取和簇間路徑搜索的過(guò)程中都考慮到了節(jié)點(diǎn)的能量負(fù)載均衡，但是通過(guò)動(dòng)態(tài)分簇過(guò)程還是可以看到靠近基站的節(jié)點(diǎn)因?yàn)槌袚?dān)了比較多的轉(zhuǎn)發(fā)任務(wù)，能量下降速度明顯比其他區(qū)域的節(jié)點(diǎn)要快；另外本研究是在固定規(guī)模固定節(jié)點(diǎn)的條件下進(jìn)行，還沒(méi)有考慮到網(wǎng)絡(luò)規(guī)模和移動(dòng)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)性能的影響；所以，下一步的工作將集中于進(jìn)一步改善網(wǎng)絡(luò)能量負(fù)載均衡和優(yōu)化算法在多種網(wǎng)絡(luò)規(guī)模下的表現(xiàn)，并參考無(wú)線通信移動(dòng)平臺(tái)[17-18]的相關(guān)技術(shù)使算法適用于存在移動(dòng)節(jié)點(diǎn)的無(wú)線傳感網(wǎng)。