基于節(jié)點(diǎn)密度加權(quán)的T-LEACH三維動態(tài)路由協(xié)議研究*

余　敏，李雅晴，張　琦，唐　瑞

（1.江西師范大學(xué)計算機(jī)學(xué)院，南昌330022；2.江西師范大學(xué)軟件學(xué)院，南昌330022）

?

基于節(jié)點(diǎn)密度加權(quán)的T-LEACH三維動態(tài)路由協(xié)議研究*

余敏1*，李雅晴2，張琦2，唐瑞2

（1.江西師范大學(xué)計算機(jī)學(xué)院，南昌330022；2.江西師范大學(xué)軟件學(xué)院，南昌330022）

摘要：隨著無線傳感網(wǎng)絡(luò)在三維動態(tài)環(huán)境應(yīng)用需求的俱增，如何在動態(tài)拓?fù)涞娜S網(wǎng)絡(luò)環(huán)境下，設(shè)計能量高效和數(shù)據(jù)傳輸高可靠性的路由協(xié)議是當(dāng)前學(xué)術(shù)界的研究熱點(diǎn)?，F(xiàn)有的三維路由協(xié)議未充分考慮節(jié)點(diǎn)移動和環(huán)境因素的影響，多為二維靜態(tài)協(xié)議的補(bǔ)充和支持。將拓?fù)浣Y(jié)構(gòu)和地理結(jié)構(gòu)的路由協(xié)議相結(jié)合，提出了基于節(jié)點(diǎn)密度加權(quán)的T-LEACH三維動態(tài)路由協(xié)議。使用T-LEACH算法獲得全局節(jié)點(diǎn)密度信息，DDRS算法預(yù)知路由空洞和使用DDRS-R的恢復(fù)算法逃逸空洞和修正路由，有效地實(shí)現(xiàn)規(guī)避局部最優(yōu)問題和迅速逃逸路由空洞的目標(biāo)，提高了網(wǎng)絡(luò)整體的健壯性和生存時間。通過在課題組設(shè)計的無線傳感器網(wǎng)絡(luò)三維環(huán)境路由協(xié)議仿真平臺上的實(shí)驗(yàn)和對比，證明本文提出的路由協(xié)議在能量消耗，網(wǎng)絡(luò)生存期及數(shù)據(jù)交付率等方面優(yōu)于現(xiàn)有協(xié)議，具有良好的應(yīng)用前景。

關(guān)鍵詞：無線傳感網(wǎng)；三維動態(tài)；路由協(xié)議；能量消耗；路由空洞；節(jié)點(diǎn)密度

隨著無線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Networks）技術(shù)的發(fā)展，二維環(huán)境下無線傳感器網(wǎng)絡(luò)路由協(xié)議已趨于成熟，然而多數(shù)應(yīng)用場景的無線傳感器網(wǎng)絡(luò)不能簡單視為二維平面。目前三維環(huán)境的路由協(xié)議絕大部分是對現(xiàn)有成熟的二維靜態(tài)拓?fù)鋮f(xié)議的補(bǔ)充和擴(kuò)展，并未對傳感器節(jié)點(diǎn)動態(tài)加入與退出，以及環(huán)境條件影響傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)提出解決方案。如COMPOW［1］等功率分配算法，能夠有效降低能量消耗，但組織成型速度過慢且不利于應(yīng)對動態(tài)變化的網(wǎng)絡(luò)環(huán)境。Roland Flury等人提出的三維隨機(jī)游走路由協(xié)議［2］通過建立特定的拓?fù)浣Y(jié)構(gòu)，將隨機(jī)游走模型運(yùn)用于三維環(huán)境中，但運(yùn)算量及實(shí)時性較差，不能運(yùn)用于動態(tài)網(wǎng)絡(luò)中。GP?SR［3］，DREAM［4］，GRID［5］均是二維環(huán)境下基于地理位置的路由協(xié)議其典型代表。Abdallah A E等人提出的AB3D［6］算法，通過降維和映射機(jī)制將FACE［7］算法拓展至三維空間，能夠有效解決三維空間內(nèi)的路由空洞問題，但這些算法只能夠部分適應(yīng)動態(tài)網(wǎng)絡(luò)，應(yīng)對變化劇烈的環(huán)境或節(jié)點(diǎn)分布不均勻的網(wǎng)絡(luò)，算法運(yùn)行額外開銷大且無法解決路由空洞問題。因此，針對三維動態(tài)傳感器網(wǎng)絡(luò)環(huán)境，提出一套有效的路由協(xié)議，具有重要研究價值和應(yīng)用前景。

