基于情景感知的Ad Hoc網絡帶寬管理機制

王海濤，閆 力，宋麗華，陳 暉，張國敏

(1.解放軍理工大學 信息管理中心，南京 210007；2.解放軍理工大學 指揮信息系統學院，南京 210007)

基于情景感知的Ad Hoc網絡帶寬管理機制

王海濤1，閆 力1，宋麗華2，陳 暉1，張國敏2

(1.解放軍理工大學 信息管理中心，南京 210007；2.解放軍理工大學 指揮信息系統學院，南京 210007)

為了在資源受限的Ad Hoc網絡中優先保障關鍵業務，提出一種基于情景感知的Ad Hoc帶寬管理機制(context-aware bandwidth management scheme，簡稱CABMS)。網絡節點收集本地情景信息，以貝葉斯網絡作為情景推理工具判斷業務重要性，確定帶寬分配的效用函數。通過建立原問題的對偶問題和引入帶寬“影子價格”，實現節點自主根據帶寬價格調整帶寬請求，并使帶寬分配算法快速收斂。CABMS將業務分為不同等級。當帶寬資源緊缺時，高等級業務優先得到帶寬；在帶寬嚴重不足時，拒絕部分常規業務請求，以保證關鍵業務的帶寬需求。仿真結果表明，在給定網絡條件下，與比例公平機制相比，緊急業務分配的帶寬增加了約42%，重要業務分配帶寬基本未變，而常規業務分配的帶寬下降了約37%，CABMS可在保證一定公平性前提下給相對重要的業務流分配更多帶寬份額。

Ad Hoc網絡；情景感知；帶寬管理；貝葉斯網絡；比例公平性

由于可在各種臨時場合靈活快速組網，Ad Hoc網絡已廣泛應用于應急場合和戰場環境。Ad Hoc 網絡中帶寬資源稀缺，當網絡中數據流對帶寬資源爭用時，就需要對數據流的帶寬分配進行控制。目前，Ad Hoc網絡的帶寬管理方面已有許多研究成果。Fang等[1]提出了非合作博弈和合作博弈2種帶寬分配模型，通過改變效用函數來權衡帶寬分配的公平性和效率。Xue等[2]引入最大團影子價格的概念，提出了一種基于價格的帶寬分配算法，在達到公平性的同時使數據流的效用之和最大化。文獻[3-4]提出了一種基于拍賣機制的Ad Hoc帶寬分配算法，數據流根據預算和當前帶寬價格確定競爭資源，降低了算法復雜度并加快了收斂速度。Zhao等[5]針對Ad Hoc網絡提出了一種分布式接入控制算法，其無需知道確切的帶寬剩余量。

但以上方法均未針對特定應用場景的特點來考慮帶寬的合理分配，實際網絡環境中不同業務的重要性各異，戰場中尤其如此。從網絡生存性角度出發，在帶寬資源緊張時，應使帶寬分配向業務重要性高的數據流傾斜，保障關鍵業務的優先完成。另外，現有的Ad Hoc網絡管理方案并未系統考慮應用所處的網絡情景，包括節點的異構性和用戶的特殊需求等。Anind Dey針對情景給出了一個較為通用的定義：情景是能夠用來表征實體當前狀況的任何信息，實體可以是人、物或其他與用戶及應用交互相關的任何對象，包括用戶和應用本身[6]。在實際網絡環境中，可通過各類傳感器和探測裝置獲取相關情景數據[7]，然后使用諸如貝葉斯網絡等相關工具對其建模和推理，并將得到的情景信息存儲在情景知識庫中供用戶查詢使用。貝葉斯網絡是一種用于不確定性問題建模和分析的方法，屬于概率圖形模型，在處理不確定性問題方面具有獨特的優點，提供各種高效的推理算法[8]。利用貝葉斯網絡作為情景推理工具已經得到廣泛認可[9-10]。基于情景感知，應用系統能及時獲知環境信息并據此做出適應性行動，進而為用戶提供相關信息或服務，使用戶以較低的代價高效獲得滿意的服務[11]。為此，提出一種Ad Hoc網絡條件下的基于情景感知的帶寬分配方案。

1 背景知識和基本理論

