Ad-Hoc网络中基于状态转换概率的中继选择算法研究

陈春梅,吴 斌,江 虹

(1.中国工程物理研究院 电子工程研究所，四川 绵阳 621900；2.西南科技大学 信息工程学院，四川 绵阳 621010)

0 引 言

Ad-Hoc网络是一种分布式的无线网络，它不依赖任何固定的通信基础设施，在紧急情况下可通过自组织网络技术进行快速组网，且抗毁性强，在当代数字化战争、地震水灾、野外探险等领域具有良好的性能。但是，Ad-Hoc网络随着跳数的增加也带来许多严重的问题。首先，由于网络节点的移动特性使得网络拓扑以及传输路由动态多变，导致系统运算复杂且稳定性差；其次，Ad-Hoc网络节点能量有限，在许多应用场合没法及时补充或更换，网络寿命也受到严重威胁[1-2]。因此，Ad-Hoc 网络的能耗问题已成为制约其发展的主要瓶颈。如何降低节点的能耗并延长网络寿命，学者们从不同角度开展了深入研究。在实际应用中，为多跳Ad-Hoc网络选择恰当的中继进行下一跳传输是节省能量和缩短时延的有效手段。一直以来，基于位置信息的中继选择方法逐渐受到人们的青睐，这是因为在仿真时可在限制场景区域内随机生成节点坐标，这样便可计算节点之间的距离。文献[3]通过推导最佳中继节点区域包络的曲线方程，将该区域划分为具有相同误码率性能的同心圆环，同时结合中继节点和目的节点的位置来选择最佳中继节点。该方法充分利用空间分集特性来提高系统误码率性能。文献[4]为了延长网络生命周期，基于节点位置信息来构建节点发射能耗、接收能耗和剩余能量组成的代价公式，从而实现3种能量权衡下的最优中继路由选择。文献[5-7]重点考虑节点位置以及与目标节点的距离等因素来选择中继。可见，这些方法都考虑到了位置与传输距离等影响，但却忽略了重要的路径干扰等因素。后来，一些学者又重点考虑了信道状态的影响。文献[8-11]研究了基于平均信噪比的中继选择方法，即选择发送节点与中继节点链接的各条链路上的平均信噪比大于指定门限的节点作为中继，但这需要知道信道的先验知识，且采用全面估计所有中继节点的平均信噪比有较大的额外开销。在动态移动的网络拓扑以及电池寿命的影响下，效率会更低。文献[12-14]采用基于本地测量得到的瞬时信道状态信息来选择合适中继。在众多可选中继节点中决策出一条最佳中继传输路径，它不需要任何先验知识，包括网络拓扑信息和地理位置信息，也不需要在中继节点间相互通信。但最佳中继传输路径选择成功与否取决于节点对当前无线信道的即时统计信息，它是一种机会式的端到端的最佳中继选择方法，具有不稳定性特征。近年来，以节能为目标的中继节点选择算法已成为无线网络中的研究热点[15-19]。因此，本文综合考虑实际情况下信道间的相互干扰、节点之间的传输距离以及能量损耗等问题，创新地提出一种基于网络状态转换概率的中继选择算法，旨在更好地实现多跳网络的传输性能。

在实际应用的多跳Ad-Hoc网络拓扑结构中，每一跳能合作传输消息的中继节点数量是变化的，本文提出在可用的邻居节点集合中选择合适的邻居节点子集和最优活动作为下一跳的中继传输目标，同时考虑网络的能耗和时延。随着网络动态变化，其状态空间也在不断变化增加。当状态空间增大时，模仿贪心搜索和模拟退火算法，去除那些在下一传输环节有较小概率到达的节点和状态，从而精简用于运算的状态空间，达到优化中继传输性能的目的。

本文研究了多跳给Ad-Hoc网络带来的性能影响。在Ad-Hoc网络中，通过网络状态转换概率的约束在众多中继节点中选出最佳中继，因此，本文首先给出了中断概率的计算方法，然后通过中断概率计算网络状态转换概率并确定最佳中继。为了减少中继选择的复杂度，我们提出了一种有效的运算方法，即通过限制参与计算的中继节点数量来提升运算速度，同时，确保参与计算的中继节点质量以优化中继传输性能。本文的主要贡献：1)提出了网络状态转换概率的计算方法；2)提出了基于空间状态剪枝技术的复杂度削减算法；3)在减少复杂度的条件下提出了一种有效的中继选择策略。

1 网络模型

1.1 信道模型