LEACH［8］算法是一個經(jīng)典的層次型拓?fù)浣Y(jié)構(gòu)算法，Multihop- LEACH［9］協(xié)議、ILEACH［10］算法、LEACH-Mobile［11］協(xié)議、CBR［12］機(jī)制協(xié)議、文獻(xiàn)［13-14］分別對LEACH協(xié)議的缺點(diǎn)進(jìn)行了改進(jìn)，降低了簇頭節(jié)點(diǎn)的能量消耗，提升了網(wǎng)絡(luò)生存期。其中，課題組提出T-LEACH［15］，設(shè)計了數(shù)據(jù)采集樹機(jī)制、簇頭節(jié)點(diǎn)反應(yīng)機(jī)制、多跳傳輸方案三大機(jī)制，相比其他改進(jìn)方案在降低能量消耗的同時保證了較低的丟包率。本文結(jié)合T-LEACH協(xié)議的優(yōu)點(diǎn)，針對基于地理位置的路由協(xié)議的節(jié)點(diǎn)密度信息進(jìn)行加權(quán)應(yīng)用，提出基于節(jié)點(diǎn)維度密度地理位置路由解決方案。實(shí)驗(yàn)證明，本文提出的路由協(xié)議在能量消耗，網(wǎng)絡(luò)生存期及數(shù)據(jù)交付率等方面優(yōu)于上述現(xiàn)有的協(xié)議，具有良好的應(yīng)用前景。

1　相關(guān)研究及分析

1.1T-LEACH協(xié)議

T-LEACH協(xié)議是課題組提出對LEACH協(xié)議的一個改進(jìn)協(xié)議，主要解決三大問題，一是使用簇間數(shù)據(jù)采集樹解決遠(yuǎn)距離節(jié)點(diǎn)失效的問題，二是提出簇頭節(jié)點(diǎn)反應(yīng)機(jī)制應(yīng)對動態(tài)無線傳感網(wǎng)，三是使用多跳傳輸機(jī)制處理節(jié)點(diǎn)分布不均，時鐘同步難的問題。本節(jié)對T-LEACH協(xié)議的簇頭節(jié)點(diǎn)反應(yīng)機(jī)制和多跳傳輸機(jī)制進(jìn)行簡單介紹。

1.1.1簇頭節(jié)點(diǎn)移動反應(yīng)機(jī)制

與LEACH算法不同，T-LEACH協(xié)議中，節(jié)點(diǎn)在穩(wěn)定階段的時間槽被劃分為若干個片段，每個片段中包含兩個部分，分別為GRT（時段）和MTS時段。如圖1所示，oo’為節(jié)點(diǎn)o在一個GRT時段內(nèi)移動的歐式距離，r為節(jié)點(diǎn)的簇間通訊半徑，設(shè)c為 o的子節(jié)點(diǎn)，p為o的父節(jié)點(diǎn)，e為代理節(jié)點(diǎn)，因oo’＞r，子節(jié)點(diǎn)c無法與簇頭節(jié)點(diǎn)o通信。節(jié)點(diǎn)c首先判斷其移動的歐氏距離cc’是否大于閾值T。如果cc’＜T，那么判定其與簇頭節(jié)點(diǎn)失去聯(lián)系是由于簇頭節(jié)點(diǎn)o的移動造成的，節(jié)點(diǎn)首先在該MTS時段不斷擴(kuò)大其通信半徑至最大為r+T，同時試圖連接簇頭節(jié)點(diǎn)，如果失敗，節(jié)點(diǎn)通過尋找簇頭節(jié)點(diǎn)周圍的代理節(jié)點(diǎn)，如節(jié)點(diǎn)e，追趕簇頭節(jié)點(diǎn)并建立聯(lián)系。

圖1　簇頭節(jié)點(diǎn)移動反應(yīng)機(jī)制

1.1.2多跳傳輸方案

在T-LEACH協(xié)議中，節(jié)點(diǎn)被分為三種類型：簇頭節(jié)點(diǎn)CH，成員節(jié)點(diǎn)M和游離節(jié)點(diǎn)N。T-LEACH協(xié)議提出多跳傳輸方案，在MTS時段，采用功率控制技術(shù)，實(shí)現(xiàn)了動態(tài)調(diào)整發(fā)射功率的目的。在成簇階段，所有CH節(jié)點(diǎn)利用功率控制技術(shù)調(diào)整簇內(nèi)通信半徑r，將成員節(jié)點(diǎn)個數(shù)限制在閾值Tmax和Tmin之間。成員節(jié)點(diǎn)M及游離節(jié)點(diǎn)N之間的通信協(xié)議（偽代碼）如圖2所示。

圖2　MTS中成員節(jié)點(diǎn)的通信協(xié)議示意圖及算法偽代碼

