基于粒子群算法的WSN非均勻分簇路由協(xié)議

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是傳感器節(jié)點自治組成的網(wǎng)絡(luò)。WSN分簇路由協(xié)議包含簇的形成及簇首選擇，其關(guān)鍵問題在網(wǎng)絡(luò)運行節(jié)點能量消耗的過程中如何選擇簇首使整個網(wǎng)絡(luò)簇內(nèi)能耗均衡。這是一個NP難問題?；谌后w智能算法，能夠避免陷入局部最優(yōu)解，找到全局最優(yōu)解，適合于解決這個NP難問題。目前許多研究者采用粒子群算法解決WSN優(yōu)化分簇問題，文獻(xiàn)主要是在LEACH算法的基礎(chǔ)上采用PSO算法優(yōu)化選擇簇首，簇頭需要完成收集數(shù)據(jù)和傳遞數(shù)據(jù)的功能，很容易消耗能量導(dǎo)致節(jié)點死亡。文獻(xiàn)主要采用PSO算法分簇，使用最小距離法，但采用單跳路由，容易導(dǎo)致距離基站較遠(yuǎn)的簇頭死亡。

本文針對文獻(xiàn)分簇策略中存在的問題，提出采用粒子群算法的非均勻分簇雙層路由協(xié)議。該協(xié)議先用LEACH算法進(jìn)行非均勻以及次簇頭的選擇，然后采用粒子群算法進(jìn)行主簇頭的選擇，主要收集普通節(jié)點數(shù)據(jù)并進(jìn)行融合，然后將融合的數(shù)據(jù)傳給次簇頭，接著次簇頭傳給匯聚節(jié)點，以平衡簇內(nèi)的能耗。

系統(tǒng)模型

網(wǎng)絡(luò)模型及假定

本文是假設(shè)N個傳感器節(jié)點隨機(jī)分布在一個M*M的正方形區(qū)域內(nèi)，假設(shè)該無線傳感器網(wǎng)絡(luò)具有以下性質(zhì)：（1）每個節(jié)點具有唯一ID，節(jié)點和匯聚節(jié)點的位置都固定不動；（2）每個節(jié)點的初始能量都相同；（3）每個節(jié)點的都具有相似的能力，并且地位相等，都有機(jī)會成為簇頭；（4）每個節(jié)點都可以根據(jù)節(jié)點間的距離來調(diào)整其發(fā)射功率的大小；（5）節(jié)點具有位置感知能力。

無線通信能耗模型

本文采用通用的無線通信模型，如下圖1所示。在該無線通信模型中，發(fā)送數(shù)據(jù)的能耗主要在發(fā)送電路和功率放大電路上，接受數(shù)據(jù)的能耗則在接收電路上。

在保證合理信噪比的條件下，傳感器節(jié)點每發(fā)送數(shù)據(jù)時所消耗的能量為：

傳感器節(jié)點接收數(shù)據(jù)時消耗的能量為：

圖1　無線通信能耗模型

圖2　PSO-CP算法原理

基于粒子群算法的非均勻分簇路由協(xié)議（PSOCP）

PSO-CP協(xié)議采用雙簇頭方式，可以避免由于簇內(nèi)簇頭能耗消耗過大而快速消亡，影響網(wǎng)絡(luò)生命周期。這種多層次的數(shù)據(jù)傳輸方式以及結(jié)合蝙蝠算法對主簇頭的選取都有助于節(jié)點間能耗的平衡。原理如圖2所示。

非均勻分簇的建立及次簇頭的產(chǎn)生

在每“輪”中，通過LEACH算法產(chǎn)生次簇頭，并且網(wǎng)絡(luò)中的其余節(jié)點根據(jù)與選擇出來的次簇頭進(jìn)行距離的比較。節(jié)點根據(jù)與所有次簇頭中距離最近的選擇加入該簇。這樣就形成了非均勻分簇路由協(xié)議。

在每“輪”中，都有一個閾值，每個節(jié)點生成一個隨機(jī)數(shù)，如果該節(jié)點的隨機(jī)數(shù)小于這“輪”的閾值那么這個節(jié)點就被選擇為次簇頭。閾值的計算公式如下：

當(dāng)次簇頭選出來后，然后網(wǎng)絡(luò)中剩余的每個節(jié)點都與剛剛生成的次簇頭進(jìn)行距離比較。當(dāng)節(jié)點的距離離該次簇頭的距離最小時，則該節(jié)點就加入這個簇。也就是非均勻分簇就形成了。

主簇頭的產(chǎn)生

成非均勻分簇后，在每一個簇內(nèi)進(jìn)行蝙蝠優(yōu)化算法選舉最優(yōu)的節(jié)點作為主簇頭。為了使之前介紹的PSO算法更好的應(yīng)用到這里，我們需要對原來的簇進(jìn)行改進(jìn)。

假設(shè)n 個節(jié)點分布在平面內(nèi)，則粒子i 的位置xid（t ）由x分量和y 分量決定，如下所示：

同時，粒子i 的速度vid（t ）也應(yīng)該由x 分量和y分量決定，即：

由于網(wǎng)絡(luò)中傳感器節(jié)點的位置并不一定會和隨機(jī)生成的粒子一一對應(yīng)，所以粒子的位置位置需要調(diào)整，使得其中Pxi和Pyi為簇內(nèi)節(jié)點位置的x 和y 分量。設(shè)Dpxi為xidx（t ）與i 節(jié)點x 分量差的絕對值，設(shè)Dpyi為xidy（t ）與i 節(jié)點y 分量差的絕對值，即：

