WSNs 中基于雞群優(yōu)化算法選擇簇頭的簇路由*

張 洋，楊守良

（1.重慶幼兒師范高等?？茖W(xué)校兒童智能科學(xué)與技術(shù)系，重慶 404047；2.重慶文理學(xué)院電子電氣工程學(xué)院，重慶 402160）

0 引言

物聯(lián)網(wǎng)的發(fā)展促進(jìn)了無線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）［1-2］在各領(lǐng)域中的應(yīng)用。WSNs 由微型、低功耗的傳感節(jié)點(diǎn)組成，這些傳感節(jié)點(diǎn)具有數(shù)據(jù)感知、數(shù)據(jù)處理和通信能力。傳感節(jié)點(diǎn)先感知環(huán)境數(shù)據(jù)，再通過多跳通信將數(shù)據(jù)傳輸至基站。

然而，節(jié)點(diǎn)資源受限，包括數(shù)據(jù)處理能力、存儲空間、通信范圍以及能量容量，阻礙了基于WSNs 應(yīng)用的拓展。尤其節(jié)點(diǎn)能量受限，極大地限制了WSNs應(yīng)用。通常，節(jié)點(diǎn)是由電池供電，電池的使用時(shí)間較短，當(dāng)節(jié)點(diǎn)電池耗盡，也不便更換電池。因此，一旦電池耗盡，節(jié)點(diǎn)就相當(dāng)于失效，無法繼續(xù)工作。

感測數(shù)據(jù)、傳輸數(shù)據(jù)等操作均消耗能量，其中傳輸數(shù)據(jù)消耗了節(jié)點(diǎn)的大部分能量。為此，控制節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量，可延緩節(jié)點(diǎn)的能耗速度。而簇技術(shù)是減少節(jié)點(diǎn)傳輸數(shù)據(jù)量的有效手段。

因此，基于簇的WSNs 被廣泛研究。簇技術(shù)就是將網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)劃分多個(gè)群。每個(gè)群稱為一個(gè)簇，每個(gè)簇又產(chǎn)生一個(gè)簇頭。簇頭負(fù)責(zé)收集簇內(nèi)節(jié)點(diǎn)所感測的數(shù)據(jù)，圖1 給出典型的簇結(jié)構(gòu)。

圖1 WSNs 的簇結(jié)構(gòu)

作為簇技術(shù)的代表，低功耗自適應(yīng)簇路由（Low Energy Adaptive Clustering Hierarchy，LEACH）技術(shù)得到廣泛應(yīng)用［3］。LEACH 采用隨機(jī)方式選擇簇頭，這不利于簇頭的均勻分布，使節(jié)點(diǎn)間的能耗不均衡。

簇頭的選擇策略是簇技術(shù)的關(guān)鍵，其也成為簇技術(shù)領(lǐng)域的研究熱點(diǎn)。研究人員試圖利用智能算法提高選擇簇頭的效率，平衡了網(wǎng)絡(luò)能耗。例如，文獻(xiàn)［4］將粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）應(yīng)用于LEACH，通過PSO 策略產(chǎn)生新的簇，進(jìn)而平衡網(wǎng)絡(luò)能耗。類似地，文獻(xiàn)［5］將猴子搜索算法（Monkey Search，MS）應(yīng)用于LEACH，形成LEACHMS 路由。

此外，文獻(xiàn)［6］提出基于蛙跳和螢火蟲算法的簇路由（Shuffled Frog-Leaping and Firefly Algorithm，SFFA）。SFFA 利用節(jié)點(diǎn)到基站的距離、節(jié)點(diǎn)剩余能量以及簇間距離等信息擇優(yōu)選擇簇頭。

雞群優(yōu)化算法（Chicken Swarm Optimization，CSO）也廣泛應(yīng)用于WSNs。例如，文獻(xiàn)［7］利用CSO算法構(gòu)建簇頭與基站間最優(yōu)的數(shù)據(jù)傳輸路徑。文獻(xiàn)［8］也利用CSO 算法解決WSNs 的定位問題。