多跳傳輸機(jī)制（MTS）在數(shù)據(jù)采集樹的基礎(chǔ)上，增加了游離節(jié)點(diǎn)和成員節(jié)點(diǎn)的路由方案，降低了單跳傳輸距離，進(jìn)一步解放了簇頭節(jié)點(diǎn)，并保障了功率控制技術(shù)在LEACH算法中的有效應(yīng)用。

T-LEACH算法通過上述三個機(jī)制，能夠應(yīng)用于大型的，且全網(wǎng)節(jié)點(diǎn)可移動的移動傳感器網(wǎng)絡(luò)中。但在移動傳感網(wǎng)中，如果節(jié)點(diǎn)移動速度較快，拓?fù)涓碌念l率提高會造成頻繁的通信中斷；此外，對網(wǎng)絡(luò)拓?fù)涞木S護(hù)也需要消耗大量的能量。

1.2節(jié)點(diǎn)密度信息于地理位置路由中的應(yīng)用

地理位置路由利用自身和目標(biāo)節(jié)點(diǎn)的地理位置信息作為選擇路由的依據(jù)，具有單跳能耗低，簡單高效等優(yōu)勢。在二維環(huán)境下，現(xiàn)有的地理位置路由協(xié)議方案如Greedy［16］，Compass［17］等算法不僅能夠完成節(jié)點(diǎn)路由的功能，還可以減少系統(tǒng)專門維護(hù)路由協(xié)議的能量開銷。然而，基于地理位置的路由協(xié)議均采用貪婪轉(zhuǎn)發(fā)策略，這將造成局部最優(yōu)（local minimum）現(xiàn)象，即路由空洞問題，該問題發(fā)生時，貪婪算法失效。

如圖3即為路由空洞現(xiàn)象，當(dāng)節(jié)點(diǎn)a將數(shù)據(jù)轉(zhuǎn)發(fā)給節(jié)點(diǎn)b時，根據(jù)貪婪轉(zhuǎn)發(fā)策略，b節(jié)點(diǎn)尋找比自己距離目的節(jié)點(diǎn)更接近的節(jié)點(diǎn)，由于這樣的節(jié)點(diǎn)不存在，因此貪婪算法在b節(jié)點(diǎn)處失效。這是因?yàn)閭鞲衅鞴?jié)點(diǎn)為降低通信開銷，僅記錄單跳內(nèi)鄰居節(jié)點(diǎn)的信息，因此利用貪婪算法只能獲得局部最優(yōu)解。

圖3　路由空洞現(xiàn)象

為了盡量規(guī)避路由空洞，并且降低空洞周圍節(jié)點(diǎn)的能量消耗，利用節(jié)點(diǎn)密度信息對路由加權(quán)是普遍的做法。文獻(xiàn)［18］指出，通常情況下，節(jié)點(diǎn)在網(wǎng)絡(luò)區(qū)域中的分布并不均勻，而是以特定概率分布模型散布。網(wǎng)絡(luò)整體的密度信息，是一個有效加權(quán)的因子，可以幫助數(shù)據(jù)分組逃逸路由空洞。通過利用組路由或者密度信息來控制傳輸半徑，規(guī)避路由空洞，并且降低空洞周圍節(jié)點(diǎn)的能量消耗。

文獻(xiàn)［19］提出針對路由空洞的恢復(fù)算法，但目前利用節(jié)點(diǎn)密度信息對路由方案進(jìn)行設(shè)計和改進(jìn)的研究很少，在節(jié)點(diǎn)覆蓋率方面，文獻(xiàn)［20］利用密度信息來控制節(jié)點(diǎn)的傳輸半徑，并關(guān)閉密集區(qū)域中的部分節(jié)點(diǎn)來達(dá)到延長網(wǎng)路生存期的目的，文獻(xiàn)［21］利用節(jié)點(diǎn)密度信息來限制洪泛數(shù)據(jù)包個數(shù)，從而節(jié)省節(jié)點(diǎn)的能量消耗。大多忽視了網(wǎng)絡(luò)整體密度分布對于指引路由過程的可行性。綜上所述，目前大多數(shù)算法主要關(guān)心路由空洞問題出現(xiàn)時，如何實(shí)施補(bǔ)救，缺乏一種提前預(yù)防的機(jī)制，控制路由選擇路徑，從本質(zhì)上降低路由空洞發(fā)生的可能性。

2　基于節(jié)點(diǎn)維度密度加權(quán)的路由協(xié)議

