基于改進(jìn)短鏈聚合策略的無線傳感器網(wǎng)絡(luò)路由算法

潘繼強, 何立風(fēng), 達(dá)列雄, 周廣彬

(1. 陜西理工大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院, 陜西 漢中 723000； 2. 陜西科技大學(xué) 電子信息與人工智能學(xué)院, 西安 710021)

傳感器技術(shù)是信息采集最重要、 最基本的途徑之一[1]. 傳感器網(wǎng)絡(luò)是根據(jù)自組織方式構(gòu)成的無線網(wǎng)絡(luò)[2], 由傳感器模塊、 數(shù)據(jù)處理模塊和通信模塊組成. 在無線傳感器網(wǎng)絡(luò)運行過程中, 路由算法至關(guān)重要. 由于路由算法對傳感器節(jié)點能量約束較大, 因此網(wǎng)絡(luò)體系結(jié)構(gòu)的設(shè)計對整個網(wǎng)絡(luò)的能量消耗和運行壽命影響很大. 為延長無線傳感器網(wǎng)絡(luò)壽命, 必須考慮能量效率. 目前已有許多類型的路由算法和協(xié)議. 文獻(xiàn)[3]提出了基于優(yōu)化蟻群算法找到無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑, 根據(jù)距離因子優(yōu)化啟發(fā)信息函數(shù), 采用最優(yōu)路徑度量公式優(yōu)化選擇方案, 在最少能耗下使螞蟻選擇最優(yōu)路徑. 文獻(xiàn)[4]提出了一種基于模糊邏輯的無線傳感器網(wǎng)絡(luò)不均等聚類算法, 將傳感器節(jié)點組織為分層結(jié)構(gòu), 通過聚合方法減少向基站的數(shù)據(jù)傳輸, 并延長網(wǎng)絡(luò)壽命. 研究表明, 所有網(wǎng)絡(luò)節(jié)點之間輪換簇頭(cluster head, CH)角色并調(diào)整CH條件群集大小, 選擇每個區(qū)域中剩余能量最高的節(jié)點作為候選CH, 其中最好的節(jié)點將被選為最終的CH, 采用模糊邏輯調(diào)整聚類半徑. 文獻(xiàn)[5]提出了一種分布式能量感知模糊邏輯路由算法(distributed energy aware fuzzy logic routing algorithm, DEFL), 同時解決了能量效率和能量均衡問題, 通過適當(dāng)?shù)哪芰恐笜?biāo)獲取網(wǎng)絡(luò)狀態(tài), 并將其映射到相應(yīng)的成本值中, 以進(jìn)行最短路徑的計算. 文獻(xiàn)[6]將低功耗自適應(yīng)分簇協(xié)議(low energy adaptive clustering hierarchy, LEACH)擴展為低能耗自適應(yīng)分簇拆分和合并協(xié)議(low energy adaptive clustering hierarchy-split and merge, LEACH-SM), 通過引入拆分和合并階段提高LEACH協(xié)議的性能和健壯性. 上述方法均可提高整個傳感器網(wǎng)絡(luò)的生命周期, 但對于無線傳感器的短鏈聚合并未進(jìn)行進(jìn)一步研究, 僅從宏觀上實現(xiàn)了網(wǎng)絡(luò)均衡控制. 基于此, 本文提出一種基于改進(jìn)短鏈聚合策略的無線傳感器網(wǎng)絡(luò)路由算法, 構(gòu)建網(wǎng)絡(luò)模型與節(jié)點能耗模型, 從距離基站最遠(yuǎn)的節(jié)點起建鏈, 利用貪心算法找到鄰居節(jié)點, 通過簇頭成鏈法建立鄰簇頭, 以進(jìn)一步降低能耗, 確保設(shè)計能量有效的網(wǎng)絡(luò)路由協(xié)議并延長網(wǎng)絡(luò)生存期.

1 算法設(shè)計

1.1 無線傳感器網(wǎng)絡(luò)

