李洋偉 譚敏生 屈國普 謝騰飛

1南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖南 421001 2南華大學(xué)核科學(xué)技術(shù)學(xué)院 湖南 421001 3中核272鈾業(yè)有限責(zé)任公司 湖南 421001

0 引言

無線傳感器網(wǎng)絡(luò)(WSN)是由大量廉價(jià)，低能耗的微型傳感器節(jié)點(diǎn)部署在監(jiān)測區(qū)域內(nèi)，通過無線通信所形成一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。其目的是協(xié)作地感知、采集和處理監(jiān)測區(qū)域內(nèi)感知對(duì)象的信息，并發(fā)送給觀察者。基于WSN的核輻射監(jiān)測系統(tǒng)將核輻射探測器裝置與傳感器節(jié)點(diǎn)作為一個(gè)監(jiān)測設(shè)備，探測器裝置負(fù)責(zé)采集數(shù)據(jù)信息，傳感器節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的無線收發(fā)。該系統(tǒng)存在大范圍、多點(diǎn)位和實(shí)時(shí)監(jiān)測等特點(diǎn)，但是網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)節(jié)點(diǎn)不能因能量耗盡而更換電池。因此，如何選取合適的路由路徑，降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存周期，成為近年來的研究熱點(diǎn)之一。

1 相關(guān)工作

LEACH協(xié)議是一種低功耗、自組織的自適應(yīng)分簇路由協(xié)議。每一個(gè)簇由一個(gè)簇頭節(jié)點(diǎn)和若干個(gè)簇內(nèi)成員節(jié)點(diǎn)組成。簇內(nèi)成員節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的采集并發(fā)送給本簇的簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)接收簇內(nèi)成員節(jié)點(diǎn)的信息，進(jìn)行數(shù)據(jù)融合，減少數(shù)據(jù)通信量，最后以單跳方式發(fā)送給匯聚節(jié)點(diǎn)。其特點(diǎn)是簇頭節(jié)點(diǎn)以等概率的形式隨機(jī)選擇簇頭，每個(gè)節(jié)點(diǎn)都有一次成為簇頭的機(jī)會(huì)，均衡了網(wǎng)絡(luò)整體能耗，節(jié)約能量，避免節(jié)點(diǎn)能耗過高而死亡，延長了節(jié)點(diǎn)的生存時(shí)間。

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是一種新型的群智能優(yōu)化算法，通過隨機(jī)初始化一群粒子，然后粒子利用自身的經(jīng)驗(yàn)積累和社會(huì)協(xié)作，在搜索空間中搜索全局最優(yōu)解，具有簡單、有效、收斂速度快的特性。

2 基于粒子群路由算法的改進(jìn)

2.1 模型描述

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

為簡化問題模型，為此，本文對(duì)所研究的無線傳感器網(wǎng)絡(luò)做出以下假設(shè)：

(1) 網(wǎng)絡(luò)中所有節(jié)點(diǎn)隨機(jī)部署在監(jiān)測區(qū)域，節(jié)點(diǎn)和基站的位置固定，基站距離傳感器節(jié)點(diǎn)較遠(yuǎn)。

(2) 除基站外，所有傳感器節(jié)點(diǎn)具有相等的初始能量值、信息處理能力，數(shù)據(jù)融合能力。

(3) 所有節(jié)點(diǎn)都知道自己的位置信息，并且可以感知剩余能量。

(4) 所有節(jié)點(diǎn)的發(fā)射功率調(diào)節(jié)可以根據(jù)通信距離的遠(yuǎn)近進(jìn)行調(diào)節(jié)。

(5) 除基站外，所有節(jié)點(diǎn)的通信范圍相同，節(jié)點(diǎn)間的數(shù)據(jù)通信是雙向的。

2.1.2 能量模型

本文采用一介無線通信模型。當(dāng)節(jié)點(diǎn)傳輸 k bit 的數(shù)據(jù)信息時(shí)，傳感器節(jié)點(diǎn)間的能耗可表示為：

其中， ETx(k,d)表示發(fā)送 k bit數(shù)據(jù)時(shí)所消耗的能量，ERx(k)接收 k bit數(shù)據(jù)時(shí)所消耗的能量， Eelec表示發(fā)送 1bit數(shù)據(jù)所消耗的能量，εfs和εmp分別為自由空間模型和多路徑衰減模型的功率放大電路能耗系數(shù)，d為數(shù)據(jù)發(fā)送距離，d0為距離設(shè)定門限：