則可知k 節(jié)點位置和粒子xid（t ）最接近，把粒子的位置用相應(yīng)節(jié)點的位置替代，即：

然后將粒子群算法引入進(jìn)來選取主簇頭，由于適應(yīng)度函數(shù)的設(shè)定直接影響到選取出來的簇頭是否最優(yōu)。在本論文中，我們將節(jié)點剩余能量情況和節(jié)點距離其它節(jié)點遠(yuǎn)近情況最為適應(yīng)度函數(shù)。構(gòu)造適應(yīng)度函數(shù)如下所示：

其中，f1為該簇內(nèi)節(jié)點與簇內(nèi)其余節(jié)點距離平均值的最小值。這樣是為了減少數(shù)據(jù)在傳輸中能量的消耗。f2為計算該該簇內(nèi)總能量與該節(jié)點能量的比值。a ，b為［0，1］的數(shù)，并且a+b=1，在仿真中，就是找到使該適應(yīng)度函數(shù)最小的值所對應(yīng)的那個粒子，并找出在網(wǎng)絡(luò)中離該粒子最近的節(jié)點，把該節(jié)點選擇為主簇頭。具體步驟如下：

第一步：初始化粒子，隨機(jī)初始化粒子的速度和位置；

第二步：根據(jù)適應(yīng)度函數(shù)，計算每個粒子的適應(yīng)度函數(shù)值；

第三步：更新粒子的個體極值；即將第i個粒子的當(dāng)前適應(yīng)值與該粒子的個體極值進(jìn)行比較，如果大于個體極值，則將其替換，否則不變。

第四步：更新種群的全局極值；對每個粒子，將其適應(yīng)值與全局極值進(jìn)行比較，如果大于全局極值，則將其替換，否則不變。

第五步：根據(jù)公式更新速度和位置；

第六步：檢查是否到了迭代條件，如果到了，則退出，沒到，返回第二步，直到達(dá)到最大循環(huán)代數(shù)。

圖3為主簇頭選取的流程圖。

仿真及結(jié)果分析

在100個傳感器節(jié)點隨機(jī)分布在100m*100m的范圍內(nèi)，匯聚節(jié)點坐標(biāo)（50，50），位于網(wǎng)絡(luò)內(nèi)部。數(shù)據(jù)包長度為所有節(jié)點的初始能量都為0.1J。對本文提出的PSO-CP路由協(xié)議，在Core i5和2G內(nèi)存計算機(jī)上，采用MATLAB2012B軟件平臺進(jìn)行仿真訓(xùn)練，并把它同LEACH和DEEC路由協(xié)議進(jìn)行性能比較。

由圖4可知，同一種顏色代表一個簇，每種簇中有兩個簇頭，一個是主簇頭，一個是次簇頭。帶有十字星的為簇內(nèi)的主簇頭，空圓點的是次簇頭。上圖中，每個簇內(nèi)都有主次簇頭，其他為普通節(jié)點。中間為匯聚節(jié)點。

圖3　主簇頭選取的流程

網(wǎng)絡(luò)性能評價指標(biāo)：

（1） 網(wǎng)絡(luò)生命周期：指網(wǎng)絡(luò)能更維持多久的時間，持續(xù)的時間越長，則網(wǎng)絡(luò)生命周期越長。通過節(jié)點存活的輪數(shù)來評價網(wǎng)絡(luò)生命周期。

（2） 平均剩余能量消耗：指網(wǎng)絡(luò)中某一輪所有節(jié)點的平均剩余能量情況。

在仿真中，運行250輪。仿真結(jié)果如圖5所示。

由圖5可以清晰的知道， LEACH算法在150輪附近時開始出現(xiàn)了節(jié)點死亡的情況，DEEC算法在165輪附近時開始出現(xiàn)了節(jié)點死亡的情況，PSO-CP算法在185輪附近時開始出現(xiàn)了節(jié)點死亡的情況。在250輪數(shù)中，LEACH算法節(jié)點死亡接近90個，DEEC算法節(jié)點死亡20個，PSO-CP算法節(jié)點死亡8個。通過比較可知，本文算法在節(jié)約節(jié)點能量方面有一定的優(yōu)勢。

圖6為三種算法節(jié)點剩余平均能量的對比，由圖可知，相比于LEACH算法、DEEC算法，PSO-CP算法代表的線條幾乎總是在它們兩個之上。也即是說，在同一輪中，PSO-CP算法的能量剩余總比其他兩種算法要多。在250輪附近，LEACH算法的剩余能量幾乎為0，DEEC算法的剩余能量也接近0.01，而在PSO-CP算法中，節(jié)點剩余的平均能量為0.03。這就說明，PSO-CP協(xié)議能更好的均衡網(wǎng)絡(luò)中節(jié)點能量消耗，避免個別節(jié)點因過度消耗能量而死亡，有效的延長了網(wǎng)絡(luò)的生存周期。

圖4　PSO-CP路由協(xié)議非均勻分簇

圖5　三種算法死亡節(jié)點數(shù)

圖6　三種算法節(jié)點剩余平均能量

結(jié)語

有效解決簇頭選舉不合理、節(jié)點能量消耗不均衡，本文提出了基于粒子群算法的非均勻分簇路由協(xié)議。在構(gòu)造非均勻分簇模型時，根據(jù)LEACH算法來進(jìn)行分簇，選取出次簇頭，然后引入粒子群算法，選取出主簇頭。仿真結(jié)果表明，雙簇頭的方式有利于節(jié)點間能量的均衡，有效的延長了網(wǎng)絡(luò)生存期。

10.3969/j.issn.1001- 8972.2016.15.028