低開銷低延遲WSN多費馬點鏈多地域群播算法*

蘇 暢，臧李立，尙鳳軍，趙 曜

(1.重慶郵電大學(xué)計算機科學(xué)與技術(shù)學(xué)院，重慶400065;2.美國康奈爾大學(xué)計算機系，紐約州伊薩卡市，美國)

隨著無線傳感器網(wǎng)絡(luò)［1］技術(shù)的進一步發(fā)展，其應(yīng)用領(lǐng)域越來越廣。傳感器節(jié)點的能量受限以及對數(shù)據(jù)實時性的高要求使得低能耗和低延遲成為無線傳感器網(wǎng)絡(luò)通信協(xié)議的重要衡量指標(biāo)?；诘乩砦恢玫穆酚蓞f(xié)議因其對網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息的極低需求使其算法簡單高效而且開銷小，其路由發(fā)現(xiàn)和數(shù)據(jù)傳輸過程依靠節(jié)點自身及其鄰節(jié)點的位置信息(通過 GPS 等定位設(shè)備［2－6］獲取)。

無線傳感器網(wǎng)絡(luò)極強的應(yīng)用相關(guān)性使基于地理位置路由的地域群播(Geocasting:即源節(jié)點向WSN中特定地理位置區(qū)域內(nèi)的所有節(jié)點發(fā)送信息)應(yīng)運而生。其應(yīng)用廣泛，如:森林管理中心需要向森林中高火險區(qū)域內(nèi)所有節(jié)點發(fā)送命令，使區(qū)域內(nèi)節(jié)點及時監(jiān)測并匯報其周圍溫度狀況;交通控制中指揮中心要向交通擁擠地區(qū)所有節(jié)點及時發(fā)出控制命令。

地域群播通過兩個過程完成傳輸:源節(jié)點與目標(biāo)區(qū)域的通信及目標(biāo)區(qū)域內(nèi)信息的傳輸。網(wǎng)絡(luò)拓撲的不規(guī)則性，尤其是路由空洞的存在，使信息如何低能耗、高可靠性、低延遲地傳輸?shù)侥繕?biāo)區(qū)域成為目前研究的熱點。Brad Karp等提出的GPSR算法［7］，以貪心算法為基礎(chǔ)，結(jié)合面路由的方法，成功解決了貪心算法因遇到路由空洞而導(dǎo)致算法失敗的問題;胥楚貴等提出的最佳匹配節(jié)點策略［8］通過選取距離由空洞邊界所圍成多邊形的最小覆蓋圓圓心最近的非活躍節(jié)點來替換失敗節(jié)點的方式修復(fù)覆蓋空洞;F.Yu 提出的彈性路由(Elastic Routing)算法［9］通過路由路徑的反方向更新Sink節(jié)點的位置信息，大大降低了能量開銷和傳輸延遲;針對密集型網(wǎng)絡(luò)的目標(biāo)區(qū)域內(nèi)信息的傳輸多采用簡單泛洪的方式，如ALURP［10］、LBM［11］等算法。而實際中網(wǎng)絡(luò)的密度狀況是不可知的，稀疏網(wǎng)絡(luò)嚴重降低了網(wǎng)絡(luò)的連通度［12］，簡單泛洪無法保證區(qū)域內(nèi)所有節(jié)點收到信息，因此 Karim Seada等提出了 GFPG［13］算法。

多目標(biāo)區(qū)域地域群播的目標(biāo)區(qū)域數(shù)量以及位置均未知，這種復(fù)雜性注定了單目標(biāo)區(qū)域算法無法滿足其需求。多路徑單地域群播算法［14］中源節(jié)點依次將信息傳輸?shù)矫總€目標(biāo)區(qū)域內(nèi)，能量開銷極大;簡單目標(biāo)區(qū)域鏈算法［14］通過鏈接所有目標(biāo)區(qū)域減少了源節(jié)點的能量開銷，但整個網(wǎng)絡(luò)的能量開銷依然很大;Lee Sung-Hee等提出的單費馬點鏈算法［12］將所有目標(biāo)區(qū)域與源節(jié)點連接到一條費馬點鏈上，如圖1(a)所示，雖然可以降低整個網(wǎng)絡(luò)的能量消耗，但是其健壯性和網(wǎng)絡(luò)傳輸延遲存在著缺陷。