無線傳感網(wǎng)絡(luò)中, 不同應(yīng)用節(jié)點的硬件結(jié)構(gòu)存在差異, 但基本上包括數(shù)據(jù)采集、 數(shù)據(jù)傳輸、 數(shù)據(jù)處理和能量供應(yīng)幾部分, 如圖1所示. 圖2為無線傳感器網(wǎng)絡(luò)協(xié)議結(jié)構(gòu). 由圖2可見, 網(wǎng)絡(luò)管理包括能量管理、 任務(wù)管理和移動管理, 應(yīng)用層、 傳輸層、 網(wǎng)絡(luò)層、 物理層和數(shù)據(jù)鏈路層構(gòu)成了橫向通信協(xié)議層.

圖1 傳感器節(jié)點硬件示意圖Fig.1 Schematic diagram of hardware for sensor node

圖2 無線傳感器網(wǎng)絡(luò)協(xié)議結(jié)構(gòu)Fig.2 Protocol architecture of wireless sensor network

1.2 改進(jìn)短鏈聚合策略及數(shù)據(jù)傳輸能耗計算

考慮到無線傳感器網(wǎng)絡(luò)運行過程中節(jié)點能量的相關(guān)問題, 根據(jù)PEGASIS(power-efficient gathering in sensor information systems)算法設(shè)計改進(jìn)路由算法PBRE(power is the best route to energy), 算法運行過程中, 根據(jù)改進(jìn)短鏈聚合策略, 在路由簇頭選舉時綜合考量節(jié)點傳輸數(shù)據(jù)能耗與剩余能量, 以達(dá)到延長網(wǎng)絡(luò)壽命并提高數(shù)據(jù)傳輸效率的目的.

構(gòu)建PBRE算法和PEGASIS算法使用相同的網(wǎng)絡(luò)模型與節(jié)點能耗模型, 其中： 基站固定, 遠(yuǎn)離傳感器節(jié)點； 網(wǎng)絡(luò)內(nèi)節(jié)點種類相同, 初始能量相同； 網(wǎng)絡(luò)中的節(jié)點無移動性； 各節(jié)點均清楚其他節(jié)點的地理位置相關(guān)信息, 具有與基站直接通信的能力.

網(wǎng)絡(luò)中的節(jié)點能耗主要為數(shù)據(jù)傳送ETx、 數(shù)據(jù)接收ERx和數(shù)據(jù)融合Eda_fu.節(jié)點傳送、 接收與融合lbit數(shù)據(jù)所消耗的能量計算公式[7]為

(1)

其中ERx和Eda_fu分別表示節(jié)點無線收、 發(fā)所耗費的能量,εamp和εfs分別表示無線路由傳送信道、 接收信道和功率放大所耗費的能量,d0為一個常數(shù),d表示傳送節(jié)點至接收節(jié)點之間的距離.

根據(jù)改進(jìn)短鏈聚合策略, 利用式(1)計算得到數(shù)據(jù)傳輸能耗. 為進(jìn)一步驗證本文算法的優(yōu)勢, 本文改進(jìn)了無線傳感器網(wǎng)絡(luò)路由算法.

1.3 無線傳感器網(wǎng)絡(luò)路由算法

基于改進(jìn)短鏈聚合策略的無線傳感器網(wǎng)絡(luò)路由算法設(shè)計過程如下.

1.3.1 建 鏈

PBRE算法與PEGASIS算法相同, 均從距離基站最遠(yuǎn)的節(jié)點起建鏈, 通過貪心算法找到鄰居節(jié)點. 以降低建鏈中長鏈生成的可能性為目的, 引入距離門限方程, 計算公式為

(2)

其中i表示某條鏈路中此時節(jié)點的跳數(shù),dv表示某條鏈路中前(i-1)跳與某跳節(jié)點之間的距離,α表示可調(diào)節(jié)參數(shù).

