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

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

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

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

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

1 正弦余弦算法

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

1)基站位于網(wǎng)絡(luò)中心，一旦部署不再變動(dòng)，而且假設(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為單位比特?cái)?shù)據(jù)融合消耗的能量。

2.3 算法模型

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

1)初始種群生成

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

k=round(Nalive·p)

(6)

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

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

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

(7)

(8)

3)位置更新

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

3 實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)在Intel core i7 CPU，16 G內(nèi)存，3.6 GHz主頻的計(jì)算機(jī)上，采用MATLAB R2010b對(duì)經(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個(gè)。

③區(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算法中馬爾科夫鏈長(zhǎng)度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)時(shí)的節(jié)點(diǎn)分布圖。從圖中可以看出，運(yùn)行經(jīng)典LEACH-C協(xié)議的網(wǎng)絡(luò)，死亡節(jié)點(diǎn)相對(duì)比較集中，集中在某一側(cè)；而圖4中運(yùn)行改進(jìn)協(xié)議的網(wǎng)絡(luò)中，死亡節(jié)點(diǎn)分布相對(duì)比較均勻。這是由于正弦余弦算法選舉出的簇頭方案在節(jié)約傳感器節(jié)點(diǎn)能耗和均能傳感器節(jié)點(diǎn)間能耗方面更優(yōu)，使得死亡節(jié)點(diǎn)的分布相對(duì)比較均勻。

圖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)對(duì)比圖，可以看出，改進(jìn)后的協(xié)議中第一個(gè)死亡節(jié)點(diǎn)時(shí)間比經(jīng)典的LEACH-C協(xié)議推后了500多輪，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期。另外還可以發(fā)現(xiàn)，改進(jìn)協(xié)議在第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)以后，其他節(jié)點(diǎn)也相繼快速死亡，呈直線下降趨勢(shì)，說(shuō)明節(jié)點(diǎn)間能量的消耗比較均衡。

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

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

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

圖6顯示了運(yùn)行LEACH-C協(xié)議的網(wǎng)絡(luò)出現(xiàn)死亡節(jié)點(diǎn)后，兩種協(xié)議累計(jì)發(fā)送數(shù)據(jù)包的對(duì)比情況。可以看出，改進(jìn)協(xié)議發(fā)送數(shù)據(jù)包的量明顯高于LEACH-C，是因?yàn)長(zhǎng)EACH-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ù)對(duì)比 圖7 兩種協(xié)議各輪累計(jì)消耗能量對(duì)比

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

4 結(jié) 論

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