圖1 多地域群播算法

本文提出一種基于多費馬點鏈低能耗低延遲多地域群播算法，在保持較低能量消耗的基礎(chǔ)上，降低了傳輸延遲，并在NS2環(huán)境下對LLA算法和現(xiàn)有的算法進行仿真分析。

1 多費馬點鏈算法

多費馬點鏈算法包括兩部分:第1是基于源節(jié)點傳輸區(qū)域的網(wǎng)格劃分以及網(wǎng)格中簇頭的選擇，第2是通過引入四邊形費馬點解決建立三角形費馬點失敗的問題，如圖1(b)所示。

1.1 網(wǎng)格劃分及簇頭選擇

假設(shè)數(shù)據(jù)源節(jié)點A的位置坐標(biāo)為(x0，y0)，則以該節(jié)點為中心建立如下坐標(biāo)系:以直線y=y0為該坐標(biāo)系的x軸，以直線x=x0為該坐標(biāo)系的y軸。此坐標(biāo)系將網(wǎng)絡(luò)分成四網(wǎng)格。當(dāng)多數(shù)目標(biāo)區(qū)域集中于某一網(wǎng)格中時，按如下規(guī)則劃分:假設(shè)網(wǎng)絡(luò)中目標(biāo)區(qū)域數(shù)量為n，網(wǎng)格劃分的層次為N

直到經(jīng)過N次劃分的網(wǎng)格中的目標(biāo)區(qū)域的數(shù)量小于等于n/2N或網(wǎng)格中的目標(biāo)區(qū)域數(shù)量均≤4。

網(wǎng)格中選取距離源節(jié)點最近的目標(biāo)區(qū)域的中心點作為該網(wǎng)格的簇頭，不同源節(jié)點對于不同的目標(biāo)區(qū)域產(chǎn)生不同的簇頭節(jié)點，避免了固定或單一簇頭導(dǎo)致其消耗能量過快而死亡。

下面對基于源節(jié)點傳輸區(qū)域的網(wǎng)格劃分及網(wǎng)格中選取距離源節(jié)點最近的目標(biāo)區(qū)域作為簇頭的方法進行性能分析。

假設(shè)有n個目標(biāo)區(qū)域，費馬點之間的平均傳輸延遲為t，費馬點到其相鄰節(jié)點之間的傳輸延遲平均為 T，則:

?delay(n)=nt+T，(delay(n)為第n個節(jié)點接收到數(shù)據(jù)包時的延遲時間)(avg(delay(n))為n個目標(biāo)區(qū)域接收到數(shù)據(jù)包時的平均延遲時間)。分成網(wǎng)格后，每個網(wǎng)格有n/4個目標(biāo)區(qū)域，由于數(shù)據(jù)在網(wǎng)格內(nèi)同時通信，其平均延遲可以認為等同于單一網(wǎng)格的延遲，考慮上面的假設(shè)，則:

通過以上分析在傳輸延遲方面該方法優(yōu)于單費馬點鏈算法。源節(jié)點將信息傳送到簇頭節(jié)點后，由簇頭節(jié)點通過費馬點鏈轉(zhuǎn)發(fā)到相應(yīng)的目標(biāo)區(qū)域內(nèi)。

1.2 網(wǎng)格費馬點鏈

網(wǎng)絡(luò)中目標(biāo)區(qū)域需要向其感興趣的節(jié)點發(fā)送位置信息及數(shù)據(jù)收集請求，源節(jié)點則需要記錄向其發(fā)送請求的所有目標(biāo)區(qū)域的位置信息以便計算費馬點鏈。