根據(jù)式(2), 按下列思想實現(xiàn)建鏈： 如果鏈中的第i跳與第(i+1)跳節(jié)點之間的距離比門限值大, 則該鏈在成鏈后, 即第(i+1)跳節(jié)點不再參與到該鏈中, 繼續(xù)在剩余節(jié)點中選擇出與基站距離最遠(yuǎn)的節(jié)點作為下條鏈的初始節(jié)點, 利用該方法建鏈, 直到遍歷完網(wǎng)絡(luò)中全部節(jié)點.但該方法易導(dǎo)致網(wǎng)絡(luò)內(nèi)出現(xiàn)部分短鏈, 這是因為在建鏈過程中, 鏈中的一些節(jié)點之間距離較短, 降低了距離門限值, 導(dǎo)致一些距離該鏈較近的節(jié)點無法添加至該鏈中[8].短鏈中節(jié)點簇頭整體輪換次數(shù)較多, 易導(dǎo)致短鏈死亡.針對該問題, 本文提出了改進(jìn)短鏈聚合策略.將節(jié)點數(shù)量小于等于3的鏈稱為短鏈, 根據(jù)距離門限方程判斷節(jié)點建鏈后的每條鏈.如果是短鏈, 則根據(jù)該鏈鏈頭h與鏈尾t在網(wǎng)絡(luò)內(nèi)找到與自己距離最接近的節(jié)點k, 如果節(jié)點k與自身更接近, 則該短鏈可與找到的節(jié)點k連接, 將此作為支鏈添加至k節(jié)點所處鏈中.利用短鏈聚合策略能高效減少網(wǎng)絡(luò)內(nèi)短鏈的生成, 從而達(dá)到延長網(wǎng)絡(luò)生存時間的目的.

1.3.2 簇頭選舉

因為無線傳感網(wǎng)絡(luò)內(nèi)有多個簇頭, 因此可根據(jù)簇頭成鏈法實現(xiàn)能耗的進(jìn)一步降低[9].在簇頭選舉時可能會涉及到鄰居鏈簇頭位置, 因此先不選舉簇頭, 只構(gòu)建一個鄰居鏈表.

步驟1) 各鏈先對自身所處位置進(jìn)行估計, 得到該鏈的中心坐標(biāo)為

X(i)=xi(1)+…+xi(n)/n,Y(i)=yi(1)+…+yi(n)/n,

(3)

其中n表示該鏈節(jié)點數(shù)量,xi和yi表示鏈上節(jié)點坐標(biāo),X(i)和Y(i)表示該鏈估計出的中心坐標(biāo).

步驟2) 根據(jù)步驟1)得到的位置, 先對比識別出與基站距離最遠(yuǎn)的鏈, 作為初始鏈, 再根據(jù)貪心算法獲取其鄰居鏈, 直到遍歷完所有鏈, 構(gòu)建完成一個鄰居鏈表.

步驟3) 在鄰居鏈表內(nèi)找出與基站距離最近的鏈, 根據(jù)

(4)

提供的簇頭選舉機制, 將EC值較小的節(jié)點作為該鏈簇頭, 其中EC表示節(jié)點能量代價的一個評估標(biāo)準(zhǔn),e(i)表示鏈上節(jié)點i的剩余能量,en表示節(jié)點的初始能量,ETx_max表示該鏈上節(jié)點傳送1 bit數(shù)據(jù)至目標(biāo)節(jié)點所消耗的最大能量.

步驟4) 選舉根據(jù)上述步驟獲取鏈的鄰居鏈簇頭, 仍采用式(4)的選舉機制, 其目標(biāo)節(jié)點修改為步驟3)選舉出的簇頭. 利用該方法繼續(xù)選舉簇頭, 將每次目標(biāo)節(jié)點修改為上步已經(jīng)選舉出的簇頭, 直到選舉出所有鏈簇頭為止.

式(4)給出了能量代價評估方法, 這種簇頭選舉法綜合考量了節(jié)點傳送數(shù)據(jù)所需的能量和剩余能量. 因為網(wǎng)絡(luò)模型要求基站要遠(yuǎn)離監(jiān)測點, 因此ETx(i)和ETx_max值差距較小. 在EC評價標(biāo)準(zhǔn)中, 無線傳感器網(wǎng)絡(luò)節(jié)點能耗影響因素占比較小, 因此可用相應(yīng)的參數(shù)對節(jié)點能耗和剩余能量在評價標(biāo)準(zhǔn)中的占比進(jìn)行調(diào)節(jié)[10-11].

1.3.3 數(shù)據(jù)傳輸

