基于均勻分區(qū)的無線傳感器網(wǎng)絡(luò)路由算法

劉玉紅，陳滿銀，李翠然

(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070)

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)由數(shù)百甚至數(shù)千個傳感器節(jié)點組成，收集監(jiān)測數(shù)據(jù)供終端用戶分析，被廣泛應(yīng)用于醫(yī)療保健、智能家居、農(nóng)業(yè)工程和目標(biāo)跟蹤等各個領(lǐng)域[1-4].WSN有很多優(yōu)勢，包括自配置、組網(wǎng)靈活、經(jīng)濟有效、體積小等，而由于傳感器節(jié)點的能量由電池供應(yīng)，電池的能量是有限的，并且傳感器網(wǎng)絡(luò)經(jīng)常部署在條件惡劣和無人堅守的環(huán)境，如救災(zāi)行動、礦產(chǎn)開采[5-6]，存在節(jié)點能量一旦耗盡便很難及時補充或更換的問題；因此延長網(wǎng)絡(luò)壽命，提高能量利用率，實現(xiàn)高效能網(wǎng)絡(luò)是WSN研究的主要目標(biāo)之一.分層路由算法是解決這一問題的重要方法，它在網(wǎng)絡(luò)中首先選舉出若干個簇頭，傳感器節(jié)點根據(jù)簇頭選擇加入簇，然后將收集到的數(shù)據(jù)發(fā)送到簇頭節(jié)點，簇頭再將數(shù)據(jù)進(jìn)行融合后轉(zhuǎn)發(fā)到基站(base station,BS)，通過優(yōu)化網(wǎng)絡(luò)通信量達(dá)到節(jié)省網(wǎng)絡(luò)能耗的目的[7].由于分層路由算法的實際應(yīng)用效果優(yōu)于平面路由算法，所以分層路由算法已經(jīng)成為WSN節(jié)能路由算法研究的熱點之一[8].

文獻(xiàn)[9]提出了最具經(jīng)典意義的LEACH算法，該算法提出了“輪循環(huán)”的思想，每輪根據(jù)閾值和賦給各節(jié)點的隨機值來確定簇頭，將網(wǎng)絡(luò)能耗分?jǐn)偟礁鱾€節(jié)點上，但因為在選擇簇頭時，沒有考慮簇頭的剩余能量和位置，導(dǎo)致能量較低的節(jié)點擔(dān)任簇頭而過早死亡以及分簇不均帶來的簇頭負(fù)載不均衡等問題.文獻(xiàn)[10]在K-means算法的基礎(chǔ)上，提出了EECPK-means算法，根據(jù)與基站之間的距離確定初始簇頭，迭代計算得到最終簇頭，在一定程度上使簇頭的分布更加均勻；但存在節(jié)點連續(xù)多次充當(dāng)簇頭而過早死亡的問題.文獻(xiàn)[11]提出了一種基于能量質(zhì)心的路由算法，在選舉簇頭時，根據(jù)節(jié)點的剩余能量與位置信息計算出能量質(zhì)心，將距離能量質(zhì)心最近的節(jié)點作為簇頭，減小網(wǎng)絡(luò)的能量消耗；但存在簇頭負(fù)載不平衡而影響網(wǎng)絡(luò)壽命的問題.

本文在對上述文獻(xiàn)進(jìn)行分析研究后，提出一種基于均勻分區(qū)的無線傳感器網(wǎng)絡(luò)節(jié)能路由算法，首先通過改進(jìn)的多叉樹遍歷算法選擇隨機且分布均勻的初始簇頭，避免出現(xiàn)節(jié)點連續(xù)多次被選為簇頭的問題；其次，節(jié)點根據(jù)自身與初始簇頭之間的距離以及成員節(jié)點的數(shù)量來加入分區(qū)，均衡各分區(qū)內(nèi)節(jié)點的個數(shù)，進(jìn)而均衡各簇頭的負(fù)載；接下來，再在各分區(qū)內(nèi)優(yōu)先選擇剩余能量較多以及與其他節(jié)點之間的距離和最小的節(jié)點擔(dān)任簇頭，有效地減小網(wǎng)絡(luò)能耗；最后進(jìn)行數(shù)據(jù)收集和上傳，其中，距離BS較遠(yuǎn)的簇頭采用多跳通信的方式將數(shù)據(jù)轉(zhuǎn)發(fā)到BS.