為此，受上述方案的啟發(fā)，將CSO 算法應(yīng)用于WSNs，并提出基于雞群優(yōu)化算法選擇簇頭的簇路由（Chicken Swarm Optimization-based Cluster Head Selecting Clustering Routing，CSO-CHS）。CSO-CHS 路由通過CSO 算法選擇最優(yōu)的節(jié)點(diǎn)作為簇頭，減少能耗，延長網(wǎng)絡(luò)壽命。仿真結(jié)果表明，提出的CSO-CHS 路由有效地緩解了節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命。

1 系統(tǒng)模型

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

1.2 能量模型

傳輸數(shù)據(jù)消耗了節(jié)點(diǎn)大部分能量。為此，本文只考慮傳輸數(shù)據(jù)和接收數(shù)據(jù)的能耗，引用文獻(xiàn)［9］的能耗模型，如圖2 所示。

圖2 能耗模型

1.3 CSO 算法概述

CSO 算法中存在多個(gè)雞群。每個(gè)雞群中個(gè)體有3 類角色：起支配作用的公雞（稱為群主）、母雞（群成員）和小雞（群成員）。公雞是群的決策者，地位最高，而母雞和小雞屬弱勢群體。母雞跟著公雞覓食，小雞跟著其母親覓食［10］。

CSO 算法是利用雞適度值將雞個(gè)體進(jìn)行等級制度劃分。具有高適度值的雞成為公雞，適度值較低的雞為小雞，其余的為母雞。

在每一輪內(nèi)，雞群個(gè)體角色不變。每次迭代更新一次，即重新計(jì)算各只雞個(gè)體的適度值，進(jìn)而更新雞群個(gè)體角色，圖3 給出CSO 算法的執(zhí)行過程，其中，t 表示迭代次數(shù)、tmax為最大的迭代次數(shù)。

圖3 CSO 算法的執(zhí)行流程

每只雞的位置對應(yīng)優(yōu)化問題的解。而不同角色的雞個(gè)體采用不同的位置更新策略。用矩陣X 表示雞的位置。

2 CSO-CHS 路由

CSO-CHS 路由是從網(wǎng)絡(luò)能耗的角度，選擇簇頭，并結(jié)合CSO 算法產(chǎn)生最優(yōu)的簇頭，平衡網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)壽命。構(gòu)建適度函數(shù)是執(zhí)行CSO 算法的關(guān)鍵。為此，CSO-CHS 路由先依據(jù)網(wǎng)絡(luò)能耗，構(gòu)建適度函數(shù)，再根據(jù)適度函數(shù)，擇優(yōu)選擇雞群中各只雞個(gè)體的角色，進(jìn)而形成最優(yōu)的簇。

2.1 基于能耗感知的目標(biāo)函數(shù)

CSO-CHS 路由旨在通過選擇最優(yōu)的簇頭，最小化傳輸數(shù)據(jù)的能耗，實(shí)現(xiàn)延長網(wǎng)絡(luò)壽命的目的。換而言之，CSO-CHS 路由的目標(biāo)函數(shù)就是最大化網(wǎng)絡(luò)壽命。

引用文獻(xiàn)［12］的定義，將網(wǎng)絡(luò)內(nèi)第1 個(gè)失效節(jié)點(diǎn)出現(xiàn)的時(shí)間作為網(wǎng)絡(luò)壽命，即將網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)最短的網(wǎng)絡(luò)壽命作為整個(gè)網(wǎng)絡(luò)壽命，如式（6）所示：

這兩部分均與簇頭的選擇有關(guān)。依式（7）可知，eCH與所選擇的簇頭直接相關(guān)。不同節(jié)點(diǎn)作為簇頭，簇頭離簇頭距離不同（dtoBS不同）以及DCH值也將不同。此外，由式（8）可知，不同節(jié)點(diǎn)作為簇頭，簇成員離簇頭的距離也發(fā)生變化，則簇成員向簇頭傳輸數(shù)據(jù)所消耗的能量也會發(fā)生變化。