1.1 基本概念

當節點的一跳覆蓋范圍相同時，Ad Hoc網絡可表示為無向圖G(V,E)，其中V為節點集合，E為鏈路集合。對于2條無線鏈路，若其中一條鏈路的任一端在另一條鏈路某一端的傳輸范圍之內，則認為這2條鏈路之間有競爭關系。據此，可用圖1(a)中的網絡拓撲構造出一個流競爭圖(圖1(b))來表示鏈路之間的競爭關系。圖1(a)有3條數據流F1、F2和F3，且各占用了不同的鏈路，F1={1,2,3,4}，F2={7,5}，F3={3,4,6}。圖1(b)中虛線為2個鏈路集合，是流競爭圖的2個極大連通子圖，稱為團。一條鏈路能夠傳輸成功，當且僅當此鏈路所在團中的其他鏈路不同時傳輸數據，團構成了Ad Hoc網絡中的基本帶寬資源單位。圖1所示3條數據流在Q1和Q2中分別占用了不同鏈路。

圖1 網絡拓撲及對應的流競爭圖Fig.1 Network topology and flow contention

1.2 團約束條件

為表達數據流占用團資源的鏈路數目，構造團流關系矩陣A，其中Q1={2,3,4,6}，Q2={1,2,3,5,7}，如表1所示。假定網絡中有n條數據流，m個團資源，帶寬分配的團約束條件需滿足：

AXT≤CT；

(1)

Rmin,i≤xi≤Rmax,i, i=1,2,…,n。

(2)

其中：X為帶寬分配向量，X={x1,x2,…,xn}；C為團的帶寬容量向量，C={C1,C2,…,Cm}。

表1 團流關系矩陣

1.3 問題建模

效用函數Ui(xi)反映分配帶寬對數據流的價值，且Ui(xi)為凹函數。帶寬分配的優化目標可表達為：

(3)

式(3)稱為原始問題P，這是一個帶有約束條件的目標函數優化問題。顯然，可行域為非空、緊致和凸的，目標函數為凹函數，故P有唯一最優解[1]。要求問題P的最優解，節點需要獲知所有其他數據流的帶寬分配值，這會帶來很大的通信代價。為此，可以考慮P的對偶問題D。

P的拉格朗日方程為：

(4)

其中γ為拉格朗日乘子向量，且γ≥0。根據拉格朗日方程可進一步寫出P的對偶形式：

(5)

(7)

其中Ω為x的可行域。由此，將γ視為帶寬價格，反映網絡中的擁塞程度。

2 CABMS方案描述

2.1 情景感知和決策

為實現自適應根據業務重要性分配帶寬資源，基于情景感知的AdHoc網絡帶寬管理機制(CABMS)需要借助情景感知技術對業務的重要性進行推理。具體來說，CABMS選用貝葉斯網絡作為推理工具，因其可表達和分析不確定性和概率性的事物[14]，貝葉斯網絡可用一種可視化方式來表達不確定性，有利于理解情景模型。決定業務重要性的因素很多，為了簡化分析，在此以戰場環境為例使用7種較常見的情景信息來評價業務的重要程度，即業務類型(business)、用戶身份(identity)、戰斗狀態(fight)、環境噪聲(noise)、用戶加速度(acceleration)、機械振動頻率(vibration)和業務重要性(significance)，且假定均為離散變量。根據變量是否可觀察，可將上述7種情景分為可觀察變量Vobserved={I,N,A,V,B}和隱藏變量Vhidden={F,S}。表2為各類情景的取值及含義，以取值集合中的黑體表示變量。根據情景對業務重要程度產生影響的因果關系，可構造出如圖2所示的貝葉斯網絡，并根據取值集合，對環境噪聲、加速度、振動頻率和用戶身份4類情景變量給出初始取值概率，具體取值在實際中可對樣本進行統計得到，如環境噪聲為嘈雜和安靜的初始概率分別為0.8和0.2。根據這4類情景推理對應業務的重要程度，圖2中白色為可觀察變量，灰色為隱藏變量。例如，當環境嘈雜、用戶快速移動且機械振動頻率較高時，用戶很可能處于戰斗環境中，此時用戶的通信需求往往更重要。同時，用戶身份對業務類型也有影響，相對而言，指揮人員的信息比來自普通士兵的信息更重要。