考虑多跳Ad-Hoc网络，其节点总数为ψ，一个节点只有一个天线接口。在传统的中继协同传输过程中，其基本过程：信息从源节点s发送到目标节点t，首先源节点s向其所有邻居节点广播消息，所有收到该消息的节点再将其转发至下一跳。以此类推，合作转发不断前传直到到达终端节点t为止。可见，这种传统的广播方式将会产生很大的冗余和系统开销。本文在此基础上进行优化，采用恰当的剪枝策略获得邻居节点的“最优子集”作为转发目标，并通过译码转发(decode and forward，DF)中继协议向前转发。假设参与协同传输的“最优子集”节点数为a，则在路径损耗和衰落条件下，集合a中的节点到任意中继接收节点的传输信道模型如图1所示。在图1中，信源s首先向其最优邻居子集发送消息，邻居子集收到消息后又分别向各自的最优邻居子集继续前传，依此类推，直到最后消息经过合并到达信宿t。在译码转发的每一跳中，最优邻居子集总是选择离信宿t更近的节点作为中继，这有助于更快完成数据通信。

图1 多跳Ad-Hoc网络信道模型Fig.1 Channel model of multi-hop Ad-Hoc network

1.2 状态转换概率

本文假设网络环境为Ad-Hoc多跳网络，并在Rayleigh信道中以译码转发中继协议传送消息，且无线节点的发射功率是相同的。因各链路质量和损耗的不同，网络可能出现延迟或闪断等各种现象。因此，为了便于选择合适的网络状态，本文定义网络状态间的转换概率来描述Ad-Hoc网络的动态变化。

假设发射节点以单位带宽速率R进行传输，令无线信道的容量为C，信道的信噪比为γ，则当信道容量为

C=lb(1+γ)

(1)

当C低于速率R时就会产生中断事件[20]。设图1中任意2节点链路间的信道增益为hi,j，发射功率为pi，σ2为加性高斯白噪声功率，考虑相邻链路的相互干扰,故信噪比可表示为

(2)

则概率密度函数(PDF)可表示为

(3)

则

(4)

由此可导出Rayleigh衰落信道模型DF方式下的中断概率计算公式为

(5)

设处于当前状态x的节点集为A(x)，则a∈A(x)，令终点状态为t，x≠t，则从中断概率的定义可导出，当前跳的合作节点子集a到下一跳任意节点n的成功传输概率为1-pout(n,a)，若令θ为

(6)

则根据Markov链的性质，系统从状态x到状态y的转换概率可以定义为

(7)

如果x,y均属于终端状态t，即当x=y=t，显然有pxy(a)=ptt(a)=1。在实际网络传输过程中，转换概率取决于传输节点的相对位置以及传输信道等综合因素。

1.3 网络回报值的计算

中继网络节点的能量消耗主要包括3部分：发送、接收和空闲。通常发送功耗是主要考虑的部分，而接收和空闲时的功耗往往视为常数或忽略不计[21]。实际中，发送功耗取决于协作节点的数目以及发送消息的环境参数。本文假设能量都作归一化处理，设发送能耗为VE，时延消耗为VD，a为解析消息且协作的节点集合，m为其他解析消息非协作节点集合，此时，能耗VE可表示为

VE=|a|+ω|m|

(8)

(8)式中，参数ω≥0为调节额外节点解析消息时的开销系数。(8)式说明某一跳若同时传输的节点越多，总的发射能耗将越大，反之，则可节省系统发射功率。

时延消耗VD可认为由2部分组成。在传输路程上的时延和中继节点上排队处理的时延。排队模型如图2所示。

图2 排队模型Fig.2 Queuing model

在图2中，待传输的数据随机地来到服务机构，按一定的排队规则等待服务。在本中继系统中，中继节点为单天线，排队系统即为单通道单服务，数据到达满足泊松分布，服务时间服从指数分布，故该中继传输系统的数据包在各中继节点上的等待时间分布为[22]

Fq(w)=1-ρe-(μ-λ)w

(9)

(10)

本文设定传输路程上的时延为一常数qt，则

(11)

则系统状态x经由|a|个中继节点到达状态y的网络回报值定义为

(12)

假设当前状态x经过所有可能的路径到达状态y，则将所有的可能路径进行概率加权，寻找到达终点时耗费最少时的方程可定义为

ξ∈[0,1]

(13)

2 中继选择优化策略

2.1 复杂度削减技术

