文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2018, Vol. 30 Issue (6): 752-759  DOI: 10.3979/j.issn.1673-825X.2018.06.004
0

引用本文 

陈春梅, 吴斌, 江虹. Ad-Hoc网络中基于状态转换概率的中继选择算法研究[J]. 重庆邮电大学学报(自然科学版), 2018, 30(6): 752-759. DOI: 10.3979/j.issn.1673-825X.2018.06.004.
CHEN Chunmei, WU Bin, JIANG Hong. Research on relay selection algorithm based on state transition probability in Ad-Hoc networks[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2018, 30(6): 752-759. DOI: 10.3979/j.issn.1673-825X.2018.06.004.

基金项目

国家自然科学基金(F010106)

通信作者

陈春梅 ccm@swust.edu.cn

作者简介

陈春梅(1977—),女,四川广安人,西南科技大学信息工程学院副教授,研究方向为网络通信与路由技术、移动互联网与信息处理技术、认知无线传输与组网技术。E-mail:ccm@swust.edu.cn; 吴斌(1965—),男,四川达州人,西南科技大学信息工程学院教授,研究方向为自动控制理论、图像处理与模式识别、智能控制、人工智能及其应用、人工生命等; 江虹(1969—),男,重庆人,西南科技大学信息工程学院教授,研究方向为无线通信、现场网络化应用及智能优化技术。

文章历史

收稿日期: 2017-11-15
修订日期: 2018-09-06
Ad-Hoc网络中基于状态转换概率的中继选择算法研究
陈春梅1,2, 吴斌2, 江虹2     
1. 中国工程物理研究院 电子工程研究所,四川 绵阳 621900;
2. 西南科技大学 信息工程学院,四川 绵阳 621010
摘要: 在多跳Ad-Hoc网络中,随着节点的增加以及传输跳数的变化,网络状态数目将不断增大,随之带来的路由计算将变得十分复杂,从而严重影响系统的整体性能。如何在海量的网络转换状态形势下,快速选择最有效的状态进行下一跳数据传输是关键。创新地提出了基于状态转换概率的中继选择策略,结合节点地理信息和信道环境信息计算出邻居节点可能的到达概率,并选择概率大者进行数据传输,从而提高数据传输性能。同时,为了降低系统运算复杂度并节省系统能量,采用了变换的metropolis选择准则,以模拟退火的贪心搜索逐级去除那些小概率的传输状态,从而大幅度降低了运算空间。仿真给出了算法参数对运算速度与成功率的影响。同时,也表明了该算法在网络拓扑变化时对系统能耗和失败概率的增长均有较好的控制。
关键词: 多跳Ad-Hoc网络    中继选择    状态转换概率    模拟退火    
Research on relay selection algorithm based on state transition probability in Ad-Hoc networks
CHEN Chunmei1,2 , WU Bin2 , JIANG Hong2     
1. Institute of Electronic Engineering, China Academy of Engineering Physics, Mianyang 621900, P.R. China;
2. School of Information Engineering, Southwest University of Science and Technology, Mianyang 621010, P.R. China
Foundation Items: The National Natural Science Foundation of China (F010106)
Abstract: In the multi-hop Ad-Hoc networks, the number of network states will increase as the number of hops and nodes increases. Then, the computation will become very complicated and the system performance will be affected seriously. In the condition of massive network states, it is crucial to choose the most effective state to the next hop. So, we innovatively propose the relay selection strategy based on the state transition probability. First, we compute the transition probability of each neighbor according to the geographic information and channel environment information. After that, the state with max transition probability will be selected as the next transmission state. Thus, the system performance can be improved. In order to reduce the state space and save system energy, we adopt the transformed Metropolis criterion and remove the states with small probabilities by the greedy search of simulated annealing. The simulation gives the influence on the operation speed and the success rate with the algorithm parameter setting. At the same time, it also shows that the algorithm can control the growth of the energy consumption and the failure probability when the network topology changes.
Keywords: multi-hop Ad-Hoc networks    relay selection    state transition probability    simulated annealing    
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网络信道模型 Figure 1 Channel model of multi-hop Ad-Hoc network
1.2 状态转换概率

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

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

$ C = {\rm{lb}}\left( {1 + \gamma } \right) $ (1)

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

$ \gamma = \left( {{p_i}{h_{i,j}}} \right)/\left( {\sigma _{i,j}^2 + \sum\limits_{k \in \psi ,k \ne i} {\left( {{p_k}{h_{k,j}}} \right)} } \right) $ (2)

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

$ \begin{array}{l} {f_{\rm{H}}}\left( x \right) = \frac{x}{{\sigma _{i,j}^2 + \sum\limits_{k \in \psi ,k \ne i} {{P_k}{h_{k,j}}} }}\exp \cdot \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\left( { - \frac{{{x^2}}}{{2\left( {\sigma _{i,j}^2 + \sum\limits_{k \in \psi ,k \ne i} {{P_k}{h_{k,j}}} } \right)}}} \right) \end{array} $ (3)

$ \begin{array}{l} F\left( x \right) = \int\limits_{ - \infty }^\infty {{f_{\rm{H}}}\left( x \right){\rm{d}}x} = \\ \;\;\;\;\;\;\;1 - \exp \left( { - \frac{{{x^2}}}{{2\left( {\sigma _{i,j}^2 + \sum\limits_{k \in \psi ,k \ne i} {{P_k}{h_{k,j}}} } \right)}}} \right) \end{array} $ (4)

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

$ \begin{array}{l} {P_{{\rm{out}}}} = {P_{\rm{r}}}\left( {C < R} \right) = P\left\{ {{\rm{lb}}\left( {1 + \gamma } \right) < R} \right\} = \\ \;\;\;\;\;\;\;\;P\left\{ {\gamma < {2^R} - 1} \right\} = F\left( {{2^R} - 1} \right) = \\ \;\;\;\;\;\;\;\;1 - \exp \left( { - \frac{{{{\left( {{2^R} - 1} \right)}^2}}}{{2\left( {\sigma _{i,j}^2 + \sum\limits_{k \in \psi ,k \ne i} {{P_k}{h_{k,j}}} } \right)}}} \right) \end{array} $ (5)

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

$ \theta = \left\{ {\begin{array}{*{20}{c}} {1,}&{n \in y,n \notin x}\\ {0,}&{n \notin y} \end{array}} \right. $ (6)

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

$ {p_{xy}}\left( a \right) = \prod\limits_{n \in \psi } {{{\left( {1 - {p_{{\rm{out}}}}\left( {n,a} \right)} \right)}^\theta }{{\left( {{p_{{\rm{out}}}}\left( {n,a} \right)} \right)}^{1 - \theta }}} $ (7)

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

1.3 网络回报值的计算

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

$ {V_{\rm{E}}} = \left| a \right| + \omega \left| m \right| $ (8)

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

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

图 2 排队模型 Figure 2 Queuing model

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

$ {F_q}\left( w \right) = 1 - \rho {{\rm{e}}^{ - \left( {u - \lambda } \right)w}} $ (9)

平均等待时长为${{W}_{\text{q}}}=\frac{\rho }{\mu -\lambda }$,其中,μ为发送速率,λ为到达速率,ρ为系统利用率,即$\rho =\frac{\lambda }{\mu }$。因此,总排队处理时间为

$ {W_{\rm{q}}} = \left| a \right|\frac{\rho }{{\mu - \lambda }} $ (10)

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

$ {V_D} = {q_t} + \left| a \right|\frac{\rho }{{\mu - \lambda }} $ (11)

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

$ \begin{array}{l} V\left( {x,\alpha ,y} \right) = {V_{\rm{E}}} + {V_{\rm{D}}} = \\ \left| a \right| + \omega \left| m \right| + {q_t} + \left| a \right|\frac{\rho }{{\mu - \lambda }} \end{array} $ (12)

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

$ \begin{array}{*{20}{c}} {{J^ * }\left( x \right) = {{\min }_{a \in A}}\left[ {\sum\limits_{y \in N\left( x \right)} {{p_{xy}}\left( a \right)\left( {v\left( {x,a,y} \right) + \xi J\left( y \right)} \right)} } \right],}\\ {\xi \in \left[ {0,1} \right]} \end{array} $ (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)式变为

$ {J_{p'}}\left( x \right) = \mathop {\min }\limits_{a \in A'\left( x \right)} J_{P'}^ * \left( {x,a,J} \right),x \in S $ (14)

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

$ M\left( x \right) = \mathop {\max }\limits_{a \in A'\left( x \right)} \left[ {\sum\limits_{y \in N\left( x \right)\backslash N'\left( x \right)} {{p_{xy}}\left( a \right)} } \right] $ (15)

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

$ \Delta \left( x \right) = M\left( x \right)\left[ {{V_{\max }} + \xi {{\max }_{x \in S}}\bar J\left( x \right)} \right] $ (16)

(16) 式中,J(x)是状态x的开销估计。在算法执行过程中,当Δ(x)=0时,表示M(x)为0,即状态xy之间没有节点变化,则不剪枝,当Δ(x)>0时,进行迭代剪枝。

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

$ {M_ - } = \frac{{\Delta \left( x \right)}}{{{V_{\max }} + \xi {{\max }_{x \in S}}\bar J\left( x \right)}} $ (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) and N′(x)

    Obtain set x′ from nodes inxclosed tot;

    Obtain set A′(x) from x′;

    ψ′←ψ-x′;

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

for (each n in ψ′)

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

    k++;

end

sortascending (v);

k=1;M(x)=0;

${{M}_{-}}\left( x \right)=\frac{\Delta \left( x \right)}{{{V}_{\max }}+\xi {{\max }_{x\in S}}\bar{J}\left( x \right)}$;

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

Repeat

    M(x)=M(x)(1-v(k))+ $\prod\limits_{j=1}^{k}{v{{\left( j \right)}^{\varepsilon \left( j \right)}}{{\left( 1-v\left( j \right) \right)}^{1-\varepsilon \left( j \right)}}}$, ε(j)∈{0, 1};

    if M(x) < M_(x) then

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

        k++;

    end

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

obtain N′(x) from V(x);

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

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

2.2 优化算法设计

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

$ {q_k}\left( {x,y} \right) = \left\{ {\begin{array}{*{20}{c}} {0,}&{若\;{\rm{d}}f < 0}\\ {\left| {1 - \exp \left( { - \left[ {\frac{{{\rm{d}}f}}{{{T_k}}}} \right]} \right)} \right|,}&{若\;{\rm{d}}f \ge 0} \end{array}} \right. $ (19)

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

步骤1  k=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);

步骤3  若ΔC≤0,则表示能耗超过上界,直接拒绝;若ΔC>0,产生随机数randrandom[0, 1),若接收概率qk=$1-\exp \left(-\frac{\Delta C}{KT} \right)>rand$,则接收y为下一个当前解。此时,若接收了新状态y,则令S(k+1)=y,否则,S(k+1)=x

步骤4  k=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 β);

    WHILE S(x) is non-terminal DO

        generate Tn+1 from Tn, Tn+1=Tn·β;

        IF Tn < terminal_T THEN init_T=init_T·β; Tn=init_T

        FOR i:=0 to |a| DO

        aA(S); generate ai+1 from ai

        IF M_-M(S(ai)) ≤0 THEN aineighborai;

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

           ai+1neighborai;

        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进行后面的仿真。

表 1 访问状态空间数目以及失败率 Table 1 Number of access state spaces and failure rate

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

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

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

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

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

参考文献
[1]
高会元.无线自组网络中基于能量的路由协议的研究[D].石家庄: 河北科技大学, 2015.
GAO Huiyuan. Research on the routing protocols based energy in wireless ad hoc networks[D]. Shijiazhuang: Hebei University of Science and Technology, 2015. http://cdmd.cnki.com.cn/Article/CDMD-10082-1015314851.htm
[2]
WANG Y L, MEI S, WEI Y F, et al. Improved ant colony-based multi-constrained QoS energy-saving routing and throughput optimization in wireless Ad-hoc networks[J]. The Journal of China Universities of Posts and Telecommunications, 2014, 21(1): 43-53. DOI:10.1016/S1005-8885(14)60267-3
[3]
孙利娟, 张歌凌. 协作中继节点选择的动态地理协作路由算法[J]. 计算机工程与设计, 2017, 38(2): 281-286.
SUN Lijuan, ZHANG Geling. Dynamic geographic cooperative routing algorithm for cooperative relay node selection[J]. Computer Engineer and Design, 2017, 38(2): 281-286.
[4]
周雷, 苏红, 唐昊, 等. 基于位置信息的无线网络协作路由算法[J]. 电子测量与仪器学报, 2015(5): 708-716.
ZHOU Lei, SU Hong, TANG Hao, et al. Wireless network cooperative routing algorithm based on location information[J]. Journal of electronic measurement and instrument, 2015(5): 708-716.
[5]
孙文胜, 姚劲松, 唐幸乐.最近中继协作算法研究[C]//浙江省电子学会2014学术年会论文集.杭州: 杭州电子科技大学学报: 自然科学版, 2014.
SUN Wensheng, YAO Jinsong, TANG Xinle. The nearest relay collaboration algorithms research[C]//Zhejiang Institute of Electronics 2014 academic annual conference papers. Hangzhou: Journal of Hangzhou Dianzi University : Natural Science, 2014. http://cpfd.cnki.com.cn/Article/CPFDTOTAL-ZJDZ201411001018.htm
[6]
NIELSEN J J, OLSEN R L, MADSEN T K, et al. Optimized Policies for Improving Fairness of Location-Based Relay Selection[C]//2013 IEEE 77th Vehicular Technology Conference. Dresden: Institute of Electrical and Electronics Engineers, 2013, 14(2382): 1-5. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6692681
[7]
BAŞTÜRK İlhan, ÖZBEK B. Distance based selection for user-relaying in OFDMA-based wireless networks[C]//Signal Processing and Communication Application Conference. Zonguldak: IEEE Press, 2016: 989-992. http://ieeexplore.ieee.org/document/7495908/
[8]
陈勤, 芮贤义. SR门限中继选择算法研究[J]. 计算机工程与应用, 2014, 50(7): 221-224.
CHEN Qin, RUI Xianyi. Research on the relay selection algorithm based on SR threshold[J]. Computer Engineering and Application, 2014, 50(7): 221-224. DOI:10.3778/j.issn.1002-8331.1205-0024
[9]
肖海林, 胡悦, 闫坤, 等. 多源-多中继协作通信的中继选择与功率分配[J]. 北京邮电大学学报, 2017, 40(2): 73-78.
XIAO Hailin, HU Yue, YAN Kun, et al. Relay selection and power allocation in multi source- multi relay cooperative communication[J]. Journal of Beijing University of Posts and Telecommunications, 2017, 40(2): 73-78.
[10]
李亦波.中继选择策略及功率优化分配算法研究[D].重庆: 重庆大学, 2016.
LI Yibo. Research on the relay selection strategy and power optimal allocation algorithm[D]. Chongqing: Chongqing University, 2016. http://cdmd.cnki.com.cn/Article/CDMD-10611-1016731332.htm
[11]
胡锦丽, 余根坚. 基于协作分集技术的无线传感器网络传输性能[J]. 四川大学学报:自然科学版, 2016, 53(6): 1261-1268.
HU Jinli, YU Genjian. Transmission capacity of wireless sensor networks based on cooperative diversity[J]. Journal of Sichuan University:Natural Science Edition, 2016, 53(6): 1261-1268.
[12]
阳俐君, 曹张华, 张士兵, 等. 单窃听双跳协作网络的中继选择方案及其性能分析[J]. 重庆邮电大学学报:自然科学版, 2016, 28(5): 648-657.
YANG Lijun, CAO Zhanghua, ZHANG Shibing, et al. Relay selection schemes for dual-hop cooperative networks with an eavesdropper and their performance analysis[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2016, 28(5): 648-657.
[13]
赵玉丽, 郭丽, 朱志良, 等. 协作通信中一种中继节点选择方案的设计[J]. 计算机应用, 2015, 35(1): 1-4.
ZHAO Yuli, GUO Li, ZHU Zhiliang, et al. Relay node selection scheme in cooperative communication[J]. Journal of Computer Application, 2015, 35(1): 1-4.
[14]
覃彩玲, 肖琨. 基于预测信噪比的中继选择算法及性能分析[J]. 计算机工程与设计, 2016, 37(12): 3196-3200.
QIN Cailing, XIAO Kun. Relay selection algorithm based on predictive signal-to-noise ratio and performance analysis[J]. Computer Engineering and Design, 2016, 37(12): 3196-3200.
[15]
WANG L J, HAN T. The Relay Selection Algorithm Based on Minimizing the User Terminal Energy Consumption[C]//International Conference on Wireless Communication and Sensor Network. Wuhan: IEEE Press, 2014: 270-275. http://dx.doi.org/10.1109/WCSN.2014.62
[16]
齐小刚, 董海俊. 基于休眠的无线传感器网络机会路由中继节点选择[J]. 信号处理, 2017(s1): 58-64.
QI Xiaogang, DONG Haijun. Opportunistic routing relay node selection based on hibernation in wireless sensor network[J]. Journal of Signal Processing, 2017(s1): 58-64.
[17]
LUO J, HU J, WU D, et al. Opportunistic Routing Algorithm for Relay Node Selection in Wireless Sensor Networks[J]. IEEE Transactions on Industrial Informatics, 2017, 11(1): 112-121.
[18]
刘杰群, 陈瑾, 任国春, 等. 能量收集全双工中继网络中的中继选择策略研究[J]. 信号处理, 2017, 33(1): 116-125.
LIU Jiequn, CHEN Jin, REN Guochun, et al. Research on Relay Selection Strategy of Energy Harvesting Full-Duplex Relay Network[J]. Journal of Signal Processing, 2017, 33(1): 116-125.
[19]
丁长文, 杨霖, 李高祥. 能量收集双向中继网络的高能效联合中继选择和功率分配算法[J]. 电子学报, 2017, 45(5): 1124-1129.
DING Changwen, YANG Lin, LI Gaoxiang. Energy efficient relay selection and power allocation for energy harvesting two-way relay network[J]. Acta Electronica Sinica, 2017, 45(5): 1124-1129. DOI:10.3969/j.issn.0372-2112.2017.05.015
[20]
ROSSI M, TAPPARELLO C, TOMASIN S. On Optimal Cooperator Selection Policies for Multi-Hop Ad Hoc Networks[J]. IEEE Transactions on Wireless Communications, 2011, 10(2): 506-518. DOI:10.1109/TWC.2011.120810.091560
[21]
YU T, LIN H M A, Hong T, et al. Power Allocation and Routing Algorithm in Multihop Cooperative Relaying Networks[J]. Transactions of Beijing Institute of Technology, 2013, 33(12): 1247-1252.
[22]
唐加山. 排队论及其应用[M]. 北京: 科学出版社, 2016: 35-90.
TANG Jiashan. Queuing theory and its application[M]. Beijing: Science Press, 2016: 35-90.
[23]
尹文也, 何伟基, 顾国华, 等. 模拟回火马尔可夫链蒙特卡罗全波形分析方法[J]. 物理学报, 2014, 63(16): 164205-164215.
YIN Wenye, HE Weiji, GU Guohua, et al. A full waveform analysis approach based on the simulated tempering Markov chain Monte Carlo method[J]. Acta Physica Sinica, 2014, 63(16): 164205-164215. DOI:10.7498/aps.63.164205