拍賣機制的包轉發路由模型及其仿真研究

徐名霞

廣東省高級技工學校 廣東 516100

0 引言

在無線傳感器網絡中，節點的自治性可以使得其在無線傳感器網絡路由中受到很大的限制。以數據作為中心的信息路由中，查詢路由是通過對整個傳感數據的命名來進行傳播的，每個網絡節點中通過建立路由樹來傳輸相應的數據從而更好地降低數據內爆，這樣的數據包可以沿著低能耗的路徑作為傳輸以至于更好地降低整個網絡的能量消耗。然而，這種路由策略會使得能量消耗不夠均衡，從而加速了網絡的劃分過程，因此，通過拍賣機制的實現包轉發路由值得我們研究。

1 拍賣機制的包轉發路由模型分析

一個拍賣博弈模型是由兩部分組成的：買方和賣方，在整個無線傳感器的網絡中，買方作為整個發送數據主要節點而賣方則是它的相鄰節點。我們需要將多跳的無線傳感器網絡轉換成為一個無向圖G =< V，E>的形式，其中V是屬于網絡中的節點集合，E節點則是它們之間所通信的邊集合。假如兩個節點存在有邊相連時，則說明它們之間是可以直接通信的，要么就無法直接通信，如圖1所示。其中ie是屬于節點iv所剩下的能量，vih是屬于節點iv至Sink節點間的跳數，(,3)vsv h是屬于節點s v通過相鄰居節點3v到 Sink節點之間的最小跳數。各個節點之間都需要保存局部整個網絡的信息，包括了各個節點到 Sink 節點之間的最小跳數以及該節點的余下能量，該節點的相鄰節點到Sink節點之間的最小跳數以及這些相鄰節點余下的能量。

圖1 網絡拓撲模型圖

Sink節點需要給發送節點之間支付一定的價格以及作為它服務的報酬和發送數據能量所消耗全部補償；另一方面，為了更好地獲得數據的有關轉發服務，發送節點也會支付相應的價格給相鄰的節點。各個相應的鄰節點是為了更好地提高自己的收益需要進行相互的競標，進行數據包相應的轉發服務。假如全部節點是屬于誠實的，且當有關節點提高整體收益時其他節點也是樂意進行友好合作的，用包的成功轉發率來抑制相關節點的不合作行為，那么整個節點就有可能會得到相關的收益以后拒絕整個轉發包又或者是轉發少量的包來減少自己現有資源的消耗。

2 拍賣機制的價格路由博弈算法流程

從源節點到 Sink 節點之間選擇一條可靠而且相對穩定的路徑，提出了一個在無線傳感器網絡中屬于拍賣機制的價格路由博弈算法—Price Routing Game(PRG)。在這樣的路由算法中，各個傳感器節點都可以看作一個決策者，他們就會依據拍賣博弈模型選擇一個適合自己的策略，各個節點也都會按照自己的信息或者相鄰節點的信息獨立地進行科學決策，給出自已的價格，并且選擇一個價格比最合適的價格來提高自已的收益，從而使選擇出來的轉發節是最優的。

為了使相關節點之間能夠順利實現拍賣，各個節點之間需要獲取相鄰節點的有關信息和它們到 Sink節點之間的跳數，為各個節點建立起相鄰的節點集合列表。第一，網絡需要通過Sink節點向其它較為普通節點發送一些廣播消息，使得每個節點可以記錄通過相鄰節點來達到 Sink 節點時的最小跳數。第二，在簇頭建立前，各個節點就會向它們的相鄰節點間發送能量更新數據消息，記錄好它們的相鄰節點余下的能量。

當相鄰節點建立好列表后，在數據發送的整個階段，與Sink 節點最遠的節點需要相鄰節點進行轉發服務，各個參與發送又或者是轉發數據的節點(買方)都會與它們相鄰的節點(賣方)組成一個拍賣博弈過程。賣方為了更好地獲得收益需要相互競爭轉發一些數據，并給出各自的標價，買方需要根據價格函數是否可以更好地提高自己的整體收益選擇最好的節點作為轉發數據。如果買方最大化收益的標價相同的有多個時，那么買方就會選擇一些能量消耗較少的路徑來提高自己的整體收益。整個算法的流程如圖2 所示。

圖2 算法流程圖

3 仿真實驗及分析

NS2(Network Simulator，version 2)是屬于一種由 UC Berkeley 開發并且成為面向對象的網絡仿真器，本質上是屬于一個離散事件模擬器，全部的仿真過程都屬于由離散事件驅動的，可以很好地實現模擬整個網絡的環境。我們可以用NS2仿真軟件對 PRG算法進行相應的仿真實驗，并且和LEACH 協議與相關簇首改善算法研究對比，表現我們算法能量消耗達到均衡的效果。

3.1 仿真實驗

我們所使用的NS2以及Mannasim 來實現該算法，并且分析它的性能，網絡中全部的節點基本上都是隨機分布的，基站 Sink都處于在整個網絡的中間位置，相應的仿真參數設置如表1所示，仿真場景如圖3所示。

表1 仿真參數設置

圖3 網絡場景

我們參考了文獻[7]所提供的改進算法—EHDC，并將我們的 PRG 算法與現有的典型 LEACH 協議以及 EHDC 算法作相應的比較。圖3與圖4分別是屬于網絡的節點數各為50以及網絡節點數為 100 的 LEACH 協議、EHDC 算法和PRG 算法余下的能量圖，通過仿真結果我們可以看出LEACH 協議中現有節點的能量消耗比 EHDC 算法以及我們的 PRG 算法速度快多了，而且 EHDC 算法中節點的所需要用能量消耗也都比我們現有的算法(PRG)快一些?？上攵?LEACH 協議中節點的能量消耗與 EHDC 所需能量消耗比我們現有算法中節點的能量消耗要快一些，這是因為LEACH協議以及EHDC 協議是單跳通信的，各個普通節點將相關數據發送給簇頭節點就即可。

