郭曉玲，李 玲，鄒 昕，韓宇軒

(河北北方學(xué)院信息科學(xué)與工程學(xué)院，河北 張家口 075000)

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是一種智能式和分布式的網(wǎng)絡(luò)，它通常由大規(guī)模的低成本傳感器節(jié)點(diǎn)通過無線的方式互聯(lián)而成[1]。目前，WSNs已經(jīng)被廣泛應(yīng)用到社會生活的諸多領(lǐng)域，是當(dāng)前備受矚目的熱議話題之一。WSNs通常采用電池供電，能量受限，如果被用于監(jiān)測環(huán)境惡劣的區(qū)域，后期更換維護(hù)電源的難度很大，因此，WSNs的首要任務(wù)就是提高攜帶的初始電源能量的利用率，盡可能延長整個網(wǎng)絡(luò)的生命周期，避免出現(xiàn)監(jiān)測盲區(qū)[2]。

WSNs大部分能量消耗集中在無線通信模塊，設(shè)計WSNs的路由協(xié)議至關(guān)重要。LEACH-C(low energy adaptive clustering hierarchy,LEACH-Centralized)，一種集中式低功耗自適應(yīng)分簇協(xié)議，它在分簇時使用模擬退火算法(simulated annealing，SA)尋找當(dāng)前最優(yōu)的簇頭方案減少每輪的能量消耗[3]。模擬退火算法作為一種隨機(jī)搜索算法，在較多的迭代次數(shù)后才能得到一個當(dāng)前最優(yōu)解，效率比較低。許多學(xué)者嘗試對LEACH-C協(xié)議進(jìn)行改進(jìn)。文獻(xiàn)[4]采用遺傳算法代替模擬退火算法選取簇頭方案，提出了一種染色體的表達(dá)方法，基于能量測度并根據(jù)問題特征確定合適的適應(yīng)度函數(shù)，將提出的2個新的適應(yīng)度函數(shù)應(yīng)用于四種不同類型傳感器網(wǎng)絡(luò)，但是改進(jìn)算法在節(jié)省能量和延長網(wǎng)絡(luò)生命周期方面并不是很明顯。文獻(xiàn)[5]用模擬退火算法收斂后的局部最優(yōu)解代替初始解進(jìn)行后續(xù)的迭代工作，嘗試提高搜索速度，而且在理論上證明了改進(jìn)的可行性，但是算法的缺陷是算法執(zhí)行的效果對初始解的依賴程度很大。在文獻(xiàn)[6]中采用圖像角點(diǎn)檢測算子SUSAN算法代替模擬退火算法選取簇頭方案，同時通過利用最小生成樹原理，將所選出的簇頭節(jié)點(diǎn)生成最小能耗樹，試圖減少網(wǎng)絡(luò)能耗，但是該算法并未考慮簇頭到基站距離的影響。本文采用近幾年剛剛提出的群體尋優(yōu)正弦余弦算法代替經(jīng)典LEACH-C協(xié)議中的模擬退火算法進(jìn)行集簇分層路由，實驗結(jié)果表明，在相同的迭代次數(shù)情況下，用正弦余弦算法改進(jìn)后，能提高監(jiān)測區(qū)域網(wǎng)絡(luò)中電源能量的利用率。

1 正弦余弦算法

正弦余弦算法(since cosine algorithm，SCA)，由S.Mirjalili在2016年提出，顧名思義，該算法利用正弦余弦數(shù)學(xué)函數(shù)來求解問題的最優(yōu)解[7]。SCA不是模擬自然界某些現(xiàn)象而產(chǎn)生的算法，故其不要假設(shè)條件，易于實現(xiàn)。

假設(shè)種群規(guī)模為m，即包含m個個體，每個個體的維度為k，個體i在第j維的空間位置表示為Xij，i∈{1,2,…,m}，j∈{1,2,…,k}， 個體i第t+1次迭代后，在第j維的空間位置按公式(1)計算：

(1)

其中，Xij(t)為個體i在第t次迭代后第j維的位置分量，Xj*(t)為第t次迭代后所有種群當(dāng)前最優(yōu)個體在第j維的位置分量，r1、r2、r3和r44個參數(shù)中，最關(guān)鍵的是參數(shù)r1，r1，按公式(2)求得，r2∈[0,2π]、r3∈[0,2]和r4∈[0,1]為3個隨機(jī)參數(shù)。

(2)