本文采用修剪网络状态空间的策略降低系统复杂度。已知处在状态x的所有节点为A(x)，邻居集为N(x)，削减不必要的和贡献率低的邻居集与行为集，即可得到新的集合A′(x)和N′(x)。显然有削减后的节点集A′(x)⊆A(x),A′(x)≠∅，邻居集N′(x)⊆N(x),N′(x)≠∅。在实际复杂度削减过程中，根据(7)式计算得出各状态转换概率pxy(a)，剪去那些传输概率较小的邻居节点，留下那些传输概率较大的路径，从而优化算法用于运算的状态空间。如此，(13)式变为

(14)

这里S表示系统所有的状态集。可定义系统从状态x到状态y的转换过程中所有被剪掉的邻居节点的最大削减概率为

(15)

那么联合(13)和(15)式可知，削减前后能量消耗值的最大差值为

(16)

由(16)式变形得到状态削减的上界

(17)

(15)式表示M(x)越小，由状态转换概率pxy得到的N′(x)以外的所有节点的概率之和越小，说明大概率的pxy已经被选入N′(x)中。因此，为了使N′(x)中的节点适当多，确定(17)式的上界M-，只要M(x)不超过M-均可。剪枝算法如Algorithm 1所示。

Algorithm 1: Reduce (x)

PROCEDURE Reduce(x)

Input:x

Output:A′(x) andN′(x)

Obtain setx′ from nodes inxclosed tot;

Obtain setA′(x) fromx′;

ψ′←ψ-x′;

k=1;v=0;V(x)=φ;

for ( eachninψ′)

v[k]←1-Pout(n,a);

k++;

end

sortascending(v);

k=1;M(x)=0;

Letm(j)∈ψ′,j=1,2,…,|ψ′|;

Repeat

ε(j)∈{0,1};

ifM(x)

V(x)←V(x)+m(k);

k++;

end

until (M(x)>M_(x) ork==|ψ′|);

obtainN′(x) fromV(x);

RETURN (A′(x),N′(x));

上述剪枝策略实现了对大量状态空间的简化运算，即每次迭代运算得到的M(x)只要超过上界M-就剔除所转状态y，否则就接受，以此得到剪枝后的邻居子集N′(x)和活动子集为A′(x)。在此方案中，上界的值将直接影响剪枝的数目，当上界取值太大，或接近状态x的所有邻居节点概率之和时，容易导致中继合作子集稀少，失败概率增大；当上界取值太小，剪枝算法将基本失效。因此，在保证成功率的前提下为了降低系统复杂度，本文参考模拟退火算法(simulate anneal, SA)做进一步优化[22]。通过对Metropolis准则的修改与运用，提出在M(x)

2.2 优化算法设计

考虑多跳中继Ad-Hoc网络状态削减上界与转换为新状态后剩余邻居节点的概率统计的差值，若削减上界小于等于网络转换到一个新状态后剩余节点的概率总计，即二者差值ΔC<0，则此状态不予接受；当ΔC≥0则以一定概率接受。由于在传统的Metropolis准则中，ΔC越小，接受的可能性越大。而在本文研究的中继传输网络中，ΔC越大，接受的可能性应该越大。因此，本文利用Metropolis的变换准则，令df=M--MX，则变换后的接受概率为

(19)

(19)式中：q表示接受概率，x,y表示系统状态，Tk表示第k时刻的温度值。变换后的Metropolis准则的执行步骤如下。

步骤1k=0时，Ad-Hoc网络所处的当前解为S(0)=x，在温度T下进行步骤2—5；

步骤2根据当前解S(k)所处的状态x，产生一个邻域子集N(S(k))⊂S,S(k)≠φ，由N(S(k))随机地得到一个新的状态y，计算剪枝上界与到达新状态y所耗费能量的差值ΔC=M--C(y)；

步骤4k=k+1执行下一次迭代，根据给定的收敛准则判断算法是否应该结束，若是则转步骤5，否则转步骤2；

步骤5返回。

基于此，本文提出了基于Metropolis变换准则的改进的模拟退火(improved simulated annealing，ISA)算法如Algorithm 2所示。ISA(S(a))旨在计算下一状态是否被接受，其工作过程如下：设置初始值init_T，如果M(S(ai))没有超过上界，以(19)式计算的接收概率qk(x,y)进行接受，以1-qk(x,y)的概率进行拒绝；超过上界的部分则直接拒绝。并在每次迭代过程中改变T值，设定T的上边界，当T按照一定斜率增长超过初始设定的terminal_T时，T将变为init_T×β。当下次迭代到来时，将继续以之前斜率增长，直到再次达到terminal_T。如此反复变换T值，通过数学分析，当迭代次数不断增加时，T将趋近于terminal_T。