結(jié)合式（9），可計(jì)算在一輪內(nèi)k 個(gè)簇所消耗的總能量Etotal：

式（11）是一個(gè)優(yōu)化方程。因此，利用全局優(yōu)化的雞群算法迭代尋優(yōu)特性，求解最優(yōu)的簇頭［10］。

2.2 基于CSO 算法的簇頭選擇

CSO-CHS 路由旨在延長網(wǎng)絡(luò)壽命，最小化網(wǎng)絡(luò)能耗。用二值變量表述個(gè)體。變量的下標(biāo)表述個(gè)體ID 號；變量的值表述該個(gè)體是否為簇頭，若值為1，表示簇頭。反之，表示簇成員。

為此，先利用sigmoid 函數(shù)將每只雞個(gè)體的值轉(zhuǎn)換為二值變量，其轉(zhuǎn)換過程如式（12）：

1）先初始化矩陣X。矩陣X 內(nèi)元素隨機(jī)賦予0或1 的值；

2）計(jì)算矩陣X 內(nèi)每一行的個(gè)體適度值；

3）依據(jù)適度值，按下降序值對所有個(gè)體進(jìn)行排序；

4）依據(jù)個(gè)體的適度值，將矩陣X 內(nèi)的元素劃分為3 個(gè)群（公雞、母雞和小雞）；

5）再分別依式（3）～式（5）更新公雞、母雞和小雞的位置；

6）利用式（12）將它們的值轉(zhuǎn)化為二值變量。然后，尋找不可用的解。即檢測矩陣X 中第1 行1的個(gè)數(shù)，如果1 的個(gè)數(shù)小于k，則隨機(jī)選擇將零更換成1；

7）再計(jì)算矩陣X 中每一行的適度值，將具有最大適度值記為xbest；

8）重復(fù)步驟2）至步驟7），直到達(dá)到最大的迭代次數(shù)tmax。

圖4 最優(yōu)解xbest示例

2.3 簇形成

一旦選擇了最優(yōu)的簇頭，基站就將這些簇頭信息向網(wǎng)絡(luò)內(nèi)傳輸。收到消息后，節(jié)點(diǎn)就檢測消息內(nèi)是否包含自己的ID 號，如果有，說明自己被選擇為簇頭。成為簇頭后，簇頭就廣播通告消息。

非簇頭節(jié)點(diǎn)可能收到來自多個(gè)簇頭傳輸?shù)南ⅰ榱藴p少非簇節(jié)點(diǎn)的能耗，非簇節(jié)點(diǎn)將第一時(shí)間收到消息的發(fā)送節(jié)點(diǎn)（簇頭）作為自己簇頭。具體而言，非簇頭節(jié)點(diǎn)一旦收到消息ADV_CH，非簇頭節(jié)點(diǎn)就向發(fā)送節(jié)點(diǎn)回復(fù)加入消息JOIN_CH，并不再接收其他簇頭發(fā)送的ADV_CH。

消息JOIN_CH 包含非簇頭節(jié)點(diǎn)的ID 號以及能量信息。一旦收到JOIN_CH 消息，簇頭就從中提取節(jié)點(diǎn)ID 號，并將其作為自己的簇成員。

3 性能分析

3.1 仿真環(huán)境

利用MATLABR2016b 建立仿真平臺。在100 m×100 m 區(qū)域內(nèi)均勻部署100 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的初始能量為0.5 J。具體的仿真參數(shù)如下頁表1 所示。

表1 仿真參數(shù)

此外，選擇SFFA、LEACH-MS、LEACH-PSO 作為參照。原因在于：它們都是采用智能算法選擇簇頭。SFFA 路由采用蛙跳和螢火蟲算法；LEACH-MS路由采用猴子搜索算法；LEACH-PSO 路由采用粒子群優(yōu)化算法。本文提出的CSO-CHS 路由采用雞群優(yōu)化算法產(chǎn)生簇頭，與SFFA、LEACH-MS、LEACH-PSO 存在可比性。

