基于情景感知的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