Algorithm 2: ISA(S(a))

PROCEDURE ISA (S(a))

Initialize(init_T,terminal_T,discountβ);

WHILES(x) is non-terminal DO

generateTn+1fromTn,Tn+1=Tn·β;

IFTn

FOR i:=0 to |a| DO

a⊆A(S); generateai+1fromai

IFM_-M(S(ai)) ≤0 THENai∉neighborai;

ELSE IF (|1-exp{-[M_-M(S(ai))]/Ti}|)>random[0, 1) THEN

ai+1∈neighborai;

END FOR

T实质所进行的是反复渐进增加的过程，当T增大时，根据(19)式，qk(x,y)将不断变小，即会逐渐增大剔除的分支。当T变为terminal_T时，退化为一个寻求较小分支的贪婪算法。

3 数值仿真

设定网络场景为正方形区域，起点s和终点t分别位于场景两端，其余各节点的坐标在150 m×150 m的网络场景内随机生成并均匀分布。在仿真过程中，设置相关参数的初值分别为n=10,ψ=15,ω=0.5,μ=0.9,λ=0.4,ξ=0.8,initT=0.01,termianlT=10,β=1.2。

将Ad-Hoc网络的全局拓扑看作无向完全图，当网络的初始节点数为n时，则有n(n-1)/2条边。设n=10,则形成的网络状态变化可高达数万亿次。为了阐述ISA算法削减状态空间的有效性，本文在不同Δ取值情况下，验证该算法迭代1 000次计算出的平均访问状态空间数目以及算法的平均失败概率如表1所示。在表1中，实际访问状态空间数目表示了算法的计算复杂度或运算速度，平均失败概率表达了本文算法不能找到最优中继的概率。从表1可知，Δ的取值直接影响到系统运算复杂度和算法失败概率2个重要指标。通常情况下，Δ的取值越大，实际访问的状态空间数目越少，算法失败概率不断增加；Δ的取值越小，实际访问的状态空间数目越多，算法失败概率不断减少。总体情况是随着Δ的减小，访问状态数目呈增长趋势，而失败概率呈降低趋势，这是因为由(17)式可知，当Δ增大，则表示削减复杂度的上界增大，由此被剔除的状态空间就越多，而剩下用于实际访问的状态空间随之减少。但是，当Δ<1时失败概率却出现了反向增长，这说明Δ太小，会使得状态数目急剧增加反而导致某些决策失败。所以，在实际的网络设计中，需要根据需求情况在降低系统运算复杂度和降低算法失败概率方面做个权衡。本文为了平衡二者的关系，取Δ=1进行后面的仿真。

为了验证多跳Ad-Hoc网络的移动特性给系统性能带来的各种影响，图3给出了因节点移动时给系统能耗带来的变化情况。由于场景大小的变化，节点之间的距离改变，当总节点数目不变的情况下，源节点和目标节点距离越远，系统总的能耗越大。从图3可以看出，总节点数n=10和n=15时，系统的能耗在67 m处出现交叉，当它们的网络场景都小于67 m时，节点数目分布越密集，能耗越小。这是因为在小范围内，n=15时各个节点的邻居节点增加，源节点到目的节点的可选中继变得容易。当网络场景大于67 m时，节点的分布变得稀疏，受发送功率和解析消息节点数目的影响，n=15时比n=10时的系统能耗增加，此时说明，n=15时选择了更多的中继节点予以弥补场景的扩展。

表1 访问状态空间数目以及失败率

图3 场景大小与系统能耗的关系Fig.3 Relationship between the size of the scene and the energy consumption

图4给出了场景大小变化与合作节点数目之间的关系。观察图4所示，在大约67 m处，小于该场景的情况下，n=15时的合作节点数少于n=10的时候，随着场景的不断增大，总节点数目增加后合作节点数目也将随之增加，由此根据(12)式得到的能耗也将增大，这与图3的能耗关系图一致。

图4 场景大小与合作节点数的关系Fig.4 Relationship between the size of scene and the number of cooperative nodes

4 结 论

基于网络状态转换概率的中继选择策略在一定程度上解决了多跳Ad-Hoc网络环境中高冗余状态空间带来的运算复杂度问题。该策略将Metropolis准则进行适当变换，以一定概率对网络状态空间实行状态剪枝和贪心搜索，从而实现中继节点的择优选择。实验结果表明，本文提出的ISA算法对系统运算量、能耗以及成功率等指标都进行了明显优化，所提方案可为后期进一步实现最优中继传输提供可靠的技术支持。