對比分析它們的CSO-CHS 路由性能。選擇3個(gè)場景：1）基站位于區(qū)域中心，網(wǎng)絡(luò)區(qū)域大小為1002m2；2）網(wǎng)絡(luò)區(qū)域大小為1002m2，基站在右上角（Top Right Corner，TRC）、右邊界線中間（Right Boundary in the Middle，RBM）、區(qū)域中心（Regional Center，RC）；3）基站位于區(qū)域中心，網(wǎng)絡(luò)區(qū)域大小為1002m2、1502m2、2002m2。

3.2 場景1

在本次場景下，分析CSO-CHS 路由的網(wǎng)絡(luò)壽命和能耗。圖5 給出SFFA、LEACH-MS、LEACHPSO 和CSO-CHS 路由的網(wǎng)絡(luò)壽命。從圖5 可知，相比于SFFA、LEACH-MS、LEACH-PSO，提出的CSOCHS 路由的網(wǎng)絡(luò)壽命分別提高了約19 豫、77 豫、80 豫。這說明CSO-CHS 路由有效地平衡了網(wǎng)絡(luò)能耗，緩解了節(jié)點(diǎn)的能耗。

圖5 網(wǎng)絡(luò)壽命

圖6 給出了平均每一輪所消耗的能量。從圖6可知，相比于SFFA、LEACH-MS、LEACH-PSO 路由，CSO-CHS 路由有效地控制每一輪所消耗的能量。例如，LEACH-PSO 路由在執(zhí)行到600 輪時(shí)，其能耗就高達(dá)0.474 J，而CSO-CHS 算法即使執(zhí)行到900 輪時(shí)其能耗也低于0.4 J。

圖6 平均每輪所消耗的能量

3.3 場景2

本次實(shí)驗(yàn)分析基站所在位置對網(wǎng)絡(luò)壽命的影響，如圖7 所示。從圖可知，相比SFFA、LEACH-PSO和LEACH-MS，提出的CSO-CHS 路由有效地延緩了第1 個(gè)失效節(jié)點(diǎn)出現(xiàn)的時(shí)間。此外，基站的位置對各算法的網(wǎng)絡(luò)壽命也存在一定的影響。相比于TRC 和RBM，基站位于RC 時(shí)的能耗最低。原因在于：當(dāng)基站在區(qū)域中心，所有簇頭向基站傳輸數(shù)據(jù)的總路徑得到有效控制，這就減少了能耗。

圖7 基站的不同位置對網(wǎng)絡(luò)壽命的影響

3.4 場景3

本次場景分析網(wǎng)絡(luò)尺寸對網(wǎng)絡(luò)壽命的影響，網(wǎng)絡(luò)尺寸分別為1002m2、1502m2、2002m2。

下頁圖8 描繪了各算法在不同網(wǎng)絡(luò)尺寸下的網(wǎng)絡(luò)壽命。從圖8 可知，網(wǎng)絡(luò)尺寸的增加，降低了網(wǎng)絡(luò)壽命。原因在于：網(wǎng)絡(luò)尺寸的增加，擴(kuò)大了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，拉長了節(jié)點(diǎn)間距離，這就使得節(jié)點(diǎn)需要更多能量傳輸數(shù)據(jù)。

圖8 網(wǎng)絡(luò)尺寸對網(wǎng)絡(luò)壽命的影響

4 結(jié)論

簇是緩解WSNs 的網(wǎng)絡(luò)能耗有效技術(shù)。然而，選擇簇頭并構(gòu)建簇是簇技術(shù)的關(guān)鍵。據(jù)此，本文運(yùn)用CSO 算法選擇簇頭。從能量角度構(gòu)建CSO 算法中的目標(biāo)函數(shù)，再利用CSO 求解，選擇最優(yōu)的節(jié)點(diǎn)作為簇頭，進(jìn)而平衡了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)壽命。仿真結(jié)果表明，提出的CSO-CHS 路由緩解了節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命。