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

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

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

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

系統(tǒng)模型

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

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

無線通信能耗模型

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

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

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

圖1　無線通信能耗模型

圖2　PSO-CP算法原理

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

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

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

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

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

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

主簇頭的產(chǎn)生

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

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

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

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

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

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

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

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

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

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

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

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

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

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

仿真及結(jié)果分析

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

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

圖3　主簇頭選取的流程

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

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

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

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

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

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

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

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

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

結(jié)語

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

10.3969/j.issn.1001- 8972.2016.15.028