其中，t為當(dāng)前的迭代次數(shù)，T為最大迭代次數(shù)，a一般取2，r1隨著t的增加逐漸遞減，從2遞減到0。

SCA算法中，r2是0到2π之間的1個隨機(jī)數(shù)，所以可知當(dāng)r1>1時，正弦函數(shù)r1sin(r2)值或者余弦函數(shù)r1cos(r2)值才有可能大于1或者小于-1，此時算法可以在大范圍空間內(nèi)進(jìn)行探索，搜索更多的解的可能；當(dāng)r1≤1時，正弦函數(shù)r1sin(r2)值或者余弦函數(shù)r1cos(r2)值必定介于-1到1之間，算法在局部尋找最優(yōu)解[8]，如圖1所示。

圖1 正弦余弦算法下一位置示意

在SCA算法中，在一個迭代周期T里，隨著迭代次數(shù)的增加，正弦函數(shù)r1sin(r2)的值或者余弦函數(shù)r1cos(r2)的值也逐漸遞減，如圖2所示，可以看到正弦或余弦函數(shù)的振幅在逐漸遞減。當(dāng)振幅較大時，算法可以在一個大的空間中進(jìn)行變化，尋找解的可能性；當(dāng)振幅逐漸減小時，算法逐漸收斂，解也逐漸收斂[9]。

圖2 正弦和余弦范圍的遞減模式

2 基于正弦余弦算法的LEACH-C協(xié)議的改進(jìn)

在LEACH-C協(xié)議中，用正弦余弦算法SCA代替原來的模擬退火算法SA選舉當(dāng)前最優(yōu)簇頭方案，盡可能高效利用電源能量并延長網(wǎng)絡(luò)生命周期。

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

1)基站位于網(wǎng)絡(luò)中心，一旦部署不再變動，而且假設(shè)基站的能量不受限[10]。

2)隨機(jī)部署傳感器節(jié)點(diǎn)，假設(shè)其在網(wǎng)絡(luò)中是隨機(jī)均勻部署的，一經(jīng)部署位置固定。

3)假設(shè)傳感器節(jié)點(diǎn)攜帶的原始能量相同，且后期不再補(bǔ)充。

4)假設(shè)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)均能夠與基站通信。

2.2 能量消耗模型

在改進(jìn)協(xié)議中，發(fā)送端消耗的能量如公式(3)：

(3)

接收端消耗的能量如公式(4)：

ERx(l)=lEelec

(4)

簇頭數(shù)據(jù)融合消耗的能量如公式(5)：

EFx(n,l)=nlEDA

(5)

其中，n為簇內(nèi)節(jié)點(diǎn)總數(shù)，l代表簇內(nèi)成員節(jié)點(diǎn)向簇頭傳輸?shù)臄?shù)據(jù)量，EDA=5nJ/bit/signal，EDA為單位比特數(shù)據(jù)融合消耗的能量。

2.3 算法模型

采用集中式分簇路由，由基站進(jìn)行每一輪的簇頭選舉和簇的劃分。其中，簇頭選舉采用正弦余弦算法，使用簇內(nèi)距離作為目標(biāo)函數(shù)，成員節(jié)點(diǎn)選擇距離最近的簇頭成簇，選擇目標(biāo)函數(shù)最小的一個個體作為本輪的最終分簇方案。成員節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)在簇頭節(jié)點(diǎn)進(jìn)行本地融合后，再傳輸?shù)交?，這樣才完成本輪的數(shù)據(jù)傳輸。

1)初始種群生成

在每一輪中，首先基站計算所有傳感器節(jié)點(diǎn)的平均能量，高于平均能量的節(jié)點(diǎn)構(gòu)成這一輪的候選簇頭集合。然后基站從候選簇頭集合中隨機(jī)選取這一輪的k個簇頭組成一個個體，個體的維度等于k，每一個個體就是一種簇頭方案，隨機(jī)選取m次構(gòu)成初始種群[13]。每一輪選擇的簇頭個數(shù)為k，按公式(6)計算：

k=round(Nalive·p)

(6)

網(wǎng)絡(luò)中規(guī)定，如果網(wǎng)絡(luò)中節(jié)點(diǎn)攜帶的原始能量消耗完時，節(jié)點(diǎn)被看作死亡。式(6)中Nalive為目前網(wǎng)絡(luò)中存活的傳感器節(jié)點(diǎn)個數(shù)，p是節(jié)點(diǎn)被選為簇頭的概率，二者相乘按四舍五入取整。