基于地理位置的路由協(xié)議，一般采用貪婪算法和恢復(fù)算法相結(jié)合的設(shè)計方案。貪婪算法具有良好的表現(xiàn)，但隨著網(wǎng)絡(luò)運(yùn)行時間的增加，傳感器節(jié)點(diǎn)的移動和失效造成節(jié)點(diǎn)密度分布不均，并產(chǎn)生路由空洞。此時，貪婪算法頻繁失效，路由空洞周圍的節(jié)點(diǎn)負(fù)擔(dān)加重，造成節(jié)點(diǎn)密度分布進(jìn)一步的惡化，進(jìn)而減少了網(wǎng)絡(luò)整體生存期。如圖4所示，是二維環(huán)境下節(jié)點(diǎn)密度分布不均勻的典型場景。若數(shù)據(jù)在圖中上部低密度區(qū)域中轉(zhuǎn)發(fā)，則極易陷入路由空洞，并造成空洞擴(kuò)大、合并甚至造成網(wǎng)絡(luò)局部失效。若分組能夠在下部高密度區(qū)域轉(zhuǎn)發(fā)，這種情況會有很大的改善。本文利用節(jié)點(diǎn)維度密度信息對路由選擇進(jìn)行加權(quán)，是一個行之有效有效的解決方案。

圖4　二維節(jié)點(diǎn)密度分布不均勻場景

2.1T-LEACH算法對節(jié)點(diǎn)密度信息的采集

本方案采用T-LEACH協(xié)議生成的拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)節(jié)點(diǎn)密度信息采集，并周期性地從所有簇頭節(jié)點(diǎn)獲得密度信息，將必要信息轉(zhuǎn)發(fā)覆蓋全網(wǎng)。

使用T-LEACH算法對節(jié)點(diǎn)維度密度信息采集過程如下：①在整個網(wǎng)絡(luò)空間中建立虛擬坐標(biāo)，對于y維度，設(shè)采樣間隔Iy≥2R（Iy為可設(shè)閾值，R為節(jié)點(diǎn)的通信半徑），將整個網(wǎng)絡(luò)的y軸向以Iy為間隔虛擬地劃分為若干個段。②對于第i個段Ii，計算各節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)的概率開始成簇，成簇后，各簇頭節(jié)點(diǎn)根據(jù)簇間多跳傳輸路徑，將該數(shù)據(jù)和自己的地理位置信息通過數(shù)據(jù)采集樹發(fā)送給Sink節(jié)點(diǎn)，得到各個區(qū)段內(nèi)的節(jié)點(diǎn)密度Di。③Sink節(jié)點(diǎn)根據(jù)各個簇頭節(jié)點(diǎn)的地理位置，發(fā)送N個距離該位置最近的段的密度值和坐標(biāo)值。簇頭節(jié)點(diǎn)轉(zhuǎn)發(fā)至成員節(jié)點(diǎn)后，網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)的使命即宣告完成。④各成員節(jié)點(diǎn)通過插值法獲得各個維度上的密度值。計算公式如式（1）所示。

其中，dj表示當(dāng)前節(jié)點(diǎn)在某一維度上的密度值，disi表示在該維度上節(jié)點(diǎn)j與參考中點(diǎn)i的距離，di表示參考中點(diǎn)i的實(shí)際密度值。傳感器節(jié)點(diǎn)獲得密度信息的整個過程與路由過程互不干擾，并且對密度信息進(jìn)行周期性采集，因此可以很好適應(yīng)動態(tài)網(wǎng)絡(luò)環(huán)境。

2.2基于節(jié)點(diǎn)維度密度加權(quán)的貪婪路由算法

獲取傳感器節(jié)點(diǎn)的各維度密度信息后，DDRS算法從若干個更加靠近目的節(jié)點(diǎn)的鄰居中，以一定的概率選擇下一跳，概率的大小由下一跳及節(jié)點(diǎn)的權(quán)重決定。DDRS算法將各維度節(jié)點(diǎn)密度納入權(quán)重的考察范圍，處于節(jié)點(diǎn)密度較大位置的節(jié)點(diǎn)，被選擇為下一跳節(jié)點(diǎn)（圖5）。圖5（b）是圖5（a）所示網(wǎng)絡(luò)y軸向的密度分布曲線。對于a和b兩個候選節(jié)點(diǎn)，從圖像中可以清楚地看出節(jié)點(diǎn)的密度情況及變化率。為了避免進(jìn)入路由空洞，處于節(jié)點(diǎn)密度較大位置的節(jié)點(diǎn)，更適合被選擇為下一跳節(jié)點(diǎn)（圖5（b）所示）。對于n個候選節(jié)點(diǎn)，候選節(jié)點(diǎn)i的權(quán)值wi計算公式如下：

其中m指候選節(jié)點(diǎn)i的某一維度，dl是節(jié)點(diǎn)i在m維度上的節(jié)點(diǎn)密度值，disc，des是m維度上，當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離，disi，des是m維度上，候選節(jié)點(diǎn)i到目的節(jié)點(diǎn)的距離。如圖5（a）所示，DDRS算法著重考量了以候選節(jié)點(diǎn)為中心的正方形（三維環(huán)境下則為正方體）區(qū)域內(nèi)的密度情況，能夠很大程度上避免路由空洞的問題。

