拍賣機制的包轉(zhuǎn)發(fā)路由模型及其仿真研究

徐名霞

廣東省高級技工學(xué)校 廣東 516100

0 引言

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

1 拍賣機制的包轉(zhuǎn)發(fā)路由模型分析

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

圖1 網(wǎng)絡(luò)拓撲模型圖

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

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

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

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

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

圖2 算法流程圖

3 仿真實驗及分析

NS2(Network Simulator，version 2)是屬于一種由 UC Berkeley 開發(fā)并且成為面向?qū)ο蟮木W(wǎng)絡(luò)仿真器，本質(zhì)上是屬于一個離散事件模擬器，全部的仿真過程都屬于由離散事件驅(qū)動的，可以很好地實現(xiàn)模擬整個網(wǎng)絡(luò)的環(huán)境。我們可以用NS2仿真軟件對 PRG算法進行相應(yīng)的仿真實驗，并且和LEACH 協(xié)議與相關(guān)簇首改善算法研究對比，表現(xiàn)我們算法能量消耗達到均衡的效果。

3.1 仿真實驗

我們所使用的NS2以及Mannasim 來實現(xiàn)該算法，并且分析它的性能，網(wǎng)絡(luò)中全部的節(jié)點基本上都是隨機分布的，基站 Sink都處于在整個網(wǎng)絡(luò)的中間位置，相應(yīng)的仿真參數(shù)設(shè)置如表1所示，仿真場景如圖3所示。

表1 仿真參數(shù)設(shè)置

圖3 網(wǎng)絡(luò)場景

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

圖4 網(wǎng)絡(luò)規(guī)模為50的單個節(jié)點的剩余能量

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

圖5 網(wǎng)絡(luò)規(guī)模為100的單個節(jié)點的剩余能量

圖6 網(wǎng)絡(luò)中不同規(guī)模單個節(jié)點的剩余能量

圖7 網(wǎng)絡(luò)節(jié)點數(shù)為50的活躍節(jié)點總的剩余能量圖

圖8 網(wǎng)絡(luò)節(jié)點數(shù)為100的活躍節(jié)點總的剩余能量圖

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

3.2 仿真分析

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

圖9 網(wǎng)絡(luò)規(guī)模不同的節(jié)點在某一段時間的剩余能量

圖10 最后一輪節(jié)點的剩余能量

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

4 總結(jié)

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

[1]孫利民,李建中,陳渝.無線傳感器網(wǎng)絡(luò)[M].清華大學(xué)出版社.2005.

[2]趙永輝,史浩山.一種無線傳感器網(wǎng)絡(luò)數(shù)據(jù)包轉(zhuǎn)發(fā)的博弈論算法.[J].西安電子科技大學(xué)學(xué)報.2010.

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

[4]李夢君.暗標拍賣的博弈分析[J].科技創(chuàng)業(yè)月刊.2009.

[5]李慧芳,姜勝明,韋崗.無線傳感器網(wǎng)絡(luò)中基于博弈論的路由建模[J].傳感技術(shù)學(xué)報.2007.

[6]楊俊剛,史浩山,楊武.無線傳感器網(wǎng)絡(luò)CSMA博弈優(yōu)化算法研究[J].傳感技術(shù)學(xué)報.2009.

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

[8]宋超,劉明,龔海剛.基于蟻群優(yōu)化解決傳感器網(wǎng)絡(luò)中的能量洞問題[J].軟件學(xué)報.2009.