2)目標(biāo)函數(shù)

對于初始種群中的每一種簇頭方案，基站計算普通成員節(jié)點(diǎn)與對應(yīng)簇頭的距離，選擇距離最近的簇頭成簇。從公式(3)可知，能量消耗與距離成指數(shù)關(guān)系，而且基站位于網(wǎng)絡(luò)中心，所以以普通成員節(jié)點(diǎn)與對應(yīng)簇頭之間的簇內(nèi)距離構(gòu)建目標(biāo)函數(shù)，按公式(7)和(8)計算，其中dtoCH代表普通成員節(jié)點(diǎn)與對應(yīng)簇頭節(jié)點(diǎn)之間的簇內(nèi)距離。

(7)

(8)

3)位置更新

選擇目標(biāo)函數(shù)值最小的一種簇頭方案保存下來，根據(jù)公式(1)進(jìn)行群體位置的更新。更新后，對于位置越界的節(jié)點(diǎn)，選擇迭代之前的對應(yīng)最優(yōu)值作為本次的更新值；對于更新后不在候選簇頭集合中的節(jié)點(diǎn)，在候選簇頭集合中選擇距離其最近的一個節(jié)點(diǎn)作為本次的更新值；若更新后因重復(fù)導(dǎo)致簇頭個數(shù)不足k個，則在候選簇頭集合中隨機(jī)選取不重復(fù)的節(jié)點(diǎn)補(bǔ)充到k個。

3 實驗仿真與分析

實驗在Intel core i7 CPU，16 G內(nèi)存，3.6 GHz主頻的計算機(jī)上，采用MATLAB R2010b對經(jīng)典的LEACH-C協(xié)議和改進(jìn)后的協(xié)議進(jìn)行編程仿真。

3.1 仿真參數(shù)設(shè)置

為了便于改進(jìn)協(xié)議和LEACH-C協(xié)議進(jìn)行比較，將仿真參數(shù)設(shè)置如下：

①區(qū)域規(guī)模：200 m*200 m。

②傳感器節(jié)點(diǎn)總數(shù)N：200個。

③區(qū)域節(jié)點(diǎn)攜帶的原始能量：0.5 J。

④基站x=100 m，y=100 m。

⑤數(shù)據(jù)量大小l：4000 bit。

⑥簇頭當(dāng)選概率p：0.05。

⑦SCA算法中，種群m=15，最大迭代次數(shù)T=20。

⑧SA算法中馬爾科夫鏈長度Len=15，初始溫度Temperature=100，溫度每次下降控制Temperature*0.5，退出條件Temperature≤0.0001。

⑨其他常數(shù)：Eelec:50 nJ/bit;∈fs:10 pJ/bit/m2;∈mp:0.0013 pJ/bit/m4。

3.2 仿真結(jié)果與分析

圖3和圖4分別是兩種協(xié)議出現(xiàn)30%死亡節(jié)點(diǎn)時的節(jié)點(diǎn)分布圖。從圖中可以看出，運(yùn)行經(jīng)典LEACH-C協(xié)議的網(wǎng)絡(luò)，死亡節(jié)點(diǎn)相對比較集中，集中在某一側(cè)；而圖4中運(yùn)行改進(jìn)協(xié)議的網(wǎng)絡(luò)中，死亡節(jié)點(diǎn)分布相對比較均勻。這是由于正弦余弦算法選舉出的簇頭方案在節(jié)約傳感器節(jié)點(diǎn)能耗和均能傳感器節(jié)點(diǎn)間能耗方面更優(yōu)，使得死亡節(jié)點(diǎn)的分布相對比較均勻。

圖3 LEACH-C協(xié)議有30%節(jié)點(diǎn)死亡的節(jié)點(diǎn)分布 圖4 改進(jìn)協(xié)議有30%節(jié)點(diǎn)死亡的節(jié)點(diǎn)分布

圖5是運(yùn)行兩種協(xié)議的網(wǎng)絡(luò)各輪生存節(jié)點(diǎn)對比圖，可以看出，改進(jìn)后的協(xié)議中第一個死亡節(jié)點(diǎn)時間比經(jīng)典的LEACH-C協(xié)議推后了500多輪，延長了整個網(wǎng)絡(luò)的生命周期。另外還可以發(fā)現(xiàn)，改進(jìn)協(xié)議在第一個死亡節(jié)點(diǎn)出現(xiàn)以后，其他節(jié)點(diǎn)也相繼快速死亡，呈直線下降趨勢，說明節(jié)點(diǎn)間能量的消耗比較均衡。