表2 各類情景的類型及取值

圖2 情景推理中的貝葉斯網絡Fig.2 BN in context reasoning

在實際應用中可根據大量樣本對貝葉斯網絡進行參數訓練。在數據無缺失時，可利用最大似然法估計參數；數據有缺失時，可利用EM算法進行參數學習。節點獲取情景后，利用構造的貝葉斯網絡進行推理，CABMS采用團樹法完成概率分布的計算。目前團樹法是一種計算速度很快的精確推理算法[15]，其主要步驟是將貝葉斯網絡轉化為團樹，通過置信傳播來計算相關概率。利用團樹法可在給定證據的條件下，計算感興趣節點的邊緣概率分布，由此判斷節點的取值。

2.2 帶寬分配過程

為反映業務的差異，實現不同業務重要性對帶寬分配結果的影響，CABMS使用Sigmoid函數來表示數據流的效用：

(8)

(9)

可解出：

(10)

因為φ>0，Ppath>0，且(φ/Ppath-2)φ/Ppath≥0，則φ/Ppath>2，故0

(11)

引入業務重要性參數κ(κ>0)，且

φ=(2+κ)Ppath，

(12)

則

(13)

規定當路徑價格Ppath相等時，業務重要性每提高一個等級，分配的帶寬增加50%。令xEM、xIM和xGE分別表示“緊急業務”、“重要業務”和“一般性業務”分配的帶寬，則有

xEM/xIM=3/2, xIM/xGE=3/2,

PPath,EM=PPath,IM=PPath,GE。

(14)

根據式(13)可求解出對應式(14)中不同業務帶寬分配關系的κ值：κEM=1，κIM=0.22，κGM=0.083。

為簡化處理，選擇團中到所有其他鏈路跳數之和最小的節點作為團首節點，團首節點負責收集經過該團的流的帶寬請求，并更新團的帶寬價格。借鑒文獻[1]的梯度投影法(gradient projection algorithm，簡稱GPA)，收到數據流的帶寬請求后，團首節點根據下式計算新的帶寬價格，

(15)

其中：[a]+表示max{0，a}；β為更新步長，且當β足夠小時，帶寬分配結果將收斂。可見，當帶寬需求大于團容量時，價格會逐步上升，反之，價格會逐步降低，反映經濟學中的供求關系。團首節點將新價格告知所有穿越該團的數據流(源節點)，數據流依照式(7)計算出新的最優帶寬分配值x*(r+1)后，節點根據式(16)確定實際的帶寬需求，并將xreq返回給團首節點，開始下一輪價格計算。如此迭代，直至各數據流的帶寬請求值收斂，作為最終帶寬分配結果，

xreq=min(max(x*,Rmin),Rmax)。

(16)

實際中，當分配的帶寬超過數據流最大帶寬需求時，再增加帶寬，其效用也不再增加，反而造成帶寬浪費；當帶寬配額低于最小帶寬需求時，其效用為0，同樣也會浪費帶寬。CABMS考慮了數據流的最大和最小帶寬需求，提高了帶寬使用效率。當帶寬充足時，為所有數據流分配其帶寬最大需求值；當團容量不足以滿足所有數據流的最小帶寬需求時，應根據業務重要性選擇性拒絕某些非關鍵業務，以優先保障關鍵業務的順利完成。當各數據流請求的帶寬值發送至團時，團首節點將計算得到的帶寬價格和團剩余容量返回數據流，然后數據流確定當前剩余帶寬是否滿足自己的最低需求。若滿足，它將繼續參與帶寬分配過程；否則，退出帶寬分配過程。

若團的帶寬容量不足以滿足所有帶寬請求，團首節點將向參與競爭的數據流發送一條帶寬不足的提示信息Requst_to_abort，以提醒部分數據流取消或者延后帶寬請求。CABMS可基于情景信息獲悉業務重要性，因此，在收到Requst_to_abort消息后，數據流應根據自身業務的重要性，以相應概率決定退出帶寬競爭。選擇概率性退出是出于公平性的考慮，以使重要性較低的業務不致于完全“餓死”。選擇性退出概率的表達式為：