圖5　DDRS算法

通過各維度的密度信息，節(jié)點(diǎn)無需建立拓?fù)浣Y(jié)構(gòu)，只需將各維度的密度信息加以考量，能夠直接預(yù)知未來路徑上的路由空洞，從而盡量規(guī)避局部最優(yōu)的問題。另外，利用T-LEACH算法實(shí)現(xiàn)周期性的密度信息采集，使得DDRS算法能夠很好的適應(yīng)動態(tài)的網(wǎng)絡(luò)環(huán)境。

2.3路由空洞恢復(fù)算法

DDRS算法可以盡量避免路由空洞的出現(xiàn)，一旦貪婪算法失效，啟動DDRS-R的恢復(fù)算法。DDRS-R恢復(fù)算法利用各維度節(jié)點(diǎn)密度函數(shù)，不僅提供逃逸空洞的方案，同時修正了路由，避免再次陷入路由空洞達(dá)到均衡消耗網(wǎng)絡(luò)能量，提高網(wǎng)絡(luò)健壯性的目的。

如圖6（a）所示，其中黑色節(jié)點(diǎn)h是位于平面α之上的節(jié)點(diǎn)，s為目的節(jié)點(diǎn)。在y軸向上，平面α以上為低密度區(qū)域。當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)h陷入路由空洞時，節(jié)點(diǎn)h首先獲得當(dāng)前位置處，各維度上的密度分布值dl，其中密度值最小的維度稱為劣質(zhì)維，即圖中y維度，密度值較大的維度稱為優(yōu)質(zhì)維，即圖中x和z維度。在之后的恢復(fù)算法中，DDRS-R算法將忽略劣質(zhì)維。

圖6　DDRS-R算法優(yōu)質(zhì)維映射示意圖

對于恢復(fù)過程的轉(zhuǎn)發(fā)節(jié)點(diǎn)（圖中h），首先將鄰居節(jié)點(diǎn)映射到優(yōu)質(zhì)維度上（圖中j，k），接下來通過計算所有鄰居節(jié)點(diǎn)的權(quán)值，來決定下一跳，權(quán)值的計算公式如下：

其中disc，s為在剩余優(yōu)質(zhì)維度上，當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離，disi，s表示在剩余優(yōu)質(zhì)維度上，候選節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離。dp表示候選節(jié)點(diǎn)劣質(zhì)維度上的密度值。dp值越大，說明經(jīng)由該節(jié)點(diǎn)，未來的路由在劣質(zhì)維上將會有所改善。因此數(shù)據(jù)分組就能夠迅速逃逸空洞，進(jìn)入高密度區(qū)域。

DDRS-R算法并不是在逃逸路由空洞時，立即停止恢復(fù)算法并轉(zhuǎn)入貪婪算法，而是在劣質(zhì)維密度dp大于閾值Td（根據(jù)網(wǎng)絡(luò)情況設(shè)置，一般設(shè)為1.2倍的初始dp）時，若當(dāng)前節(jié)點(diǎn)已經(jīng)逃逸路由空洞，表明此時分組已經(jīng)處于高密度區(qū)域，具備產(chǎn)生高質(zhì)量路由的條件，可以進(jìn)入貪婪路由過程。如果仍然沒有逃逸出空洞，那么將T值設(shè)置為1.2T，重復(fù)恢復(fù)過程。

3　仿真實(shí)驗(yàn)與分析

本文主要從基于拓?fù)浣Y(jié)構(gòu)的路由協(xié)議和基于地理位置的路由協(xié)議兩個方向進(jìn)行研究，提出一個結(jié)合二者優(yōu)勢的混合型路由協(xié)議。針對三維空間內(nèi)移動傳感器網(wǎng)絡(luò)應(yīng)用和路由空洞問題，在丟包率，節(jié)點(diǎn)能量消耗和網(wǎng)絡(luò)整體生存期等方面進(jìn)行了改進(jìn)，本文實(shí)驗(yàn)也從上述3個方向，將現(xiàn)有的路由協(xié)議與本文提出的兩種路由協(xié)議進(jìn)行了對比和分析。本文提出的路由協(xié)議所進(jìn)行的測試和對比實(shí)驗(yàn)均在課題組獨(dú)立開發(fā)的WSN路由協(xié)議三維空間仿真平臺上進(jìn)行。

3.1WSN-TDRS仿真實(shí)驗(yàn)平臺介紹