1 WSN能耗模型及參數(shù)設(shè)置

1.1 無線通信能耗模型

因為節(jié)點的能量消耗主要集中在數(shù)據(jù)的接收和發(fā)送上[12]，所以本文對節(jié)點的能耗分析主要考慮節(jié)點的無線通信能耗.節(jié)點發(fā)送l/bit數(shù)據(jù)到與其距離為d/m的節(jié)點，其消耗的能量ETX(l,d)為：

(1)

其中：Eelec是發(fā)送和接收數(shù)據(jù)時電路消耗的能量;εfs與εmp分別表示自由空間和多徑衰落模型下的放大器系數(shù);距離閾值[13]Dthreshold為

(2)

節(jié)點接收l/bit數(shù)據(jù)所消耗的能量ERX(l)為

ERX(l)=lEelec.

(3)

節(jié)點對m個數(shù)據(jù)包進(jìn)行數(shù)據(jù)融合所消耗的能量Efuse為

Efuse(m)=m×lEDA,

(4)

其中，EDA是融合單位比特數(shù)據(jù)所消耗的能量.

1.2 仿真場景參數(shù)設(shè)置

本文在進(jìn)行能耗分析和仿真實驗過程中，仿真場景參數(shù)設(shè)置見表1.

表1 仿真場景參數(shù)設(shè)置

2 WSN能耗分析

2.1 簇頭節(jié)點能耗分析

在無線傳感器網(wǎng)絡(luò)分層路由算法中，簇頭節(jié)點主要負(fù)責(zé)接收該簇成員節(jié)點收集到的傳感數(shù)據(jù)，并將融合后的數(shù)據(jù)轉(zhuǎn)發(fā)到基站.所以，簇頭節(jié)點的能耗主要包括接收數(shù)據(jù)的能耗、融合數(shù)據(jù)的能耗和向下一簇頭發(fā)送數(shù)據(jù)的能耗.根據(jù)公式(1)、(3)、(4)，如果簇內(nèi)成員節(jié)點的個數(shù)為n，簇頭的發(fā)送距離為d，則該簇頭節(jié)點在一輪中消耗的能量[14]ECH(n,d)為

ECH(n,d)=ETX+ERX+Efuse=(n+1)×lEelec+nlEDA+lεfsd2.

(5)

由式(5)可以得到，簇頭能耗與簇內(nèi)節(jié)點的數(shù)量n和簇頭的發(fā)送距離d的關(guān)系分別為：

(6)

其中：1≤n≤100；0≤d≤Dthreshold.則ECH(n)和ECH(d)的取值范圍分別為：

(7)

由式(7)可知，簇內(nèi)節(jié)點的數(shù)量對簇頭能耗的影響要遠(yuǎn)大于發(fā)送距離對其的影響.所以均衡簇內(nèi)節(jié)點的數(shù)量對均衡簇頭的能量消耗起著主導(dǎo)性的作用.

2.2 簇頭位置對網(wǎng)絡(luò)能耗的影響分析

假設(shè)一個簇中10個節(jié)點隨機分布在10 m×10 m的監(jiān)測區(qū)域內(nèi)，如圖1所示，計算這10個節(jié)點分別充當(dāng)簇頭時，簇頭節(jié)點與其他節(jié)點之間的距離之和與網(wǎng)絡(luò)能耗，如圖2所示.

圖1 節(jié)點分布位置圖

圖2 簇頭位置和網(wǎng)絡(luò)能耗關(guān)系對比圖

從圖2中可以看出，網(wǎng)絡(luò)能耗與距離和(簇頭節(jié)點與其他簇內(nèi)節(jié)點之間的距離之和)成正比關(guān)系.其中，節(jié)點10與其他節(jié)點之間的距離和最小，當(dāng)簇頭位置在節(jié)點10上時，網(wǎng)絡(luò)能耗也是最小的.所以，在簇頭選舉時，選擇距離和越小的節(jié)點作為簇頭越能降低網(wǎng)絡(luò)的能耗.