(17)

3 仿真分析

3.1 仿真參數設置

利用Matlab進行仿真實驗，在1000 m×1000 m區域中隨機生成一個包含10個節點的Ad Hoc網絡，隨機產生的拓撲結構如圖3所示，節點的覆蓋范圍是半徑為400 m的圓，節點間的邊表示兩節點在彼此覆蓋范圍內。設源節點為{5,1,3}，對應的目標節點為{8,10,9}，路由算法使用Floyd算法，可得到3條數據流的路由分別為F1={1,4,6,10}，F3={3,6,10,9}，F5={5,4,6,8}。根據活動鏈路構建團資源，在給定網絡拓撲和路徑后，圖4為最大團Q1和Q2，其中Q1={(1,4), (5,4), (4,6), (3,6), (6,10), (6,8)}，Q2={(9,10), (4,6), (3,6), (6,10), (6,8)}。

圖3 隨機產生的拓撲結構Fig.3 Some topology generated randomly

圖4 最大團Q1和Q2Fig.4 Maximum cliques Q1 and Q2

設k為業務的重要等級，k越大表示業務越重要，N為業務等級，N=3，從業務重要性角度定義公平性指數F，業務分配到的帶寬應正比于其業務重要性，

(18)

F越大則公平性越好，且F∈[0,1]。

3.2 仿真結果與分析

假定圖3中源節點的情景如表3所示，表4為通過團樹法計算得到的業務重要性概率及判定結果。在獲取情景信息后可推理得到節點當前的業務重要性，進而確定對應的κ值。

表3 各節點情景配置

表4 給定證據下推理得到的業務重要性

3.2.1 仿真實驗1

為簡化分析，假設所有數據流的最小帶寬需求均為0，最大帶寬需求均為3 Mbit/s。圖5、6分別為在CABMS和比例公平準則下的帶寬分配。CABMS下3條數據流的帶寬分配結果為：{x1=1.579 0，x2=1.048 1，x3=1.055 9}，比例公平準則下的帶寬分配結果為：{x1=1.111 2，x2=1.666 8，x3=1.111 2}。從圖5、6可看出，帶寬分配在一定輪次后收斂，帶寬分配步長β越大，收斂速度越快。數據流F1和F5在Q1和Q2中所占的鏈路數相同，按照規則，CABMS中F1分配的帶寬是F5的1.5倍，而F1分配的帶寬并未達到F3的2.25倍。這是因為F3在Q1中只使用了2條鏈路，在帶寬競爭較激烈的Q1中，F3為得到相同帶寬所支付的代價比另2條數據流要低，故其分配得到了更多帶寬。由于比例公平性準則中嚴格按照數據流占用鏈路資源的大小分配帶寬，F3在帶寬價格不為0的Q1中占用的鏈路最少，分配到的帶寬也最多。常規性的業務(F3)在比例公平準則下，由于占用Q1中鏈路資源少的固有優勢，獲得了比其他2條數據流多50%的帶寬分配，這使得重要性更高的2條數據流的QoS下降。CABMS中由于在帶寬分配中對重要性高的數據流(F1)賦予更大的κ值，獲得了高出比例公平性下分配的帶寬。計算公平指數和效率，可得到比例公平性下的Fprop=0.695 0，CABMS下的FCABMS=0.890 6。顯然，CABMS獲得了更好的帶寬分配公平性。

圖5 CABMS下的帶寬分配Fig.5 Bandwidth assignment under CABMS

圖6 比例公平準則下的帶寬分配(節點1與5曲線重合)Fig.6 Bandwidth assignment under proportional fairness (curves of node 1 and 5 overlaps)

圖7為CABMS下帶寬價格的變化情況。從圖7可看出，Q1由于容量不能完全滿足各數據流的帶寬需求，價格不斷上升，最終趨于穩定。Q2由于初始時各數據流提出的帶寬需求較大，價格開始上升，但隨各數據流不斷調整自身需求，使之趨于合理，Q2的帶寬容量可完全滿足需求，故帶寬價格最終又降為0。