課題組結(jié)合仿真平臺設(shè)計思想，根據(jù)三維環(huán)境和本文提出的路由方案的需求，借助Unity3D引擎提供的編程接口和可視化工具，設(shè)計了一款三維空間路由協(xié)議仿真平臺WSN-TDRS。在仿真平臺中，能夠顯示網(wǎng)絡(luò)整體信息，節(jié)點(diǎn)信息，節(jié)點(diǎn)行為，節(jié)點(diǎn)通信，實(shí)現(xiàn)路由控制、拓?fù)淇刂频裙δ?，WSN-TDRS仿真實(shí)驗(yàn)平臺主界面如圖7所示。左側(cè)邊欄顯示網(wǎng)絡(luò)整體信息相關(guān)的選項(xiàng)，操作和信息，包括運(yùn)行日志，丟包率曲線，能量消耗曲線（整體）等；右側(cè)邊欄顯示了不同階段選中節(jié)點(diǎn)的信息，底邊欄顯示了用戶視角信息等雜項(xiàng)與實(shí)驗(yàn)操控按鈕。

圖7　WSN-TDRS仿真實(shí)驗(yàn)平臺主界面

3.2實(shí)驗(yàn)結(jié)果及分析

WSN-TDRS仿真實(shí)驗(yàn)平臺假定網(wǎng)絡(luò)中各個傳感器節(jié)點(diǎn)相同。設(shè)置網(wǎng)絡(luò)規(guī)模為200×200×200，單個節(jié)點(diǎn)初始能量值為999 J，采樣時間間隔為0.5 s，傳感器節(jié)點(diǎn)個數(shù)分別設(shè)置為100，200，300，400，800個。

在三維空間的網(wǎng)絡(luò)應(yīng)用上，我們將T-LEACH協(xié)議與LEACH協(xié)議和CBR-Mobile協(xié)議進(jìn)行對比。在本次實(shí)驗(yàn)中，交付率被定義為數(shù)據(jù)包和數(shù)據(jù)請求包之比。由圖9可以看出，得益于簇頭節(jié)點(diǎn)的反應(yīng)機(jī)制，T-LEACH協(xié)議減少了簇頭節(jié)點(diǎn)移動造成的數(shù)據(jù)丟失，運(yùn)行時間越長表現(xiàn)越穩(wěn)定。并且，T-LEACH只是改變了LEACH算法對節(jié)點(diǎn)移動的控制，并未增加整體算法復(fù)雜度。如圖10所示，在能量消耗方面，CBR和LEACH協(xié)議均因?yàn)槿鄙倩騼H提供部分移動反應(yīng)機(jī)制，造成能量消耗波動劇烈，T-LEACH算法利用多跳傳輸機(jī)制，進(jìn)一步降低了非簇頭節(jié)點(diǎn)的能量消耗，具有能耗穩(wěn)定和低消耗的良好表現(xiàn)。有效證明了在大型的、拓?fù)浣Y(jié)構(gòu)動態(tài)的、節(jié)點(diǎn)密度分布不均的移動傳感器網(wǎng)絡(luò)中，T-LEACH協(xié)議能夠有效建立和維護(hù)其多級拓?fù)浣Y(jié)構(gòu)。

圖8　算法流程圖

圖9　數(shù)據(jù)包交付率對比

圖10　節(jié)點(diǎn)平均能量消耗對比

在路由空洞的逃逸和恢復(fù)上，我們將DDRS優(yōu)化方案與LEACH的層次路由方案、GREEDY路由進(jìn)行對比。從圖11、圖12可以看出，得益于DDRS協(xié)議令數(shù)據(jù)包在高密度區(qū)域轉(zhuǎn)發(fā)的原則，有效改善了單跳的能量消耗，同時令數(shù)據(jù)包避開了大部分路由空洞，減少了長距離傳輸?shù)膿p耗，達(dá)到了均衡消耗網(wǎng)絡(luò)能量的目的，延長了網(wǎng)絡(luò)生存期。在網(wǎng)絡(luò)運(yùn)行的中前期，DDRS算法在能量消耗方面接近甚至優(yōu)于層次路由。

圖11　單跳平均能量消耗

圖12　網(wǎng)絡(luò)生存期比較

丟包率方面（圖13），DDRS有效減少了局部最優(yōu)問題，保證了較高的交付率，相較于LEACH的層次路由方案，DDRS不存在周期性拓?fù)涓略斐傻耐ㄐ胖袛喱F(xiàn)象，進(jìn)一步降低了丟包率。由于DDRS計算下一跳過程只涉及優(yōu)質(zhì)維內(nèi)歐式距離的計算，保證了較低的算法復(fù)雜度。

圖13　丟包率比較