三角形中一定存在費馬點，如圖2所示，尋找△ABC費馬點的過程如下。

圖2 三角形費馬點

在△APC中，將∠PAC按逆時針方向旋轉(zhuǎn)60°，點P和點C分別落于點P1和C'，的最小值即的最小值，即C'到點B的直線距離

這時點P和P1都在線段C'B上，同理我們可得點P必在線段B'A和線段A'C上，三條線段的交點即是三角形的費馬點。因此只需找到A'、B'和C'中的任意兩點就可以找到該三角形的費馬點，如圖2所示。

單費馬點鏈算法存在著明顯的缺陷:局部能量開銷大、極大的傳輸延遲、可靠性差。當(dāng)費馬點存在于三角形外部時(即三角形任意一內(nèi)角大于等于120°)，按照順序往下繼續(xù)尋找目標(biāo)區(qū)域，然后以這三個目標(biāo)區(qū)域和簇頭組成的四邊形為基礎(chǔ)，尋找四邊形的費馬點，找到該費馬點后，繼續(xù)尋找接下來的三角形的費馬點，直到所有的目標(biāo)區(qū)域都連接到費馬點鏈上。如圖3所示，有兩種情況:凸四邊形(如圖3(a)所示)和凹四邊形(如圖3(b)所示)。兩種情況下∠ABC＞120°，因此選取第四個目標(biāo)區(qū)域D形成四邊形，計算出四邊形的費馬點后再以該費馬點、簇頭A和下一個目標(biāo)區(qū)域的中心點E形成的三角形繼續(xù)尋找費馬點。

圖3 四邊形費馬點鏈

定理1 凸四邊形費馬點的位置為對角線的交點。

證明:假設(shè)凸?ABCD中，對角線AC、BD交于點P，如圖4所示。

圖4 四邊形費馬點

定理2 內(nèi)含三角形中內(nèi)三角形的兩邊之和小于外三角形的兩邊之和。

定理3 凹四邊形的費馬點在凹點上，即四邊形內(nèi)角大于180°的頂點上。

證明:如圖5(b)和5(c)兩種情況所示:F點均為四邊形內(nèi)部異于凹點的任意一點，在圖5(b)中，△CDB是△CFB的內(nèi)含三角形，由定理2可知:

在圖5(c)中，△ADB是△AFB的內(nèi)含三角形，

由上證明可得出結(jié)論:凹四邊形的費馬點在其凹點上。

圖5 四邊形費馬點

通過引入四邊形費馬點保證了所建費馬點鏈的連續(xù)性，然后源節(jié)點將信息沿著費馬點鏈傳送到所有的目標(biāo)區(qū)域，到達目標(biāo)區(qū)域的信息在該區(qū)域內(nèi)泛洪，完成地域群播路由過程。該方法能夠減少單個網(wǎng)格內(nèi)節(jié)點的能量消耗，降低整個網(wǎng)絡(luò)的能量開銷。

2 仿真結(jié)果與分析

2.1 仿真環(huán)境

我們使用的仿真工具是NS2.30，MAC層采用的是802.11協(xié)議。我們構(gòu)建了如下的無線傳感器網(wǎng)絡(luò):400個無線傳感器節(jié)點隨機地分布在2 000 m×2 000 m的正方形區(qū)域內(nèi)，地域群播區(qū)域為半徑250 m的圓形區(qū)域。整個仿真過程中，對每種算法我們分別設(shè)定并隨機選取網(wǎng)絡(luò)中的地域群播區(qū)域的數(shù)量為2、4、6、8、10、12、14、16 個。