圖7 CABMS下帶寬價格變化趨勢(帶寬價格單位為1)Fig.7 Change of bandwidth price under CABMS (bandwidth price unit is 1)

3.2.2 仿真實驗2

實驗2為團容量不能滿足所有數據流最小帶寬需求時帶寬的分配情況。網絡拓撲和數據流配置與仿真實驗1相同，但3條數據流的最大、最小帶寬需求如表5所示，團容量為3 Mbit/s。可見，團1無法滿足所有數據流的最小帶寬需求，即0.7×3+0.5×3+0.2×2=4>C1=3，這種情況下必須拒絕某些數據流的帶寬請求。圖8、9為CABMS下2種可能的分配結果(結果1和結果2)，圖10、11分別為對應的帶寬價格變化趨勢

表5 3條數據流的最大、最小帶寬需求

圖8 數據流1和3得到的帶寬分配Fig.8 F1 and F3are assigned bandwidth

圖9 數據流5得到的帶寬分配Fig.9 F5 is assigned bandwidth

圖10 分配結果1下的帶寬價格變化(帶寬價格單位為1)Fig.10 Bandwidth price’s change under result 1 (bandwidth price unit is 1)

圖11 分配結果2下的帶寬價格變化(帶寬價格單位為1)Fig.11 Bandwidth price’s change under result 2 (bandwidth price unit is 1)

從圖8、9可看出，在分配結果1中，約30輪次時首次收到Request_to_abort，數據流1保持自己的帶寬請求，而數據流3和數據流5均放棄帶寬請求，所以團1對應的帶寬價格在此時開始下降。在約50輪次時，數據流1分配帶寬達到了自身最大帶寬需求0.8 Mbit/s。在約80輪次時，Q1的帶寬價格降至0，此時，數據流5判斷剩余帶寬容量已不足以滿足其最小帶寬需求，故完全退出帶寬競爭，而數據流3判斷剩余帶寬容量可以滿足自身最小帶寬需求，故重新加入帶寬分配，在350輪次時結果收斂，得到帶寬配額0.3 Mbit/s。同時，Q1接入的數據流趨于飽和，故帶寬價格不為0。與結果1類似，結果2在首次收到Request_to_abort后，3條數據流均選擇臨時退出帶寬競爭，導致Q1的帶寬價格降為0，再次收到Request_to_abort時，只有數據流5保持自己的帶寬請求，并得到了最大帶寬需求0.9 Mbit/s。此時，Q1帶寬容量仍有剩余，故帶寬價格為0，但剩余容量不滿足數據流1和數據流3的最小帶寬需求，故二者徹底退出帶寬競爭。

4 結束語

實際網絡應用環境中，特別是戰場環境下，各種業務的重要性存在顯著差異。為了能夠在帶寬資源受限的Ad Hoc網絡環境中優先保障關鍵業務的順利實施，提出了一種情景感知的帶寬分配方案(CABMS)，利用各類傳感器收集的數據作為情景推理依據，以貝葉斯網絡作為推理工具推理業務重要性，根據其重要程度在數據流競爭稀缺的帶寬資源時為關鍵業務分配相對更多的帶寬，提高了網絡生存性。但是，為簡化分析，CABMS將變量假定為離散變量，而實際中有些變量(如噪聲)是連續的。今后可利用高斯混合模型(mixture of gaussian，簡稱MOG)來描述變量，進而可根據噪聲變化的特征確定相關場景。另外，CABMS帶寬分配中，團首節點需要收集所有數據流的帶寬請求后才計算新的帶寬價格，要求各數據流間的同步，這在動態變化的Ad Hoc網絡較難實現，今后還可考慮實現異步式的帶寬分配方案。

[1] FANG Z,BENSAOU B.Fair bandwidth sharing algorithms based on game theory frameworks for wireless Ad-Hoc networks[C]//INFOCOM 2004:Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies,2004:1284-1295.

[2] XUE Y,LI B,NAHRSTEDT K.Price-based resource allocation in wireless ad hoc networks[C]//Eleventh International Workshop on Quality of Service,2003:79-96.

