Ad—hoc網(wǎng)絡(luò)節(jié)點(diǎn)休眠策略的設(shè)計(jì)

王兆位

摘要：在本文中，作者基于博弈論提出了一種Ad-hoc網(wǎng)絡(luò)節(jié)點(diǎn)的休眠策略，并給出了計(jì)算這種休眠策略的方法。這種休眠策略同時(shí)考慮了節(jié)點(diǎn)的存活時(shí)間和網(wǎng)絡(luò)傳輸數(shù)據(jù)包的效率。理論上來(lái)說(shuō)，這種休眠機(jī)制可以同時(shí)保證網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)男屎途W(wǎng)絡(luò)中節(jié)點(diǎn)的存活時(shí)間。

關(guān)鍵詞：Ad-hoc網(wǎng)絡(luò)；節(jié)點(diǎn)休眠；博弈論

1.前言

Ad-hoc網(wǎng)絡(luò)中如果節(jié)點(diǎn)的能量是有限的，為了節(jié)省節(jié)點(diǎn)的能量，節(jié)點(diǎn)需要在一定時(shí)間內(nèi)進(jìn)入休眠狀態(tài)，因?yàn)樵谛菝郀顟B(tài)中節(jié)點(diǎn)消耗的能量很少。但是節(jié)點(diǎn)進(jìn)入休眠，網(wǎng)絡(luò)中活躍的節(jié)點(diǎn)會(huì)變少，因此設(shè)計(jì)節(jié)點(diǎn)的休眠策略就顯得非常重要。節(jié)點(diǎn)休眠會(huì)造成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的變化，減少網(wǎng)絡(luò)中可用的節(jié)點(diǎn)，所以設(shè)計(jì)休眠機(jī)制的時(shí)候還要考慮這種休眠機(jī)制對(duì)網(wǎng)絡(luò)中數(shù)據(jù)包傳輸效率的影響。

當(dāng)一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的時(shí)候，它的發(fā)送功率是可變的，當(dāng)發(fā)送的功率越大時(shí)，數(shù)據(jù)包被傳送的距離就越遠(yuǎn)，到達(dá)目標(biāo)節(jié)點(diǎn)的概率就越大，但是節(jié)點(diǎn)本身消耗的能量就越多，它存活的概率就越小。這樣的節(jié)點(diǎn)可以認(rèn)為是比其余節(jié)點(diǎn)更加需要休眠的。節(jié)點(diǎn)選擇發(fā)送功率的時(shí)候需要考慮自身的能量上限以及以相應(yīng)功率發(fā)送數(shù)據(jù)能得到的期望收益，這里的收益可以根據(jù)網(wǎng)絡(luò)設(shè)計(jì)的目的來(lái)定義。而在本文的討論中，收益定義為可能得到的休眠時(shí)間和剩余的能量的線性組合。

2.處理方案

2.1基本設(shè)定。

考慮一個(gè)簡(jiǎn)單的模型，一個(gè)節(jié)點(diǎn)集合N={1，2，3…n}，一個(gè)節(jié)點(diǎn)的最大能量用θ表示。對(duì)于接收到的數(shù)據(jù)包P，節(jié)點(diǎn)用于發(fā)送這個(gè)數(shù)據(jù)包的能量稱為傳輸能量。節(jié)點(diǎn)可以選擇以不同的功率發(fā)送P，不同功率發(fā)送P所需要的能量分別為{d1，d2，d3…dm}，用D表示這個(gè)集合。根據(jù)統(tǒng)計(jì)可以得到節(jié)點(diǎn)選擇傳輸能量的概率分布為Ω=（w1，w2，w3…wm），其中wi表示節(jié)點(diǎn)選擇di的概率。在估算一個(gè)網(wǎng)絡(luò)的相關(guān)參數(shù)的時(shí)候，節(jié)點(diǎn)的最大能量θ可以認(rèn)為是未知的，但是θ的概率分布可以認(rèn)為是已知的，設(shè)θ的概率分布密度函數(shù)為f（θ）。

2.2休眠機(jī)制的基本思想。

