Ad—hoc網絡節點休眠策略的設計

王兆位

摘要：在本文中，作者基于博弈論提出了一種Ad-hoc網絡節點的休眠策略，并給出了計算這種休眠策略的方法。這種休眠策略同時考慮了節點的存活時間和網絡傳輸數據包的效率。理論上來說，這種休眠機制可以同時保證網絡中數據傳輸的效率和網絡中節點的存活時間。

關鍵詞：Ad-hoc網絡；節點休眠；博弈論

1.前言

Ad-hoc網絡中如果節點的能量是有限的，為了節省節點的能量，節點需要在一定時間內進入休眠狀態，因為在休眠狀態中節點消耗的能量很少。但是節點進入休眠，網絡中活躍的節點會變少，因此設計節點的休眠策略就顯得非常重要。節點休眠會造成網絡的拓撲結構的變化，減少網絡中可用的節點，所以設計休眠機制的時候還要考慮這種休眠機制對網絡中數據包傳輸效率的影響。

當一個節點發送數據包的時候，它的發送功率是可變的，當發送的功率越大時，數據包被傳送的距離就越遠，到達目標節點的概率就越大，但是節點本身消耗的能量就越多，它存活的概率就越小。這樣的節點可以認為是比其余節點更加需要休眠的。節點選擇發送功率的時候需要考慮自身的能量上限以及以相應功率發送數據能得到的期望收益，這里的收益可以根據網絡設計的目的來定義。而在本文的討論中，收益定義為可能得到的休眠時間和剩余的能量的線性組合。

2.處理方案

2.1基本設定。

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

2.2休眠機制的基本思想。

一般來說，發送的功率越大數據包被傳輸的距離越遠，同時發送節點使用的能量越多。所以節點發送時使用的能量越多，它越需要進行休眠。基于這個思想，可以設計如下的休眠策略：設節點N發送數據包P時按概率wi選擇使用傳輸能量di發送數據包P，如果di是所有發送P的節點中使用的最大的傳輸能量，節點N可以休眠T（di）個時間單位，否則不休眠；不進行休眠的節點繼續工作，它在這一輪的發送中沒有收獲，反而消耗了自己的能量。其中di<θ，因為節點發送數據使用的能量不可能超過自己的最大能量；T（x）是一個增函數。傳輸能量的概率分布會影響整個策略的效率，休眠的時間和選擇的傳輸能量之間的關系也會影響整個策略的效率。所以，在上述的框架中要得到一個最優的休眠策略最終需要確定節點選擇傳輸能量的概率分布。

在上面設計的激勵機制作用下，節點之間會形成一種非合作的競爭關系，而這種激勵機制可以同時保證節點傳輸數據包的效率和節點自身的存活時間。整個過程可以建模為一個非合作博弈，博弈的均衡點是一個描述節點使用傳輸能量的概率分布的元組，就代表了一個對各個節點最優的休眠策略。因為節點的最大能量是未知的，但是最大能量的分布是已知的，所以這個博弈是一個貝葉斯博弈。所以接下來的核心任務就是計算這個博弈的均衡點。但是在計算博弈的均衡點之前，需要嚴格定義節點的收益情況。

2.3推導節點的效用。

2.4計算均衡點。

因為要處理的博弈是一個貝葉斯博弈，所以利用Fictitious Play算法來估算均衡點。標準的Fictitious Play算法不能處理貝葉斯博弈，但是研究者把它進行了擴展，擴展后的Fictitious Play算法可以處理這種連續參數的貝葉斯博弈。在介紹使用Fictitious Play算法計算均衡點之前，還需要介紹一些其它的概念。

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

3.總結

本文基于博弈論提出了一種控制Ad-hoc網絡中節點休眠的策略，并給出了得到這種策略的計算過程。從理論上來說，這種休眠策略可以使每個節點處于最優的情況，在這種休眠策略的控制下，節點發送數據的成功率和有效性以及獲得的休眠時間可以取得一個較好的平衡。

參考文獻：

[1]黃浩軍，尹浩，陳和平，張俊寶，錢峰，宋偉.無線Ad-hoc網絡能量感知地理路由協議研究進展，1061-1064，軟件學報 Vol.25，No.5，May 2014.

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