2.2 算法描述

2.2.1 適應(yīng)值函數(shù)的改進(jìn)

適應(yīng)值函數(shù)是評(píng)價(jià)最優(yōu)解的關(guān)鍵因子，本文用適應(yīng)值函數(shù)來評(píng)價(jià)所選簇頭的質(zhì)量(能量和位置因素)，主要考慮以下三個(gè)方面：一是簇頭能量評(píng)價(jià)因子f1，取簇頭節(jié)點(diǎn)能量占簇內(nèi)節(jié)點(diǎn)總能量的比例的倒數(shù)，簇頭節(jié)點(diǎn)剩余能量越大越好。二是簇內(nèi)距離評(píng)價(jià)因子f2，表示簇內(nèi)成員節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的平均距離，平均距離越小，節(jié)點(diǎn)間數(shù)據(jù)傳輸能量消耗越小。三是簇頭節(jié)點(diǎn)到基站距離評(píng)價(jià)因子f3。簇頭節(jié)點(diǎn)到基站的最佳路徑越小，簇頭節(jié)點(diǎn)消耗能量越小。假設(shè)，有網(wǎng)絡(luò)包含M個(gè)節(jié)點(diǎn)，采用LEACH協(xié)議分為k個(gè)簇，其改進(jìn)的適應(yīng)值函數(shù)f如下：

其中，E(CHi)表示第i個(gè)簇的簇頭節(jié)點(diǎn) C Hi的剩余能量，E(nj)表示第i個(gè)簇的成員節(jié)點(diǎn)j的能量，d(nj, C Hi) 表示第i個(gè)簇內(nèi)節(jié)點(diǎn)j到簇頭節(jié)點(diǎn) C Hi的距離，|Ci|表示第i個(gè)簇的成員節(jié)點(diǎn)數(shù)量。d(C Hi,B S)表示第 i個(gè)簇的簇頭節(jié)點(diǎn) C Hi到基站(BS)的距離。α，β，γ為個(gè)評(píng)價(jià)因子在公式(3)所占的比重，即權(quán)重系數(shù)， α +β+γ=1。

根據(jù)式公式(3)計(jì)算粒子的適應(yīng)值函數(shù)值越小，說明簇頭節(jié)點(diǎn)的剩余能量越大，或者簇內(nèi)成員節(jié)點(diǎn)與簇頭節(jié)點(diǎn)的距離越小，或者簇頭節(jié)點(diǎn)距離基站的距離越近。

2.2.2 算法步驟

本文算法的執(zhí)行過程是周期的，每個(gè)周期分為簇的建立和穩(wěn)定數(shù)據(jù)傳輸階段，其中數(shù)據(jù)傳輸階段包括簇內(nèi)路由和簇間路由數(shù)據(jù)傳輸。具體步驟如下：

(1) 利用 LEACH算法對(duì)網(wǎng)絡(luò)進(jìn)行初始分簇。設(shè)定能量閾值 ET，節(jié)點(diǎn)的剩余能量大于 ET時(shí)被選為候選簇頭，只有候選簇頭才有機(jī)會(huì)成為本輪的簇頭。設(shè) C Hcandidate表示候選簇頭集合，則 C Hcandidate= ｛ni| Ei > ET｝，其中：

Ei表示節(jié)點(diǎn)i的當(dāng)前剩余能量，M表示網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)量。該階段只考慮了節(jié)點(diǎn)的剩余能量，忽略了節(jié)點(diǎn)間的距離和數(shù)據(jù)傳輸能耗等因素，導(dǎo)致整個(gè)網(wǎng)絡(luò)的能耗不均衡，因此需要通過改進(jìn)適應(yīng)值函數(shù)，從候選簇頭集合中選取最優(yōu)的簇頭。