3 基于均勻分區(qū)的WSN路由算法

3.1 均勻分區(qū)

根據(jù)2.1節(jié)中關(guān)于簇頭節(jié)點能耗的分析可知，簇內(nèi)節(jié)點的數(shù)量是影響簇頭能耗的主要因素.由此，本文提出均勻分區(qū)的方法，通過均衡各分區(qū)內(nèi)節(jié)點的數(shù)量，同時在各分區(qū)中選取能使網(wǎng)絡(luò)能耗最小的節(jié)點充當(dāng)簇頭，從而均衡簇頭負(fù)載能耗，有效減小網(wǎng)絡(luò)能耗.

3.1.1 最優(yōu)簇頭數(shù)的確定

根據(jù)監(jiān)測區(qū)域的大小和節(jié)點的數(shù)量計算出所需的簇頭數(shù)，設(shè)有N個節(jié)點隨機分布在M×N的區(qū)域中，得到最優(yōu)簇頭數(shù)[15]kopt為

(8)

其中，dtoBS是節(jié)點到基站之間的平均距離.

3.1.2 初始簇頭的選擇

假設(shè)在M×M的監(jiān)測區(qū)域中，隨機分布N個節(jié)點，需要從其中隨機選取kopt個節(jié)點作為簇頭，要求這kopt個節(jié)點兩兩之間距離大于間隔值Dmin.

本文采用改進(jìn)的多叉樹遍歷算法來求解初始簇頭的位置，該算法的具體求解思路是：先隨機選擇一個根節(jié)點，根據(jù)節(jié)點間的距離信息，將與該節(jié)點(父節(jié)點)距離大于約束距離Dmin的節(jié)點均設(shè)為該節(jié)點的子節(jié)點；再根據(jù)同樣的距離約束條件，設(shè)定每個子節(jié)點(此時為父節(jié)點)的下一級子節(jié)點；以此類推，完成節(jié)點多叉樹的構(gòu)建，如圖3(a)所示.接下來，要找到一條滿足所有子節(jié)點與父節(jié)點的距離大于Dmin約束條件且層數(shù)為kopt的路徑，判斷該條路徑中kopt個節(jié)點是否滿足兩兩之間距離均大于Dmin的總條件，若滿足，則記錄節(jié)點信息，停止循環(huán)；否則，選擇下一條路徑并判斷其中的節(jié)點是否滿足以上條件.

如圖3(b)所示，先隨機選出一個節(jié)點a1，根據(jù)子節(jié)點與父節(jié)點之間的距離大于Dmin的約束條件，找到第一條路徑a1→a2→a4，其中a1和a2、a2和a4滿足距離大于Dmin的約束條件.下一步判斷a1、a2、a4這三個節(jié)點是否滿足兩兩之間距離均大于Dmin的總條件.從圖3(a)中可看出，與a1節(jié)點距離大于間隔值Dmin的節(jié)點有a2、a3、a5，其中沒有a4，所以，節(jié)點a1與a4之間的距離不符合條件.檢查下一條路徑a1→a2→a5，其中a1和a2、a2和a5滿足距離大于Dmin的約束條件，同時a5又是a1節(jié)點的子節(jié)點，所以a1和a5之間的距離也符合距離大于Dmin的約束條件.所以，節(jié)點a1、a2與a5之間符合兩兩之間距離大于Dmin的約束條件，選為初始簇頭，示于圖3(b)中的陰影節(jié)點，記錄節(jié)點信息，并停止循環(huán).可見，改進(jìn)后的多叉樹遍歷算法在被選取節(jié)點的隨機性前提下，可以使選出的節(jié)點分布更加均勻.

圖3 多叉樹示例圖

根據(jù)以上多叉樹遍歷算法求解初始簇頭的位置.其中，根據(jù)監(jiān)測區(qū)域的面積以及最優(yōu)簇頭數(shù)計算出的間隔值Dmin為

(9)

3.1.3 節(jié)點選擇分區(qū)