在數(shù)據(jù)傳輸時, 因為支鏈節(jié)點了解自身在鏈中的位置, 因此能計算自身得到的時隙[12-13]. 無線傳感器網(wǎng)絡(luò)內(nèi)每條鏈數(shù)據(jù)傳輸模式都與PEGASIS算法一致. 當(dāng)無線傳感器網(wǎng)絡(luò)內(nèi)節(jié)點數(shù)量最多的鏈實現(xiàn)數(shù)據(jù)傳輸后, 利用最接近基站的鏈簇頭作為最終簇頭, 分布Token至簇頭構(gòu)成鏈的端節(jié)點, 每個簇頭將自身鏈上的數(shù)據(jù)向最終簇頭傳輸, 最后根據(jù)最終簇頭將數(shù)據(jù)傳輸至基站.

2 實驗結(jié)果與分析

為驗證基于改進(jìn)短鏈聚合策略無線傳感器網(wǎng)絡(luò)路由算法的可靠性, 對該算法進(jìn)行仿真實驗. 將實驗平臺搭建在MATLAB上對算法進(jìn)行模擬, 并分析算法性能.

仿真參數(shù)設(shè)置如下： 在仿真環(huán)境中設(shè)一個100 m×100 m的區(qū)域, 任意分布100個節(jié)點. 實驗中,ETx=ERx=50 pJ/bit,εfs=20(pJ·bit-1)/m2,εamp=0.0013(pJ·bit-1)/m2,d0=87[14]. 控制包為100 bit, 網(wǎng)絡(luò)節(jié)點傳送的數(shù)據(jù)包為4000 bit, 各節(jié)點的初始能量均為1 J.

用文獻(xiàn)[3]方法和文獻(xiàn)[4]方法作為實驗對比方法, 測試網(wǎng)絡(luò)存活節(jié)點與時間之間的變化關(guān)系, 實驗結(jié)果如圖3所示. 由圖3可見, 文獻(xiàn)[3]方法在無線傳感器網(wǎng)絡(luò)傳輸時間為1 600 s時存活節(jié)點數(shù)量為0, 文獻(xiàn)[4]方法存活節(jié)點數(shù)量為0的時間為1 400 s, 而本文方法的節(jié)點存活時間為2 100 s, 表明本文方法的節(jié)點存活時間更長, 增強了節(jié)點均衡性.

圖3 不同方法網(wǎng)絡(luò)存活節(jié)點與時間的變化關(guān)系對比Fig.3 Comparison of change relationship between network survival nodes and time of different methods

圖4為不同方法的網(wǎng)絡(luò)生命周期對比. 由圖4可見： 在存活節(jié)點相同的情況下, 本文方法運行時間為1 250 s, 而文獻(xiàn)[3]、 文獻(xiàn)[4]方法分別為550 s和900 s； 當(dāng)剩余能量相同時, 本文方法運行時間為1 600 s, 而文獻(xiàn)[3]、 文獻(xiàn)[4]方法分別為850 s和1 100 s. 由于考慮了節(jié)點能耗問題, 所以本文方法能將無線傳感網(wǎng)絡(luò)傳輸節(jié)點的多個短鏈聚合, 利用簇頭成鏈法, 均衡網(wǎng)絡(luò)節(jié)點能耗, 不但延長了網(wǎng)絡(luò)的整體生命周期, 還增強了其均衡性. 圖5為不同方法網(wǎng)絡(luò)剩余能量與時間的變化關(guān)系對比. 隨著時間的延長, 網(wǎng)絡(luò)剩余能量為0, 達(dá)到提升網(wǎng)絡(luò)均衡的目的. 由圖5可見, 本文方法運行過程中能有效減少簇頭選舉次數(shù), 降低了簇頭選舉所花費的額外能耗, 并且兼顧了網(wǎng)絡(luò)剩余能量較低的節(jié)點, 提升了網(wǎng)絡(luò)均衡性.

圖4 不同方法的網(wǎng)絡(luò)生命周期對比Fig.4 Comparison of network life cycle of different methods

圖5 不同方法網(wǎng)絡(luò)剩余能量與時間的變化關(guān)系對比Fig.5 Comparison of change relationship between network residual energy and time of different methods

綜上所述, 本文提出了一種基于改進(jìn)短鏈聚合策略的無線傳感器網(wǎng)絡(luò)路由算法, 并通過仿真實驗驗證了算法的有效性及魯棒性.