譚立興，陳光亭，李溢潔，徐冬冬

(杭州電子科技大學運籌與控制研究所，浙江杭州310018)

0 引言

無線傳感器網絡是一種基于無線通信技術的、低功耗的和自組織的網絡，一般由一個或多個基站和大量部署于監(jiān)測區(qū)域、配有各類傳感器的無線網絡節(jié)點構成。WSN具有十分廣闊的應用前景，在軍事國防、工農業(yè)、生物醫(yī)療、環(huán)境監(jiān)測、搶險救災等許多重要領域都有潛在的實用價值，已經引起了許多國家學術界和工業(yè)界的高度重視，被認為是對21世紀產生巨大影響力的技術之一［1］。網絡均衡是一個非常重要的問題，如何根據(jù)無線傳感器網絡的自身特點，設計合適的路由協(xié)議，有效減少網絡能量的消耗和獲得高效的、可靠的傳輸路徑，延長節(jié)點和網絡的壽命，對無線傳感器網絡的發(fā)展具有極其重要的意義。為了提高無線傳感器網絡的性能，提出了許多路由協(xié)議［2-6］，其中包括平面路由協(xié)議與分層路由協(xié)議，這些協(xié)議將各自獨立的節(jié)點組成一個共同完成某個特定任務的高性能網絡結構。本文針對無線傳感器網絡中局部節(jié)點耗能過快問題，以網絡均衡的思想解決WSN路由問題，提出一種低能耗的、帶懲罰函數(shù)的路由協(xié)議。協(xié)議采用平面路由策略，路徑選擇過程中既考慮了路徑的能耗，也引入了懲罰函數(shù)作為路徑選擇的依據(jù)，這樣就使得協(xié)議在保證總能耗比較少的同時又考慮了數(shù)據(jù)傳輸?shù)目煽啃?。實驗表明該算法具有比SPRP等算法具有更好的能量均衡性，從而有效的延長了網絡壽命。

1 WSN選路過程的建模及分析

1.1 一般網絡路由模型

通常用帶權重的連通圖Gwsn=(V，E，ω)表示給定的無線傳感器網絡，其中V是頂點集，E是邊集，ω:E|→R+為E中每條邊所賦的一個權重值。無線傳感器網絡的路由模型就是為了尋找WSN中從所需各個傳感器節(jié)點到基站按某種特定需求的最優(yōu)路徑，如:能量最短路徑、距離最短路徑等等。

1.2 帶懲罰網絡路由模型

為了設計更優(yōu)的無線傳感器網絡路由協(xié)議，定義了一個路由懲罰函數(shù)f。用(Gwsn，twsn，α，f)表示無線傳感器網絡路由模型，其中:

(1)twsn表示無線傳感器網絡的網絡壽命，本文將其定義為從一開始直到第一個傳感器節(jié)點死亡的這段時間;

(2)Gwsn=(V，E，ω)表示給定的無線傳感器網絡，其中V是頂點集，E是邊集，ω:E|→R+為E中每條邊所賦的一個權重值;

(3)α表示懲罰閾值，即重復經過eij∈E的次數(shù)大于αn(其中n表示E的總節(jié)點數(shù))就要受到懲罰;

(4)本文采用的是線性懲罰，即f=kω(其中k為懲罰系數(shù))。

1.3 無線能量模型

無線傳感器的能耗主要包括3個部分:傳感器模塊、處理器模塊和無線通信模塊，其中無線通信模塊是主要的耗能點，本文采用的無線通信模型是文獻6所敘述的自由空間模型，無線通信模塊包括無線發(fā)送模塊、放大模塊和無線接收模塊，當傳輸k bit數(shù)據(jù)時，各個部分的能耗滿足下列關系:

式中，ETx(k，d)表示源節(jié)點發(fā)送k bit數(shù)據(jù)到距離為d的基站的能耗，ERx(k，d)表示節(jié)點接收k bit數(shù)據(jù)的能耗，Eelec=50nJ/bit為傳輸電路或接收電路的能耗，εamp=10pJ/bit/m2為傳輸放大電路的能耗。

2 算法分析與設計

在文獻3提出了基于M2WSN的協(xié)議SPRP用于節(jié)省節(jié)點的能量，SPRP主要分為兩個階段:鄰居發(fā)現(xiàn)和最短路徑的構造。鄰居發(fā)現(xiàn)通過廣播HELLO包來得到F節(jié)點的鄰接矩陣，最短路徑的構造則是利用Floyd算法得到各個所需F節(jié)點到基站的最優(yōu)路徑。假設SPRP調用Floyd算法的F節(jié)點有很多個并且F節(jié)點能量有限，則必然出現(xiàn)所有最短路徑中存在重復出現(xiàn)次數(shù)很高的節(jié)點，此現(xiàn)象表示整個WSN具有很差的網絡均衡性。所以，不妨以犧牲少部分的總耗費能量來換取WSN具有更好的網絡均衡性。本文將給出PSPRP算法的設計細節(jié)，本算法的主要思想是:在無線傳感器網絡中找從源節(jié)點到目的節(jié)點最小耗費能量路徑的同時;也考慮網絡的可靠性問題，即數(shù)據(jù)傳輸過程中如果僅考慮能耗最少可能會導致一部分節(jié)點能量消耗過快而死亡。在本算法中，通過引入懲罰函數(shù)的思想，將一部分能量消耗過快節(jié)點的能耗轉移給能量消耗較少的節(jié)點。

PSPRP算法的主要步驟:

(1)給定傳感器節(jié)點的坐標、初始能量E0，初始化無線傳感網絡，并建立鄰接矩陣;

式中，r0表示傳感器的的傳輸半徑，(xi，yi)表示傳感器節(jié)點i的坐標，(xj，yj)表示傳感器節(jié)點j的坐標.，dij表示傳感器節(jié)點i與傳感器節(jié)點j之間的距離;

(2)利用Floyd算法分別求出所需傳感器節(jié)點到基站的最短路徑，對給定一個無線傳感器網絡Gwsn=(V，E，ω)，其中，得到一個矩陣序列{εk|k=0，1，…，n}(k 表示中間節(jié)點的個數(shù))，其中ε0=(ωij)n×n，εk(i，j)表示節(jié)點i到節(jié)點j、且滿足中間節(jié)點皆屬于集合{1，2，…，k}的一條最短路徑的能耗值，且有;

(3)統(tǒng)計Step 2中所有能量最短路徑中每條邊被使用的次數(shù)num;

(4)判斷num是否大于給定的懲罰閾值，如果大于懲罰閾值則邊權改變，否則不變;懲罰關系表示如下;

式中，ωij表示邊eij的能量權重，α表示懲罰閾值，k為懲罰系數(shù);

(5)更新鄰接矩陣并調用Floyd算法，再統(tǒng)計每個節(jié)點所耗能量， k)，即每個節(jié)點的能耗為最短路徑中所有由該節(jié)點發(fā)出的邊的能量和;判斷是否有節(jié)點死亡，如果不存在Ei〉E0(即不存在節(jié)點死亡)，則更新鄰接矩陣并返回(2);反之，輸出最終的結果。

由于傳感器節(jié)點的密集性和隨機分布性，則存在一小部分節(jié)點能耗過快導致過早死亡，這在無線傳感網絡需要得到精確結果的應用領域是不被允許的，如軍事領域等。為了解決上述現(xiàn)象，設計了PSPRP協(xié)議。在步驟2中，調用Floyd算法的時間復雜度是o(n2)，在步驟3中，雖然統(tǒng)計所有能量最短路徑每條邊被重復使用的次數(shù)，但是由于傳感器集群數(shù)目龐大，只從中挑選出能耗過快的少部分節(jié)點。

3 仿真驗證與分析

為了評價改進后的PSPRP協(xié)議的性能，本文對PSPRP算法和SPRP算法進行了仿真實驗。在200m×200m的正方形WSN監(jiān)測區(qū)域中，隨機部署了200個傳感器節(jié)點，如圖1所示，基站位于(0，0)處，所有節(jié)點一再放置就不再移動。懲罰閾值α=20%，懲罰系數(shù)k=2，傳輸半徑r0=87m。

如圖2所示，橫坐標表示的是隨機分布的200個傳感器節(jié)點，縱坐標表示的是各個傳感器所耗費的能量值。

圖1 200個節(jié)點的隨機分布圖

圖2 200個節(jié)點的能耗仿真結果示意圖

仿真結果顯示PSPRP算法比SPRP算法具有更好的網絡均衡性，就拿兩種算法耗能最多的節(jié)點相比，SPRP算法中耗能最多的節(jié)點是59(39 672m2)，消耗的總能量為311 803m2。而PSPRP算法中耗能最多的節(jié)點是97(27 030m2)，消耗的總能量為320 161m2。通過對比發(fā)現(xiàn)PSPRP算法中耗能最多的節(jié)點比SPRP算法節(jié)約32%，但總耗能只增長0.026%。綜上所述，PSPRP算法比SPRP算法具有更好的網絡均衡性是以增長小幅度的總耗能為代價。

4 結束語

設計有效的路由協(xié)議目的就是要利用節(jié)點有限的資源，完成高效的數(shù)據(jù)傳輸任務，延長網絡的使用壽命，提高節(jié)點的能效，并保證一定的靈活性、可靠性和魯棒性。在PSPRP協(xié)議中，采用“分治”的策略，將能量最短路徑上的所有邊劃分為懲罰邊和正常邊，這樣就可以有效的減少能量消耗過快節(jié)點的能耗。但是PSPRP算法還有很多待解決的問題，比如算法對網絡環(huán)境動態(tài)變化的適應性問題(節(jié)點移動性、通信狀態(tài)的變化等等)，而且負載均衡只在懲罰區(qū)域內部實現(xiàn)，未能在全局范圍內考慮，之后將在這些方面對算法進行進一步的優(yōu)化。

［1］ Li JZ，Gao H.Survey on sensor Network Research［J］.Journal of Computer Research and Development of china，2008，45(1):1-15.

［2］ Heinzelman W，Chandrakasan A，Balakrishman H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEETransWireless Commum，2002，1(4):660-670.

［3］ Duan Zhi-feng，Guo Fan，Deng Ming-xing，et al.Shortest Path Routing Protocol for Multi-layer Mobile Wireless Sensor Net Works［C］.WuHan:Huazhong University of Science and Technology，2009:106-110.

［4］ Intanagonwiwat C，Govindan R，Estrin D，et al.Directed diffiusion for wireless sensor networking［J］.IEEE/ACM Trans On Networking，2003，11(1):2-16.

［5］ 崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展［J］.計算機研究與發(fā)展，2005，42(1):163-174.

［6］ Heinzelman W，Chandrakasan A，Balakrishman H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］.Hawaii:Proceedings of the 33rdAnnual Hawaii International Conference on System Sciences，2000:10-19.