從仿真實(shí)驗(yàn)結(jié)果來看，DDRS路由協(xié)議方案能夠有效提升網(wǎng)絡(luò)整體生存期，降低丟包率。在節(jié)點(diǎn)密度分布不均勻的環(huán)境下，有效保存空洞周圍節(jié)點(diǎn)的能量，防止網(wǎng)絡(luò)連通性進(jìn)一步的惡化。同時，因?yàn)門-LEACH周期更新拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)節(jié)點(diǎn)能夠在不中斷路由的情況下，周期性更新節(jié)點(diǎn)密度信息，更好的適應(yīng)拓?fù)渥兓?，同時DDRS路由方案還為數(shù)據(jù)融合等技術(shù)提供了基礎(chǔ)，能夠很好地適應(yīng)多種應(yīng)用場景的需求。

4　總結(jié)與展望

本文將拓?fù)浣Y(jié)構(gòu)和地理結(jié)構(gòu)的路由協(xié)議相結(jié)合，提出了基于節(jié)點(diǎn)密度加權(quán)的T-LEACH三維動態(tài)路由協(xié)議，使用T-LEACH算法獲得全局節(jié)點(diǎn)密度信息，DDRS算法預(yù)知路由空洞和使用DDRS-R的恢復(fù)算法逃逸空洞和修正路由，有效地實(shí)現(xiàn)規(guī)避局部最優(yōu)問題和迅速逃逸路由空洞的目標(biāo)，提高了網(wǎng)絡(luò)整體的健壯性和生存時間。最后，本文在項(xiàng)目組設(shè)計的三維動態(tài)無線傳感器網(wǎng)絡(luò)路由協(xié)議仿真平臺WSN-TDRS上對本文提出的路由協(xié)議和方案與現(xiàn)有的一些研究成果進(jìn)行了對比，實(shí)驗(yàn)證明，本文提出的協(xié)議在能量消耗，網(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)整體生存時間等方面，均有良好的表現(xiàn)，優(yōu)于現(xiàn)有的多種協(xié)議，具有良好的應(yīng)用前景。以后，課題組將繼續(xù)研究繼續(xù)降低路由協(xié)議的節(jié)點(diǎn)能量消耗問題，各類路由協(xié)議的優(yōu)勢聯(lián)合問題，并思考如何把時下熱門的技術(shù)如數(shù)據(jù)融合、節(jié)點(diǎn)定位等技術(shù)與路由協(xié)議設(shè)計相結(jié)合。

參考文獻(xiàn)：

［1］Narayanaswamy S，Kawadia V，Sreenivas R S，et al.Power Control in Ad-hoc Networks：Theory，Architecture，Algorithm and Imple?mentation of the COMPOW Protocol［C］//European Wireless Conf，F(xiàn)lorence，Italy，2002：156-152

［2］Flury R，Wattenhofer R R.Randomized 3D Geographic Routing ［C］//The 27th Conference on Computer Communications（INFO?COM），Phoenix，USA，2008：13-18.

［3］Karp B，Kung H T.GPSR：Greedy Perimeter Stateless Routing for Wireless Networks［C］//The sixth Annual ACM/IEEE Int Conf on Mobile Computing and Networking（MobiCom 2000），Boston，USA.2000：243-254.

［4］Basagni S，Chlamtac I，Syrotiuk Y R，et al.A Distance Routing Ef?fect Algorithm for Mobility（DREAM）［C］//The 4th Annual ACM/IEEE Int Conf on Mobile Computing and Networking，Dallas Tex?as，USA，1998：76-84.

［5］Liao W H，Sheu J P，Tseng Y C.GRID：A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks［J］.Telecommuni?cation Systems，2001，18（1）：37-60.

［6］Abdallah A E，F(xiàn)evens T，Opatrny J.Power-Aware 3D Position-Based Routing Algorithms for Ad Hoc Networks［C］//IEEE Inter?national Conference on Communications 2007- ICC- 2007，Glasgow，UK，2007：3130-3135.

［7］Bose P，Morin P，Stojmenovic I，et al.Routing with Guaranteed Delivery in Ad Hoc Wireless Networks［J］.Wireless Networks Journal，2001，7（6）：609-616.

［8］Heinzelman W R，Chandrakasan A，Balakrishnan H.An Applica?tion-Specific Protocol Architecture for Wireless Microsensor Net?works［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

［9］Fan Xiangning，Song Yulin.Improvement on LEACH Protocol of Wireless Sensor Network［C］//International Conference on Sensor Technologies and Applications，Valencia，Spain，2007：260-264.

［10］Yang Jing，Li Zetao，Lin Yi.An Improved Routing Algorithm Based on LEACH for Wireless Sensor Networks［C］//The 25th Chinese Control and Decision Conference（CCDC），Guiyang，Chi?na，2013：3716-3720.

［11］Do-Seong Kim，Yeong-Jee Chung.Self-Organization Routing Pro?tocol Supporting Mobile Nodes for Wireless Sensor Network［C］//First International Multi-Symposiums on Computer and Computa?tional Sciences（IMSCCS），Hanzhou，China，2006：622-626.