[3] CURESCU C,NADJM-TEHRANI S.A bidding algorithm for optimized utility-based resource allocation in Ad Hoc networks[J].IEEE Transactions on Mobile Computing,2008,7(12):1397-1414.

[4] KAO B R,LEE L K,LAI K R.Multi-hop auction-based bandwidth allocation in wireless Ad Hoc networks[C]//IEEE International Conference on Advanced Information Networking & Applications,2011:772-778.

[5] ZHAO H,GARCIA-PALACIOS E,WEI J,et al.Distributed resource management and admission control in wireless ad hoc networks:a practical approach[J].IET Communications,2012,6(8):883-888.

[6] DEY A K.Understanding and using context[J].Personal and Ubiquitous Computing,2001,5(1):4-7.

[7] PERERA C,ZASLAVSKY A,CHRISTEN P,et al.Context aware computing for the internet of things:a survey[J].IEEE Communications Surveys & Tutorials,2014,16(1):414-454.

[8] WITZIG T,ZOLLNER J M,PANGERCIC D,et al.Context aware shared autonomy for robotic manipulation tasks[C]//2013 IEEE/RSJ International Conference on Intelligent Robots and Systems,2013:5686-5693.

[9] KO K E,SIM K B.Development of context aware system based on bayesian network driven context reasoning method and ontology context modeling[C]//2008 International Conference on Control, Automation and Systems,2008:2309-2313.

[10] RHO W H,CHO S B.Context-aware smartphone application category recommender system with modularized Bayesian networks[C]//2014 10th International Conference on Natural Computation,2014:775-779.

[11] WOOD A,STANKOVIC J A,VIRONE G,et al.Context-aware wireless sensor networks for assisted living and residential monitoring[J].IEEE Network,2008,22(4):26-33.

[12] LI B J,LIEW S C.Proportional fairness in wireless LANs and ad hoc networks[C]//2005 IEEE Wireless Communications and Networking Conference,2005:1551-1556.

[13] BOYD S,VANDENBERGHE L.Convex Optimization[M].New York:Cambridge University Press,2004:215-264.

[14] 王越，譚暑秋，劉亞輝.基于互信息的貝葉斯網絡結構學習算法[J].計算機工程，2011,37(7):62-64.

[15] 厲海濤，金光，周經倫，等.貝葉斯網絡推理算法綜述[J].系統工程與電子技術，2008,30(5):935-939.

編輯：翁史振

Context awareness based bandwidth management scheme for Ad Hoc network

WANG Haitao1, YAN Li1, SONG Lihua2, CHEN Hui1, ZHANG Guomin2

(1.Information Management Center, PLA University of Science and Technology, Nanjing 210007, China;2.College of Command Information Systems, PLA University of Science and Technology, Nanjing 210007, China)

In order to guarantee key businesses when bandwidth resource is in shortage, an adaptive and flexible context-aware bandwidth management scheme (CABMS) is proposed to improve Ad Hoc network survivability. Nodes firstly query the local context information, and use Bayesian network (BN) to determine the importance of current business and the utility function of bandwidth allocation. Through establishing the dual problem of original one, the "shadow price" of bandwidth is introduced, so that the nodes are able to adjust bandwidth requests on their own according to the price with the convergence of allocation result. CABMS business is classified into different levels. When bandwidth resource is in shortage, the high-class business will be biased in bandwidth allocation; when in severe shortage, some regular business bandwidth requests will be rejected in order to guarantee the bandwidth requests of key business. Simulation results indicate that CABMS can assign more bandwidth to relatively important business under given conditions, compared with proportional fairness, urgent business bandwidth allocation increases by about 42%, important business bandwidth allocation remains essentially unchanged, and the regular allocate bandwidth falls by about 37%.

Ad Hoc network; context awareness; bandwidth management; Bayes network; proportional fairness

2016-03-15

國家自然科學基金(61072043，61402521)

王海濤(1976-)，男，河南焦作人，副教授，博士，研究方向為無線自組網和網絡管理。E-mail:haitmail@126.com

王海濤，閆力，宋麗華，等.基于情景感知的Ad Hoc網絡帶寬管理機制[J].桂林電子科技大學學報，2016,36(6):487-494.

TP393

A

1673-808X(2016)06-0487-08