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

劉玉紅，陳滿銀，李翠然

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

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

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

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

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

1.1 無(wú)線通信能耗模型

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

(1)

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

(2)

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

ERX(l)=lEelec.

(3)

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

Efuse(m)=m×lEDA,

(4)

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

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

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

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

2 WSN能耗分析

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

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

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

(5)

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

(6)

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

(7)

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

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

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

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

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

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

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

3.1 均勻分區(qū)

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

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

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

(8)

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

3.1.2 初始簇頭的選擇

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

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

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

圖3 多叉樹(shù)示例圖

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

(9)

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

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

(10)

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

(11)

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

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

3.2 簇頭競(jìng)選

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

(12)

3.3 節(jié)點(diǎn)通信

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

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

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

4 仿真驗(yàn)證

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

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

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

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

(13)

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

表2 3種算法5輪觀測(cè)中簇頭的標(biāo)識(shí)號(hào)

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

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

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

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

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

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

5 結(jié)論

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