［12］Awwad S A B，Ng C K，Noordin N K，et al.Cluster Based Routing Protocol for Mobile Nodes in Wireless Sensor Network［J］.Inter?national Symposium on Collaborative Technologies and Systems，2009：233-241.

［13］陳炳才，么華卓，楊明川，等.一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議［J］.傳感技術(shù)學(xué)報，2014，27（3）：373-377.

［14］馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究［J］.傳感技術(shù)學(xué)報，2013（8）：1147-1151.

［15］Qi Zhang，Min Yu.A Routing Protocol for Mobile Sensor Network Based on LEACH［C］//The 10th International Conference on Wireless Communications，Networking and Mobile Computing （WICOM 2014），2014：473-477.

［16］Finn G G.Routing and Addressing Problems in Large Metropoli?tan-Scale Internetworks［C］//ISI Research Report.1987.

［17］Kranakis B，Singh H，Urrutia J.Compass Routing on Geometric Networks［C］//The 11th Canadian Conference on Computational Geometry（CCCG’99），Vancouver，Canada，1999：51-54.

［18］Ramanathan R，Rosales- Hain R.Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment［C］//INFO?COM 2000.Nineteenth Annual Joint Conference of the IEEE Com?puter and Communications Societies.Proceedings，Tel-Aviv，Isra?el，2000：404-413.

［19］Wang Zhixiao，Zhang Deyun，Alfandi O，et al.Efficient Geographi?cal 3D Routing for Wireless Sensor Networks in Smart Spaces ［C］//2011 Baltic Congress on Future Internet and Communica?tions（BCFIC Riga 2011），Riga，Latvia，2011：168-172.

［20］Ahmad A，Latif K，Javaid N，et al.Density Controlled Divide-and-Rule Scheme for Energy Efficient Routing in Wireless Sensor Net?works［C］//CVPR 2013：26th IEEE Conference on Computer Vi?sion and Pattern Recognition，Portland，USA，2013：1-4.

［21］Siqueira I G，F(xiàn)igueiredo，et al.An Integrated Approach for Densi?ty Control and Routing in Wireless Sensor Networks［C］//20th IEEE International Parallel &Distributed Processing Symposium，Rhodes Island，Greece，2006：10.

余　敏（1964-），女，通訊作者，江西師范大學(xué)計算機(jī)信息工程學(xué)院教授、碩士生導(dǎo)師。主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、分布式系統(tǒng)與移動計算，myu821@ 163.com；

張　琦（1991-），男，江西師范大學(xué)軟件學(xué)院碩士研究生，主要研究方向?yàn)闊o線傳感網(wǎng)絡(luò)；

李雅晴（1992-），女，江西師范大學(xué)軟件學(xué)院碩士研究生，主要研究方向?yàn)闊o線傳感網(wǎng)絡(luò)；

唐　瑞（1991-），男，江西師范大學(xué)軟件學(xué)院碩士研究生；主要研究方向?yàn)闊o線傳感網(wǎng)絡(luò)，室內(nèi)定位。

Research on 3D Dynamic Routing Protocol Based on T-LEACH Using Node Weighting Density*

YU Min1*，LI YaQing2，ZHANG Qi2，TANG Rui2
（1.School of Computer Science，Jiangxi Normal University，Nanchang 330022，China；2.School of Software，Jiangxi Normal University，Nanchang 330022，China）

Abstract：With the increasing requirement of 3D dynamic environment applications，how to design an efficient and reliable protocal in the dynamic 3D environment is becoming a reaseach hotspot.The existing 3D routing protocol，with missing consideration of node mobility and environmental factors，is just auxiliary means for the 2D static proto?col.In this paper，we proposed a node density based T-LEACH 3D dynamic routing protocol which combined the to?pology protocol and routing protocol.We used the T-LEACH algorithm to obtain the global node density informa?tion，used the DDRS algorithm to predict routing hole and used recovery algorithm DDRS-R to escape holes and modify the routing，and finally we successfully avoided local optimization problem and rapid escape from the route hole problem，which greatly improved robustness and overall survival time of the network.At the same time，we did experiments and contrast analysis on a wireless sensor network designed by our research group，which proved that the proposed routing protocol was superior to the existing protocol in many ways，such as energy consumption，net?work lifetime and data delivery ratio and so on，and which also proved that the node density based T-LEACH 3D dy?namic routing protocol will have a good application prospect.

Key words：WSN；3D dynamic；routing protocol；energy consumption；routing hole；node density

doi：EEACC：6210L；6210Q10.3969/j.issn.1004-1699.2016.02.021

收稿日期：2015-07-20修改日期：2015-11-14

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：1004-1699（2016）02-0278-07

項(xiàng)目來源：國際科技合作項(xiàng)目（14-35）；國家自然科學(xué)基金項(xiàng)目（41164001）