圖5 兩種協(xié)議各輪生存節(jié)點(diǎn)對比

從表1可以看出，改進(jìn)協(xié)議中第1個死亡節(jié)點(diǎn)出現(xiàn)的輪數(shù)比LEACH-C協(xié)議推后了542輪，20%死亡節(jié)點(diǎn)、50%死亡節(jié)點(diǎn)、80%的死亡節(jié)點(diǎn)出現(xiàn)的時間比LEACH-C協(xié)議都推后了；而且改進(jìn)協(xié)議的網(wǎng)絡(luò)，從出現(xiàn)第1個死亡節(jié)點(diǎn)，到80%的節(jié)點(diǎn)死亡僅僅用了19輪，說明改進(jìn)協(xié)議比LEACH-C協(xié)議能更均衡和高效地利用網(wǎng)絡(luò)中的電源能量。

表1 兩種協(xié)議出現(xiàn)相同比例死亡節(jié)點(diǎn)時輪數(shù)對照表

圖6顯示了運(yùn)行LEACH-C協(xié)議的網(wǎng)絡(luò)出現(xiàn)死亡節(jié)點(diǎn)后，兩種協(xié)議累計發(fā)送數(shù)據(jù)包的對比情況。可以看出，改進(jìn)協(xié)議發(fā)送數(shù)據(jù)包的量明顯高于LEACH-C，是因為LEACH-C協(xié)議中的死亡節(jié)點(diǎn)出現(xiàn)較早，節(jié)點(diǎn)死亡了便不再發(fā)送數(shù)據(jù)包，而改進(jìn)協(xié)議的死亡節(jié)點(diǎn)出現(xiàn)較晚。出現(xiàn)死亡節(jié)點(diǎn)前，兩種協(xié)議的所有節(jié)點(diǎn)均能發(fā)送數(shù)據(jù)，發(fā)送數(shù)據(jù)包的量相同。由于運(yùn)行兩種協(xié)議的網(wǎng)絡(luò)初始總能量相同，改進(jìn)協(xié)議比LEACH-C協(xié)議發(fā)送的總數(shù)據(jù)包要多，不難得出，改進(jìn)協(xié)議發(fā)送單位數(shù)據(jù)包所消耗的能量要低于LEACH-C協(xié)議。所以，在能量的利用率方面改進(jìn)協(xié)議表現(xiàn)更優(yōu)。

圖6 出現(xiàn)死亡節(jié)點(diǎn)后兩種協(xié)議發(fā)送數(shù)據(jù)對比 圖7 兩種協(xié)議各輪累計消耗能量對比

圖7是運(yùn)行兩種協(xié)議的網(wǎng)絡(luò)各輪累計消耗能量對比圖。圖7中改進(jìn)后的協(xié)議在整個網(wǎng)絡(luò)生命周期內(nèi)，能量消耗均低于LEACH-C，運(yùn)行LEACH-C協(xié)議的網(wǎng)絡(luò)節(jié)點(diǎn)全部死亡時間比改進(jìn)協(xié)議要早。運(yùn)行LEACH-C協(xié)議的網(wǎng)絡(luò)能量消耗殆盡時，改進(jìn)協(xié)議還在繼續(xù)工作。

4 結(jié) 論

在傳感器網(wǎng)絡(luò)中，對網(wǎng)絡(luò)生命周期的影響最重要的2個要素是能量和距離，在改進(jìn)協(xié)議中優(yōu)先考慮高能量節(jié)點(diǎn)構(gòu)建候選簇頭集合，對均衡傳感器節(jié)點(diǎn)間的能量消耗起到了一定的作用；基站部署在網(wǎng)絡(luò)中心，所以采用簇內(nèi)距離構(gòu)建目標(biāo)函數(shù)，也是充分考慮到距離與能量消耗之間成指數(shù)關(guān)系。仿真實驗結(jié)果表明，在相同迭代次數(shù)的情況下，正弦余弦算法比模擬退火算法表現(xiàn)更優(yōu)，更能選舉出合適的簇頭方案，從而有效地均衡節(jié)點(diǎn)間的能量消耗，避免一些節(jié)點(diǎn)過早死亡，很好地延長了整個網(wǎng)絡(luò)的生命周期。下一步工作將研究多跳SCA和鏈?zhǔn)絊CA在更大規(guī)模網(wǎng)絡(luò)分簇路由中的應(yīng)用。