(2) 根據(jù)改進(jìn)的適應(yīng)值函數(shù)，利用粒子群優(yōu)化算法選取最優(yōu)的簇頭。對(duì)候選簇頭粒子群進(jìn)行初始化，計(jì)算各個(gè)粒子的適應(yīng)值函數(shù)值，通過迭代的方法不斷更新粒子的速度和位置，持續(xù)搜索網(wǎng)絡(luò)空間區(qū)域，直到達(dá)到最大的迭代次數(shù)時(shí)算法終止，將全局最優(yōu)解作為本輪的簇頭節(jié)點(diǎn)。

基本步驟如下：

Step1：初始化粒子群。初始化候選簇頭集合中的粒子的速度和位置。根據(jù)公式(3)計(jì)算每個(gè)粒子的適應(yīng)值，將粒子的初始位置作為每個(gè)粒子的個(gè)體最優(yōu)解Pid，選擇其中適應(yīng)值最小的粒子作為整個(gè)粒子群的全局最優(yōu)解Pgd。

Step2：更新粒子的位置和速度。并計(jì)算出新的適應(yīng)值函數(shù)值fi。

Step3：個(gè)體最優(yōu)解的更新。將第i個(gè)粒子的當(dāng)前適應(yīng)值fi與該粒子的個(gè)體最優(yōu)解Pid作比較，若fi< Pid,則更新Pid，否則，保持Pid不變。

Step4：全局最優(yōu)解的更新。將當(dāng)前粒子群中所有粒子的最小個(gè)體最優(yōu)解與整個(gè)粒子群的初始全局最優(yōu)解Pgd作比較，若小于Pgd，則將粒子的個(gè)體最優(yōu)解作為整個(gè)粒子群的全局最優(yōu)解Pgd，否則，保持Pgd不變。

Step5：重復(fù)步驟Step2，Step3和Step4，直到達(dá)到最大迭代次數(shù)，結(jié)束循環(huán)。選取最優(yōu)解作為簇頭節(jié)點(diǎn)。

其算法流程圖如圖1。

圖1 改進(jìn)算法選取簇頭流程圖

(3) 最優(yōu)簇的形成。選取最優(yōu)簇頭節(jié)點(diǎn)后，候選簇頭將簇頭節(jié)點(diǎn)的消息發(fā)送給簇內(nèi)成員節(jié)點(diǎn)，每個(gè)成員節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度選擇自己所屬的簇，并將自身的剩余能量和位置信息發(fā)送給本簇的簇頭節(jié)點(diǎn)，然后簇頭節(jié)點(diǎn)給簇內(nèi)成員節(jié)點(diǎn)分配TDMA時(shí)隙。

(4) 穩(wěn)定數(shù)據(jù)傳輸階段。

① 簇內(nèi)數(shù)據(jù)傳輸階段。該階段主要是在最優(yōu)簇結(jié)構(gòu)形成后，網(wǎng)絡(luò)處于穩(wěn)定的數(shù)據(jù)傳輸，簇內(nèi)成員節(jié)點(diǎn)在相應(yīng)的時(shí)槽內(nèi)將采集的數(shù)據(jù)傳輸給本輪簇的簇頭節(jié)點(diǎn)，其余時(shí)間簇內(nèi)成員節(jié)點(diǎn)處于睡眠狀態(tài)，以節(jié)約能量。

② 簇間數(shù)據(jù)傳輸階段。假設(shè)限定距離值 d0，一般取各個(gè)簇頭節(jié)點(diǎn)到基站的平均距離。若簇頭節(jié)點(diǎn)到基站的距離d >d0，簇頭節(jié)點(diǎn)則以多跳方式將融合后的數(shù)據(jù)傳送給基站。若簇頭節(jié)點(diǎn)到基站的距離d < d0，簇頭節(jié)點(diǎn)則直接以單跳的方式將融合后的數(shù)據(jù)傳輸給基站。

當(dāng)簇頭節(jié)點(diǎn)能量低于設(shè)定的限定能量閾值TE時(shí)，則進(jìn)行簇頭的重新選擇。這樣選取剩余能量高的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，延長了數(shù)據(jù)穩(wěn)定傳輸階段，均衡了網(wǎng)絡(luò)的能耗，從而有效地延長了網(wǎng)絡(luò)生存周期。

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

