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

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

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

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

1 正弦余弦算法

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

假設種群規(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次迭代后所有種群當前最優(yōu)個體在第j維的位置分量，r1、r2、r3和r44個參數中，最關鍵的是參數r1，r1，按公式(2)求得，r2∈[0,2π]、r3∈[0,2]和r4∈[0,1]為3個隨機參數。

(2)

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

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

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

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

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

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

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

2.1 網絡模型

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

2)隨機部署傳感器節(jié)點，假設其在網絡中是隨機均勻部署的，一經部署位置固定。

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

4)假設網絡中的傳感器節(jié)點均能夠與基站通信。

2.2 能量消耗模型

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

(3)

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

ERx(l)=lEelec

(4)

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

EFx(n,l)=nlEDA

(5)

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

2.3 算法模型

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

1)初始種群生成

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

k=round(Nalive·p)

(6)

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

2)目標函數

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

(7)

(8)

3)位置更新

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

3 實驗仿真與分析

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

3.1 仿真參數設置

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

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

②傳感器節(jié)點總數N：200個。

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

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

⑤數據量大小l：4000 bit。

⑥簇頭當選概率p：0.05。

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

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

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

3.2 仿真結果與分析

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

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

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

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

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

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

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

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

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

4 結 論

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