計算節(jié)點與各初始簇頭之間的距離權(quán)值，節(jié)點根據(jù)最小的距離權(quán)值選擇加入的分區(qū).本文定義的距離權(quán)值函數(shù)W(nodei,aj)為：

(10)

其中：dis(nodei,aj)是節(jié)點nodei與初始簇頭之間的距離；ni是初始簇頭aj所在區(qū)域當(dāng)前擁有的節(jié)點個數(shù)；uj為該分區(qū)節(jié)點數(shù)量的上限，如式(11)所示.

(11)

其中，Nalive是當(dāng)前輪網(wǎng)絡(luò)中存活節(jié)點的個數(shù).

由式(10)和式(11)可知，當(dāng)各區(qū)域節(jié)點個數(shù)未達(dá)到上限值時，節(jié)點根據(jù)距離最近原則加入分區(qū)；當(dāng)該區(qū)域節(jié)點個數(shù)達(dá)到上限值時，則不再接收新的節(jié)點加入,這樣就可以有效地控制各區(qū)域節(jié)點的數(shù)量.

3.2 簇頭競選

根據(jù)均勻分區(qū)可得到kopt個節(jié)點數(shù)量均勻的區(qū)域，在每個區(qū)域中選擇一個能耗權(quán)值最小的節(jié)點充當(dāng)簇頭節(jié)點.由2.2節(jié)知，簇頭節(jié)點與其成員節(jié)點之間的距離和越小，網(wǎng)絡(luò)的能量消耗就越小，同時考慮到簇頭節(jié)點的剩余能量，可得到競選簇頭時節(jié)點的能耗權(quán)值WCH(nodei)為

(12)

3.3 節(jié)點通信

在WSN分層路由算法中，節(jié)點通信可分為簇內(nèi)通信和簇間通信.節(jié)點將收集到的數(shù)據(jù)發(fā)送到簇頭節(jié)點的過程被稱為簇內(nèi)通信；簇頭節(jié)點將數(shù)據(jù)轉(zhuǎn)發(fā)到基站則稱為簇間通信.本文采用的節(jié)點通信方式具體如下：

1) 簇內(nèi)通信距離通常小于距離閾值.為了避免傳輸信號出現(xiàn)沖突，簇內(nèi)通信采取單跳的方式進(jìn)行通信.

2) 如果簇頭節(jié)點與基站之間的距離大于距離閾值，采用單跳的方式會急速消耗網(wǎng)絡(luò)能量，此時簇間通信采用多跳的方式將數(shù)據(jù)轉(zhuǎn)發(fā)到基站；如果簇頭節(jié)點與基站之間的距離小于距離閾值，則簇間通信采取直接與基站進(jìn)行通信的方式.

4 仿真驗證

為了驗證本文提出的路由算法的有效性，采用Matlab對其進(jìn)行了仿真實驗測試，并與LEACH算法、EECPK-means算法和能量質(zhì)心算法進(jìn)行了對比分析，具體的實驗仿真參數(shù)見表1.

4.1 簇結(jié)構(gòu)對比分析

根據(jù)式(13),在100 m×100 m的區(qū)域隨機生成100個節(jié)點的位置，第i個節(jié)點的橫、縱坐標(biāo)分別為S(i)·x和S(i)·y，rand()用來生成[0,1]之間均勻分布的隨機數(shù).根據(jù)3.1節(jié)中的均勻分區(qū)方法對監(jiān)測區(qū)域進(jìn)行分區(qū)，再使用能量質(zhì)心算法和EECPK-means算法對監(jiān)測區(qū)域進(jìn)行分區(qū)，得到三種算法各分區(qū)節(jié)點數(shù)量對比圖，如圖4所示.由圖4可見，本文算法中各區(qū)域節(jié)點數(shù)最為均衡.

圖4 3種算法各分區(qū)節(jié)點數(shù)量對比

(13)

此外，分別對EECPK-means算法、能量質(zhì)心算法和本文算法進(jìn)行5輪觀測，并記錄下各簇頭(C1,C2,C3,C4)的標(biāo)識號，見表2.從表2可以看出:能量質(zhì)心算法和EECPK-means算法都有一個共同的缺點，即同一個節(jié)點會連續(xù)多次被選為簇頭節(jié)點，導(dǎo)致節(jié)點能量快速消耗；而本文算法的各區(qū)隨著每輪初始簇頭的變化而發(fā)生位置上變化，從而影響簇頭位置的變化，能夠在一定程度上將簇頭能耗分?jǐn)偨o不同節(jié)點.