本文主要從網(wǎng)絡(luò)節(jié)點(diǎn)存活數(shù)和網(wǎng)絡(luò)節(jié)點(diǎn)剩余總能量兩方面與LEACH協(xié)議作比較。將100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在100 x100的正方形區(qū)域內(nèi)，基站位于(X=50，Y=150)。假設(shè)節(jié)點(diǎn)間不出現(xiàn)數(shù)據(jù)傳輸?shù)腻e(cuò)誤和重發(fā)等現(xiàn)象，簇內(nèi)成員節(jié)點(diǎn)在不傳輸數(shù)據(jù)時(shí)處于睡眠狀態(tài)。粒子群優(yōu)化算法的各參數(shù)為：α=0.35，β=0.35，γ=0.3，ω=0.9，學(xué)習(xí)因子 c1=2，c2=2。仿真能耗各參數(shù)為：節(jié)點(diǎn)總能量elecE 為50nJ/bit，單個(gè)節(jié)點(diǎn)初始能量0E為0.5J，數(shù)據(jù)融合能耗DAE 為5nJ/bit/singal，功率放大器能耗fsε為10pJ/bit/m2，信號(hào)放大器倍數(shù)mpε為0.0013pJ/bit/m4，數(shù)據(jù)包長度為4000bits。

網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)與仿真輪數(shù)的關(guān)系如圖 2所示。與LEACH算法相比較，隨著輪數(shù)的進(jìn)行，改進(jìn)算法的中第一個(gè)節(jié)點(diǎn)出現(xiàn)死亡的時(shí)間比較晚，并且當(dāng)20%的節(jié)點(diǎn)數(shù)目出現(xiàn)死亡時(shí)，節(jié)點(diǎn)經(jīng)歷的輪數(shù)比LEACH算法中節(jié)點(diǎn)經(jīng)歷的輪數(shù)多了25%左右，也就是說當(dāng)經(jīng)歷相同輪數(shù)時(shí)，節(jié)點(diǎn)的生存周期相對(duì)延長了 25%左右。由此可知，本文改進(jìn)算法相比LEACH算法，節(jié)省了節(jié)點(diǎn)的能量，顯著地延長了網(wǎng)絡(luò)的生存周期。

圖2 存活節(jié)點(diǎn)數(shù)與仿真輪數(shù)的關(guān)系圖

網(wǎng)絡(luò)節(jié)點(diǎn)剩余總能量與仿真輪數(shù)的關(guān)系如圖3所示。仿真結(jié)果表明，當(dāng)經(jīng)過相同的輪數(shù)時(shí)，改進(jìn)算法中節(jié)點(diǎn)的能耗相比LEACH算法中節(jié)點(diǎn)的能耗相對(duì)要小，即網(wǎng)絡(luò)節(jié)點(diǎn)的剩余總能量相對(duì)較高，明顯的延長了網(wǎng)絡(luò)的生存周期，并且改進(jìn)算法中節(jié)點(diǎn)剩余總能量的曲線相比之下較為平緩。

圖3 網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量與仿真輪數(shù)關(guān)系圖

4 結(jié)束語

本文根據(jù)核輻射環(huán)境的特殊性及無線傳感器網(wǎng)絡(luò)傳感器節(jié)點(diǎn)能量的有限性，在LEACH協(xié)議的基礎(chǔ)上提出一種路由改進(jìn)算法。仿真結(jié)果表明，與LEACH算法相比較，改進(jìn)路由算法明顯的減少了網(wǎng)絡(luò)能耗，有效地延長了網(wǎng)絡(luò)的生命周期。使得基于無線傳感器網(wǎng)絡(luò)的核輻射監(jiān)測系統(tǒng)能夠高效、穩(wěn)定地實(shí)時(shí)監(jiān)測環(huán)境。

[1]孫利民,李建中,陳渝等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社.2005.

[2]Tubaishat M,Madria S.Sensor Networks：an Overview[J].IEEE Potenial.2003.

[3]W.Heinzelman,A.Chandrakasan,H. BalakrishLnan. Energyefficient communication Protocol for wireless microsensor networks. Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui:IEEE Computer Society.2000.

[4]J.Kennedy, R.C. Eberhart. Particle swarm optimization. IEEE International Conference on Neural Networks.1995.

[5]Russell Eberhart, James Kennedy. A new Optimizer Using Particle Swarm Theory. Sixth International Symposium on Micro Machine and Human Science.1995.