仿真中我們采用三個指標(biāo)來衡量該算法的性能:包的成功傳輸比率、端到端的平均延遲和數(shù)據(jù)傳輸?shù)侥繕?biāo)區(qū)域內(nèi)這一過程中的平均能量消耗(下文簡稱為平均傳輸能量消耗)。包的成功傳輸比率定義為網(wǎng)絡(luò)中所有的目標(biāo)節(jié)點成功接受到數(shù)據(jù)包的總量與網(wǎng)絡(luò)中所有數(shù)據(jù)源節(jié)點發(fā)送的數(shù)據(jù)包的總量的比值;端到端的平均延遲定義為網(wǎng)絡(luò)中所有數(shù)據(jù)包的延遲的總和與網(wǎng)絡(luò)中所有數(shù)據(jù)包總量的比值;平均傳輸能量消耗定義為網(wǎng)絡(luò)中所有傳輸?shù)臄?shù)據(jù)包的總字節(jié)數(shù)與網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包的總量和數(shù)據(jù)包成功傳輸比率的乘積的比值。

2.2 仿真結(jié)果和分析

圖6展示了數(shù)據(jù)包的成功傳輸比率。從圖中可以看出單費馬點鏈算法、多路徑單地域群播算法和本文中提出的多費馬點鏈算法的數(shù)據(jù)包的成功傳輸比率在95.5% ～97%之間波動，多路徑單地域群播算法采用的是每次只向一個區(qū)域發(fā)送數(shù)據(jù)，而基于費馬點鏈的兩種算法的第1階段都是采用GPSR算法，可以很好的解決導(dǎo)致成功傳輸比率下降的主要因素——路由空洞，并且對鏈路進行了優(yōu)化。當(dāng)目標(biāo)區(qū)域數(shù)量大于6個的時候，簡單目標(biāo)區(qū)域鏈算法的成功傳輸比率呈現(xiàn)線性下降趨勢，當(dāng)區(qū)域數(shù)量為12時，成功傳輸比率已降到95%，數(shù)量為16時降到93.5%，因為簡單目標(biāo)區(qū)域鏈算法存在兩個方面的缺陷:無法解決路由空洞并且路由路徑最長。通過以上分析，多費馬點鏈算法可以有效地保證將數(shù)據(jù)傳輸?shù)侥繕?biāo)區(qū)域，其數(shù)據(jù)成功傳輸比率高且穩(wěn)定。

圖6 數(shù)據(jù)包成功傳輸比率

圖7 端到端的平均延遲

圖7展示了端到端的平均延遲。簡單區(qū)域鏈算法的延遲明顯高于其它3種算法，當(dāng)區(qū)域數(shù)量為16時，平均延遲為150 ms，是其它3種算法的300% ～500%;而單費馬點鏈算法的平均延遲高于多費馬點鏈算法，目標(biāo)區(qū)域從4變化到16時，其延遲是多費馬點鏈算法的200%，因為該算法單一的傳輸鏈路導(dǎo)致其傳輸路徑過長;目標(biāo)區(qū)域大于10的時候，多路徑單地域群播算法的延遲比多費馬點鏈算法高出30% ～40%，因為其延遲主要由兩部分組成:數(shù)據(jù)傳到第1個和最后1個目標(biāo)區(qū)域的時間和事件在隊列中的等候時間，而多費馬點鏈算法是在4個網(wǎng)格同時通信，因此目標(biāo)區(qū)域數(shù)量對其的影響僅為其它算法的1/4。通過以上分析，多費馬點鏈算法在平均延遲上要明顯好于其它3種算法。

圖8展示了網(wǎng)絡(luò)中的平均傳輸開銷。當(dāng)區(qū)域數(shù)量為4的時候，4種算法的平均開銷基本相同，為7 kbit;區(qū)域數(shù)量大于6時，簡單區(qū)域鏈算法和多路徑單地域群播算法的開銷，明顯高于基于費馬點鏈的算法，目標(biāo)區(qū)域數(shù)量從10開始一直到16，其開銷比其它基于費馬點鏈的算法平均高出20%～30%。因為基于費馬點鏈的兩種算法對傳輸鏈路進行了優(yōu)化，鏈路數(shù)要比以上兩種算法少。通過以上分析，單費馬點鏈算法和多費馬點鏈算法在平均傳輸開銷上明顯低于簡單區(qū)域鏈算法和多路徑單地域群播算法。