表2 3種算法5輪觀測中簇頭的標(biāo)識號

4.2 網(wǎng)絡(luò)壽命對比分析

分別對LEACH算法、EECPK-means算法、能量質(zhì)心算法和本文算法進(jìn)行仿真，得到4種算法網(wǎng)絡(luò)壽命與時間的關(guān)系，如圖5所示.從圖5中可以看出:本文提出的算法有效地延長了第一個能量耗盡節(jié)點的壽命，其主要原因是本文提出的分區(qū)方式具有較大的優(yōu)勢，能夠有效地均衡各區(qū)節(jié)點的數(shù)量，并且在一定程度上分?jǐn)偞仡^的能耗；并且，當(dāng)算法運行到第800輪時，本文算法網(wǎng)絡(luò)中還有74個節(jié)點存活，能量質(zhì)心算法有48個節(jié)點存活，EECPK-means算法有35個節(jié)點存活，LEACH算法僅有6個節(jié)點存活.可見，本文算法能夠有效地提高網(wǎng)絡(luò)的生存周期.

圖5 4種算法網(wǎng)絡(luò)生存周期對比

4.3 網(wǎng)絡(luò)能量利用率對比分析

WSN是一種以采集傳感數(shù)據(jù)為目的且能量受限的網(wǎng)絡(luò)，所以除了網(wǎng)絡(luò)壽命，網(wǎng)絡(luò)的能量利用率也是WSN另一重要的性能指標(biāo).網(wǎng)絡(luò)能量利用率越高，說明算法越節(jié)能.網(wǎng)絡(luò)的初始能量為50 J，圖6給出了4種算法網(wǎng)絡(luò)能耗與基站接收數(shù)據(jù)包數(shù)量之間的關(guān)系.從圖6中可以看出，在接收數(shù)據(jù)包的數(shù)量為2 000個時，本文算法消耗8.884 J能量，能量質(zhì)心算法消耗了12.09 J能量，EECPK-means算法消耗了16.2 J能量，LEACH算法消耗了48.77 J能量.可知，在接收數(shù)據(jù)包的數(shù)量相同時，本文算法消耗的能量最小，能量利用率最高.其主要原因是，本文算法在簇頭的選舉時優(yōu)先選擇與分區(qū)內(nèi)其他節(jié)點之間的距離和最小的節(jié)點，從而使網(wǎng)絡(luò)能耗最小，并且從圖5中可以看出，在同一時間，本文算法網(wǎng)絡(luò)中存活節(jié)點的數(shù)量也最多.

圖6 4種算法網(wǎng)絡(luò)能量利用率對比

5 結(jié)論

本文從均衡簇頭負(fù)載和優(yōu)化網(wǎng)絡(luò)能耗兩個方面出發(fā)，針對分層路由算法中出現(xiàn)的節(jié)點過早死亡、簇頭負(fù)載不均衡等問題，提出了基于均勻分區(qū)的無線傳感器網(wǎng)絡(luò)路由算法.首先采用改進(jìn)的多叉樹遍歷算法隨機選取分布均勻的初始簇頭，從而使每輪產(chǎn)生不同的簇頭，避免了節(jié)點連續(xù)多次被選為簇頭的現(xiàn)象，在一定程度上分?jǐn)偭舜仡^能耗；然后基于距離權(quán)值函數(shù)進(jìn)行分區(qū)，均衡了簇頭的負(fù)載；最后，通過分析簇頭位置和網(wǎng)絡(luò)能耗的關(guān)系得到最優(yōu)簇頭位置，優(yōu)化了網(wǎng)絡(luò)能耗.仿真結(jié)果表明：本文提出的算法能有效均衡簇頭負(fù)載，避免節(jié)點過早死亡，延長網(wǎng)絡(luò)的生存周期，同時提高網(wǎng)絡(luò)的能量利用率.