一般來(lái)說(shuō)，發(fā)送的功率越大數(shù)據(jù)包被傳輸?shù)木嚯x越遠(yuǎn)，同時(shí)發(fā)送節(jié)點(diǎn)使用的能量越多。所以節(jié)點(diǎn)發(fā)送時(shí)使用的能量越多，它越需要進(jìn)行休眠?；谶@個(gè)思想，可以設(shè)計(jì)如下的休眠策略：設(shè)節(jié)點(diǎn)N發(fā)送數(shù)據(jù)包P時(shí)按概率wi選擇使用傳輸能量di發(fā)送數(shù)據(jù)包P，如果di是所有發(fā)送P的節(jié)點(diǎn)中使用的最大的傳輸能量，節(jié)點(diǎn)N可以休眠T（di）個(gè)時(shí)間單位，否則不休眠；不進(jìn)行休眠的節(jié)點(diǎn)繼續(xù)工作，它在這一輪的發(fā)送中沒(méi)有收獲，反而消耗了自己的能量。其中di<θ，因?yàn)楣?jié)點(diǎn)發(fā)送數(shù)據(jù)使用的能量不可能超過(guò)自己的最大能量；T（x）是一個(gè)增函數(shù)。傳輸能量的概率分布會(huì)影響整個(gè)策略的效率，休眠的時(shí)間和選擇的傳輸能量之間的關(guān)系也會(huì)影響整個(gè)策略的效率。所以，在上述的框架中要得到一個(gè)最優(yōu)的休眠策略最終需要確定節(jié)點(diǎn)選擇傳輸能量的概率分布。

在上面設(shè)計(jì)的激勵(lì)機(jī)制作用下，節(jié)點(diǎn)之間會(huì)形成一種非合作的競(jìng)爭(zhēng)關(guān)系，而這種激勵(lì)機(jī)制可以同時(shí)保證節(jié)點(diǎn)傳輸數(shù)據(jù)包的效率和節(jié)點(diǎn)自身的存活時(shí)間。整個(gè)過(guò)程可以建模為一個(gè)非合作博弈，博弈的均衡點(diǎn)是一個(gè)描述節(jié)點(diǎn)使用傳輸能量的概率分布的元組，就代表了一個(gè)對(duì)各個(gè)節(jié)點(diǎn)最優(yōu)的休眠策略。因?yàn)楣?jié)點(diǎn)的最大能量是未知的，但是最大能量的分布是已知的，所以這個(gè)博弈是一個(gè)貝葉斯博弈。所以接下來(lái)的核心任務(wù)就是計(jì)算這個(gè)博弈的均衡點(diǎn)。但是在計(jì)算博弈的均衡點(diǎn)之前，需要嚴(yán)格定義節(jié)點(diǎn)的收益情況。

2.3推導(dǎo)節(jié)點(diǎn)的效用。

2.4計(jì)算均衡點(diǎn)。

因?yàn)橐幚淼牟┺氖且粋€(gè)貝葉斯博弈，所以利用Fictitious Play算法來(lái)估算均衡點(diǎn)。標(biāo)準(zhǔn)的Fictitious Play算法不能處理貝葉斯博弈，但是研究者把它進(jìn)行了擴(kuò)展，擴(kuò)展后的Fictitious Play算法可以處理這種連續(xù)參數(shù)的貝葉斯博弈。在介紹使用Fictitious Play算法計(jì)算均衡點(diǎn)之前，還需要介紹一些其它的概念。

給出了算法收斂的判斷條件，在這個(gè)條件下收斂得到的結(jié)果不是真正意義上的均衡點(diǎn)，但是只要參數(shù)設(shè)置得足夠小，算法得到的結(jié)果和真正的均衡點(diǎn)的差異也足夠小。所以這樣做可以在減少計(jì)算量的前提下保證結(jié)果的有效性。

3.總結(jié)

本文基于博弈論提出了一種控制Ad-hoc網(wǎng)絡(luò)中節(jié)點(diǎn)休眠的策略，并給出了得到這種策略的計(jì)算過(guò)程。從理論上來(lái)說(shuō)，這種休眠策略可以使每個(gè)節(jié)點(diǎn)處于最優(yōu)的情況，在這種休眠策略的控制下，節(jié)點(diǎn)發(fā)送數(shù)據(jù)的成功率和有效性以及獲得的休眠時(shí)間可以取得一個(gè)較好的平衡。

參考文獻(xiàn)：

[1]黃浩軍，尹浩，陳和平，張俊寶，錢峰，宋偉.無(wú)線Ad-hoc網(wǎng)絡(luò)能量感知地理路由協(xié)議研究進(jìn)展，1061-1064，軟件學(xué)報(bào) Vol.25，No.5，May 2014.

[2] Brown G. W.， ‘Iterative solutions of games by fictitious play， Activity Analysis of Production and Allocation， （1951）.