圖4 網絡規模為50的單個節點的剩余能量

整個簇頭節點再將各個數據以單跳的形式轉發給 Sink節點，當某一個簇頭節點離 Sink 節點較遠時，需要傳輸能量將會變大，從而導致了大量的能量消耗。因為EHDC 算法在進行簇頭選擇時是參考節點的余下能量來進行選擇的，各個節點需要通過自已現有的余下能量與相關簇內節點平均的剩余能量之比來決定成為簇頭的概率，從而更好地均衡每一個網絡的能量，因此它比 LEACH 協議會好一些。隨著整個網絡規模的不斷加大，PRG 現有算法的能量消耗也會比其它的算法能量消耗小一些。圖5作為整個網絡中不相同規模的單個節點的余下能量，從圖中我們可以看出來，隨著各個網絡節點數的相應增加，各個節點的能量將會消耗得越來越多，由于節點越多時其所需要轉發或者傳輸的數據將會越來越多，因此單個節點的能量消耗將會變大。

圖5 網絡規模為100的單個節點的剩余能量

圖6 網絡中不同規模單個節點的剩余能量

圖7 網絡節點數為50的活躍節點總的剩余能量圖

圖8 網絡節點數為100的活躍節點總的剩余能量圖

圖7與圖8是屬于在一個較小的時間段較為活躍的節點余下能量的總和，從上圖我們可以看得出來，網絡中當每一個節點的數量為50與100 時，那么LEACH 協議與EHDC算法中各個活躍節點的總能量就會比我們現有算法中活躍節點的總能量小一些，并且當整個活躍節點的總能量下降的比我們現有的算法快時，那么我們算法(PRG)中各個活躍節點的能量消耗相對來說會比較穩定。在無線傳感器網絡中各個單跳通信方式來消耗的能量比多跳要高一些，通過多跳通信的方式，并利用相應的博弈模型來選擇一個可靠的轉發節點，因此相對于 LEACH 協議以及 EHDC 算法來說，本算法能夠起到降低節點的能量消耗的作用。

3.2 仿真分析

為了更好地說明我們的拍賣路由博弈算法能量消耗的具有穩定性，我們進行隨機挑選了一個時間段內的 10個節點在各個不同網絡情況下的余下能量的測試，結果這 10個節點的余下能量情況如圖9所示。從圖中我們可以知道，隨著網絡的整體規模的不斷加大，節點的相應能量消耗也會隨著加大，但是各個節點的能量消耗相對來說會變得比較均衡。圖10是整個網絡規模為100個節點的最后一輪節點的余下能量，從圖中可以知道，LEACH協議中各個節點的余下能量十分不穩定，而 EHDC 算法中各個節點的余下能量比LEACH協議來說會相對穩定多了。由于EHDC 算法是按照能量最大化的節點來選擇相應的簇頭，而LEACH 協議簇頭的選擇是具有一定的隨機性，因此EHDC算法比 LEACH協議會好很多。LEACH 協議和EHDC 算法的簇頭節點之間與 Sink 是屬于直接通信的，各個節點之間單跳的通信方式是屬于消耗了大量的能量。在我們現有的算法中，各個多跳通信，基本上都是采用博弈模型來選擇一個最為可靠的轉發節點，而且每一次的轉發時所選擇的節點是不相同的，因此，我們在整個算法中節點的余下能量相對來說會變得均衡一些，從能量的消耗情況看，在我們的 PRG 算法中節點的生命周期比 LEACH 協議要長一些。

圖9 網絡規模不同的節點在某一段時間的剩余能量

圖10 最后一輪節點的剩余能量

我們的 PRG 算法主要是采用了多跳路由算法，在節點剩余能量方面，與其它兩個算法來比具較好的優越性，并且從上圖中我們也可以看出 PRG算法中的每個節點的能量消耗也都比較均衡。從另一角度來看，我們的協議的和其它兩個協議之間的比較可以知道數據傳輸時延會有所增加。

4 總結

綜上所述，文中建立了拍賣路由博弈模型，并提出了一種進行轉發節點選擇的價格路由博弈算法流程，該算法流程可以激勵各個節點相互合作地轉發數據包，每一個節點的目的都是為了通過招標選擇最優的轉發節點來實現自己最大化的收益。仿真結果表明當前節點的包成功轉發率越高，表明該節點的合作級別就越高，越能夠提高整個網絡的吞吐量。

[1]孫利民,李建中,陳渝.無線傳感器網絡[M].清華大學出版社.2005.

[2]趙永輝,史浩山.一種無線傳感器網絡數據包轉發的博弈論算法.[J].西安電子科技大學學報.2010.

[3]徐雷鳴,龐博,趙耀.NS與網絡模擬[M].北京:人民郵電出版社.2003.

[4]李夢君.暗標拍賣的博弈分析[J].科技創業月刊.2009.

[5]李慧芳,姜勝明,韋崗.無線傳感器網絡中基于博弈論的路由建模[J].傳感技術學報.2007.

[6]楊俊剛,史浩山,楊武.無線傳感器網絡CSMA博弈優化算法研究[J].傳感技術學報.2009.

[7]劉新華,李方敏,曠海蘭.基于能量異構的無線傳感器網絡分布式成簇算法[J].小型微型計算機系統.2010.

[8]宋超,劉明,龔海剛.基于蟻群優化解決傳感器網絡中的能量洞問題[J].軟件學報.2009.