圖8 平均傳輸開銷

3 結(jié)束語

多地域群播的目標(biāo)區(qū)域數(shù)量和位置均未知，這種復(fù)雜性導(dǎo)致目前無線傳感器網(wǎng)絡(luò)多地域群播算法都無法做到能量和傳輸延遲的平衡。本文提出了一種新的基于多目標(biāo)區(qū)域的多費馬點鏈算法，主要思想是以源節(jié)點為中心將自身傳輸區(qū)域分為4個網(wǎng)格，網(wǎng)格中選取距離源節(jié)點最近的目標(biāo)區(qū)域的中心點為簇頭，并以該簇頭與目標(biāo)區(qū)域形成三角形與四邊形相結(jié)合的費馬點鏈。通過仿真實驗表明多費馬點鏈算法在保持較低能量消耗的同時大大降低了傳輸延遲。

［1］ Akyildiz I F，Su W L，Sankarasubramaniam Y.A Survey on Sensor Networks［J］.Communications Magazine，2002，40(8):102－114.

［2］ Li J Y，JAnnotti J，Couto D，et al.A Scalable Location Service for Geographic Ad Hoc Routing［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，New York，2000:120－130.

［3］ Xue Y，LI B C，Nahrstedt K.A Scalable Location Management Scheme in Mobile Ad-Hoc Networks［C］//Proc.LCN 2001.26th Annual IEEE Conference，Tampa，2001:102－111.

［4］ He T，Huang C，Blum B，et al.Rangefree Localization Schemes for Large Scale Sensor Networks［C］//Proc.of the 9th Annual International Conference on Mobile Computing and Networking，2003:81－95.

［5］ Seada K，Helmy A.Rendezvous Regions:A Scalable Architecture for Service Location and Data-Centric Storage in Large-Scale Wireless Networks［C］//Parallel and Distributed Processing Symposium，Proc.18th International，2004:218－225.

［6］ Stojmenovic I，Liu D D，Jia X H.A Scalable Quorum-Based Location Service in Ad Hoc and Sensor Networks［C］//Mobile Adhoc and Sensor Systems，Vancouver，2006:489－492.

［7］ Karp B，Kung H T.GPSR:Greedy Perimeter Stateless Routing for wireless Networks［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，Boston，2000:243－254.

［8］ 胥楚貴，鄧曉衡，鄒豪杰.無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)策略［J］.傳感技術(shù)學(xué)報，2010，23(2):256－259.

［9］ Yu F，Park S，Lee E，et al.Elastic Routing:A Novel Geographic Routing for Mobile Sinks in Wireless Sensor Networks［C］//IET The Institution of Engineering and Technology，2010，4(6):716－727.

［10］ Wang G，Wang T，Jia W，et al:Adaptive Location Updates for Mobile Sinks in Wireless Sensor Networks［J］.The Journal of supercomputing，2009，47(2):127－145.

［11］ Ko Y B，Vaidya N H.Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks［J］.Mobile Networks and Applications，2002，7(6):471－480.

［12］ Seada K，Helmy A.Efficient Geocasting with Perfect Delivery in Wireless Networks［C］//Proceedings of IEEE WCNC 2004，Atlanta，2004，4:2551－2556.

［13］張強，孫雨耕，劉麗萍.邊界節(jié)點對無線傳感器網(wǎng)絡(luò)連通性的影響［J］.傳感技術(shù)學(xué)報，2011，24(5):737－741.

［14］ Lee S H，Ko Y B.Efficient Geocasting with Multi-Target Regions in Mobile Multi-Hop Wireless Networks［C］//Wireless Networks.2010，16(5):1253－1262.