基于改進短鏈聚合策略的無線傳感器網絡路由算法

潘繼強, 何立風, 達列雄, 周廣彬

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

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

1 算法設計

1.1 無線傳感器網絡

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

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

圖2 無線傳感器網絡協議結構Fig.2 Protocol architecture of wireless sensor network

1.2 改進短鏈聚合策略及數據傳輸能耗計算

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

構建PBRE算法和PEGASIS算法使用相同的網絡模型與節點能耗模型, 其中： 基站固定, 遠離傳感器節點； 網絡內節點種類相同, 初始能量相同； 網絡中的節點無移動性； 各節點均清楚其他節點的地理位置相關信息, 具有與基站直接通信的能力.

網絡中的節點能耗主要為數據傳送ETx、 數據接收ERx和數據融合Eda_fu.節點傳送、 接收與融合lbit數據所消耗的能量計算公式[7]為

(1)

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

根據改進短鏈聚合策略, 利用式(1)計算得到數據傳輸能耗. 為進一步驗證本文算法的優勢, 本文改進了無線傳感器網絡路由算法.

1.3 無線傳感器網絡路由算法

基于改進短鏈聚合策略的無線傳感器網絡路由算法設計過程如下.

1.3.1 建 鏈

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

(2)

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

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

1.3.2 簇頭選舉

因為無線傳感網絡內有多個簇頭, 因此可根據簇頭成鏈法實現能耗的進一步降低[9].在簇頭選舉時可能會涉及到鄰居鏈簇頭位置, 因此先不選舉簇頭, 只構建一個鄰居鏈表.

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

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

(3)

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

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

步驟3) 在鄰居鏈表內找出與基站距離最近的鏈, 根據

(4)

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

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

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

1.3.3 數據傳輸

在數據傳輸時, 因為支鏈節點了解自身在鏈中的位置, 因此能計算自身得到的時隙[12-13]. 無線傳感器網絡內每條鏈數據傳輸模式都與PEGASIS算法一致. 當無線傳感器網絡內節點數量最多的鏈實現數據傳輸后, 利用最接近基站的鏈簇頭作為最終簇頭, 分布Token至簇頭構成鏈的端節點, 每個簇頭將自身鏈上的數據向最終簇頭傳輸, 最后根據最終簇頭將數據傳輸至基站.

2 實驗結果與分析

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

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

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

圖3 不同方法網絡存活節點與時間的變化關系對比Fig.3 Comparison of change relationship between network survival nodes and time of different methods

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

圖4 不同方法的網絡生命周期對比Fig.4 Comparison of network life cycle of different methods

圖5 不同方法網絡剩余能量與時間的變化關系對比Fig.5 Comparison of change relationship between network residual energy and time of different methods

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