ABSTRACT

The extremely poor performance owns to interference, attenuation, multi-path, path loss and shadowing. It makes it impossible to guarantee the quality and the reliability of the single hop communication between two nodes with long distance in mobile Ad-hoc network. The cooperative diversity could be achieved to counterbalance the above affects, once the multi-hop virtual multi-antenna system was implemented with the aid of clustering the nodes. In terms of the static and dynamic clustering, this paper analyzed the characteristics of clustering schemes, according to the exploration of the mutual information accumulation with the aid of distributed space-time coding for dynamic clustering, in the light of the investigation of clustering schemes based on signal to noise ratio and Viterbi algorithm. On the basis of current achievement on theory and practice of clustering techniques and their essential relation, the proposals for future research and development were presented.

Keywords:Mobile Ad-hoc Network, Multi-Hop, Cooperative Diversity, Clustering

无线多跳网络中分簇算法的研究进展
和未来前瞻

高  莹，倪梁方^*，陈建建

安徽工业大学电气与信息工程学院，马鞍山

Email: gaoying901111@163.com, ^*nilf@njupt.edu.cn, 553913401@qq.com

收稿日期：2014年9月27日；修回日期：2014年10月18日；录用日期：2014年10月30日

摘  要

受干扰、衰落、多径、路径损耗和阴影等因素制约，当移动Ad-hoc网络中两个节点间的距离较远时，两者间通过单跳方式无法保证高质量的可靠通信。若在该网络中通过节点分簇建立多跳虚拟天线阵列，实现协同分集，就可以有效应对上述不利影响。本文从静态和动态两个方面，在研究了基于信噪比和基于维特比算法分簇方案的基础上，进一步探讨了动态分簇对利用编码存储互信息的需求，详细分析了分簇方案的特性，并依据现阶段分簇技术在理论和实践两方面取得的主要成果及二者之间的本质联系，对未来的研究和探索提出了建议。

关键词

移动Ad-hoc网络，多跳，协同分集，分簇

1. 引言

无线Ad-hoc网络中，由于受到干扰、衰落、多径、路径损耗和阴影等因素的影响，通过在信源信宿之间建立独立信道实现协同分集是抑制此类不利影响的有效方案[1] 。然而，移动Ad-hoc网络中，各个移动节点以半双工模式(即不能同时发送和接收)，并基于窄带信道传输信号，无法有效利用时间和频率分集。此外，节点天线的尺寸体积和电池持续时间的限制也阻碍了天线提供空间分集的可能性[2] 。如果，基于单天线节点分簇建立虚拟天线阵列，通过多跳协同传输数据包，就可以有效地避免符号间干扰和因错误传输引起的信噪比损失，达到提高协同分集度和改善通信链路性能的目的。为此，协同网络中的节点的分簇方案就成为众多学者研究的热点。

协同网络中的分簇方案[1] -[5] 主要有两种：静态分簇和动态分簇[3] 。在静态分簇方案中所有簇内节点同步参与发送和接收数据，节点在传输过程中可看作是静止的，即没有节点加入和离开簇。其中，Lingya Liu, A.H. Bastami等针对单跳通信中信源和中继、中继和信宿间信道增益不平衡，每跳都会成为整个通信瓶颈的问题，从组合优化[1] 和阈值门限设定[2] 两个方面提出了基于信噪比的分簇方案；Qimin You等通过将网络中的多跳中继映射成卷积码网格，采用维特比算法来选择端到端信噪比最大的路径，提出了基于维特比算法的分簇方案。而动态分簇方案[6] -[14] 中接收到数据包的节点即可加入分簇，之后依据对数据的有效编码存储积累节点之间的互信息(mutual information accumulation, MIA) [12] [14] 完成数据的传输。为此，本文从静态和动态两个方面，在研究了基于信噪比和基于维特比算法分簇方案的基础上，进一步探讨了动态分簇对利用编码存储互信息的需求，详细分析了分簇方案的特性。

目前大多数分簇协同通信网络中，中继都是采用基于重传的放大转发或解码前馈策略传递信源信息，以降低带宽效率和严重损耗信噪比为代价，实现满分集。若节点在中继信息前，利用分布式空时编码的传递信息，并实现满分集，可以避免由单纯的重传方式引起的不利影响[15] -[17] 。由于无线Ad-hoc协同通信网络的分布式特性，所以分布式编码设计中，构成完整码字的各个部分由不同的节点产生，并通过不同的无线链路进行传输。因此将信道编码和空时编码设计的概念应用于无线中继网络的同时，必须要考虑若干实际问题，例如中继存在译码错误、码字的多个组成部分分别经历不同的信道衰落、源节点和中继处的码率与概率分配等。最近，陆续提出了基于动态分簇下互信息积累设计的分布式空时编码方案[14] ，保证异步协同传输环境下的满分集性能的分布式时延空时码方案[18] ，应用于全双工(FD)工作模式下的部分分布式线性卷积空时编码方案(部分DLC-STC) [19] [20] 等许多新的分布式编码方案。然而，在基于分簇的无线多跳网络中，节点分簇完成以后，将单条直接链路分解成多条较短的链路，中继以多跳的方式转发数据时采用分布式空时编码实现数据重构的研究仍有待进一步的探索。为此，本文依据现阶段分簇技术在理论和实践两方面取得的主要成果及二者之间的本质联系，对未来的研究和探索提出了建议。

2. 静态分簇算法

若一个移动Ad-hoc网络中有一个信源节点、一个信宿节点、若干个移动中继节点且各个移动节点工作在半双工模式，即不能同时发送和接收；那么，协同通信时，一个中继信道发送周期分为两个阶段：1) 信源向中继和信宿广播信息；2) 信源停止广播；静态分簇算法基于同步发送和接收数据的准则构建虚拟阵列实现空间分集，其主要的方案有以下几种。

2.1. 基于信噪比的分簇算法

2.1.1. 组合优化分簇法

该算法根据移动节点的信道特征 (这里;)诱导的信道增益，形成基于信噪比的约束

(1)

式中和分别表示第1、2跳分簇节点集合。进而，将选择若干潜在节点构建分簇的问题转为组合优化中的背包问题

(2)

式中若，则第个节点参与协同；而，则第个节点不参与协同。并按照网络层的要求

(3)

自适应地调节协同节点数目，从而以最佳的组合方式实现信号的多跳传输。式(3)中，“”表示集合的基数。然而，经典优化算法需借助穷举法才能获得最优分簇方案；当网络节点数较多时，这是一个非多项式(NP)问题，实时性较差。

2.1.2. 阈值门限分簇法

若采用由 (这里是自然数)表示的离散时间基带等效信号模型，则第一跳时，则第个中继节点的接收信号为

(4)

式中表示信源到第个中继节点的信道衰落系数，是第个中继节点处的加性高斯白噪声，是信源的调制信号，是信源的比特传输能量，是网络中可能作为中继的个数。

第二跳时，信宿的接收信号为

(5)

式中是由第个中继节点处的估值诱导的空时编码信号，是分配给第个中继节点的比特传输能量，是表示第个节点在第二跳是否参与中继的随机变量，且

(6)

此外，分配给信源和中继节点的总比特传输能量为。

如前所述，仅当移动节点的瞬时接收信噪比大于给定的阈值，才在第二跳前馈信息。由于第个中继节点处的接收信噪比与信源到中继的信道系数成比例，因此可以简单地将与给定的阈值比较后，决定是参与中继还是保持静默。显然，是以为参数的指数分布随机变量，即

(7)

于是，第个中继节点在第二跳前馈信息的概率可表为

(8)

2.2. 基于维特比算法的分簇算法

在无线Ad-hoc网络中，若表示联接簇的第个中继与簇的第个中继的分支，分支序列表示路径(这里,)，为联接簇与簇的分支数目，表示网络中总的路径数，则基于维特比算法中继选择的目标是在预设复杂度约束条件下，从条路径中搜索具有最大的端到端信噪比的跳路径。

若表示分支的信道增益，且所有节点以相同的功率传输信号，则每个节点的相应的

瞬时信噪比SNR为，每个节点的平均信噪比为 (这里为加性高斯白噪声

(additive white Gaussian noise, AWGN)的功率谱密度)。

假设表示路径的等效信噪比，则它满足如下约束条件

(9)

且有

(10)

随后，该算法沿着路径方向搜索式(9)所示和式的最小值。这类似于卷积码的维特比译码算法沿着路径方向，搜索平方欧氏距离为路径度量的累积和的最小值。

该方案以差错概率度量性能优劣，如果接收信噪比低于给定的阈值，传输信号会出现差错。于是，第条路径上出现差错的概率为

(11)

式(11)表明路径差错概率取决于该条路径上传输条件最差的分支的瞬时信噪比。

由于式(9)和(10)是渐进紧的，因此，在高信噪比条件下，每条路径的分支的瞬时信噪比倒数和是路径的积累SNR的逆的紧的下界，即由此诱导的中继路径是近似最优的协同路径。

3. 动态分簇算法

动态分簇时，节点可以随时加入或离开正在传输的分簇，一旦接收到数据包，就可以参与协同传输。首先，将数据包中信源信息编为一系列码字，并传输至中继。随后，中继节点根据接收码字集合的互信息积累(mutual information accumulation, MIA) [12] -[14] 的大小决定是否译码。节点完成的译码之后，重新编码，并加入分簇传输数据。每个节点用b秒传输一个数据分组。

文献[8] 中动态分簇通过传统的增量冗余固定速率编码方案[9] 获得互信息积累。由于无线网络环境的变化导致固定设计的应用效果不好，M. Lub提出可变速率的编码方案[10] [11] 来获得动态分簇所需的互信息积累[12] [13] 。然而，文献[12] [13] 是基于确定信道模型不考虑信道衰落情况下的分析。为此，有待进一步探讨随机信道下该方案的实现。

由于动态分簇实现过程复杂，现阶段的研究大多仅局限于对编码方式的改进，而对于节点的选择成簇的研究尚未取得太多实质性的进展。限于篇幅，本文暂且不对动态分簇过程中将信源信息编成码字的方案作更为详细的阐述。

4. 未来前瞻

通过前文阐述的分簇算法对无线Ad-hoc网络中的中继节点分簇，形成虚拟天线阵列，从而实现类似于MIMO中的协同分集，而中继节点主要采用解码前馈[15] -[17] 中基于重传的方式转发信源信息[16] ，需要为每个中继分配相互正交的子信道，这种方式虽然可以获得满分集，但是会导致带宽效率降低，且信噪比的损耗随中继节点指数变化。然而，若采用解码前馈中的基于分布式空时编码的方式，各个中继可以在相同的子信道上传输信息，实现满分集时，其信噪比仅随中继节点线性衰减[16] 。因此，在中继采用解码前馈策略时中应用分布式空时编码技术正在逐渐受到重视。

文献[18] 利用完备码的循环可除代数理论，构造与同步环境下完备码具有相同特性的分布式时延空时码，保证异步协同传输环境下的满分集性能。维数为的分布式时延空时码的由哈达玛码字矩阵诱导而来。

(12)

式中为构建分布式时延空时码中对应的码字

(13)

式中，为选择星座集中的符号矢量。为由,张成的维的复酉矩阵

(14)

式中表示克罗内克积。

假设一个伽罗华域，分别在两个域进行扩张，即，。式(14)中,为二者分别对应的生成矩阵

(15)

(16)

式中，是归一化因子，保证，是酉阵，为映射运算。

为保证该分布式时延空时码与同步环境下完备码具备相同的性能，对式(12)中的限定是构建码的关键。

分布式时延空时码方案与同步环境下完备码具有相同特性，保证异步协同传输环境下的满分集性能，有效避免了移动Ad-hoc网络由节点高速流动难以同步的特性而引起的中继信道掉线，系统的分集程度受损。

文献[19] [20] 提出进行部分分布式线性卷积空时编码(partial distributed linear convolutional space-time coding, partial DLC-STC)方案。全双工模式下，由单个中继节点处输入输出间的信号溢出产生环路自干扰和多个中继节点输入输出间的串扰干扰，会严重影响系统性能。Partial DLC-STC方案对上述两类干扰的一部分进行消除，而另一部分作为信道信息做自编码，实现协同满分集。信宿接收信号可表为

(17)

式中，为信源到中继节点的信道，为中继环路信道，中继到信宿的信道，信源到信宿之间的信道，是信源发送的归一化能量为1的信号，是信宿处的加性噪声，是中继处的加性噪声，均满足服从，是中继节点处的放大因子，是时延，是环路干扰违背删除的部分，由中继节点在时刻的发送信号

(18)

可知中的为消除系数，当且仅当时，认为是完全环路干扰消除。因此在部分删除干扰的前提下，通过调节放大因子，决定空间分集的程度。从中继节点的接收信号中的存在环路干扰，因此删除部分接收信号，由此根据时刻中继节点在的接收信号

(19)

诱导出式(18)中继节点在时刻的发送信号。

根据文献[21] 中提出的分布式线性卷积空时编码，在码字间引入保护间隔避免相邻码字间的干扰。中继处的经分布式线性卷积空时编码的信号为

(20)

式中是信道矩阵，是噪声，有效编码矩阵需要满足在不同时延下都是满秩的。因此，通过式(21)表示的生成矩阵来设计分布式线性卷积空时码，使得对所有的刻画时延的变量，都是满秩的。

(21)

式中是的行矢量，为移位满秩(Shift-FullRank, SFR)矩阵。

全双工模式中一个中继节点只需要一条信道完成端到端传输，因此相比半双工模式，具有较高的频谱利用率，同时系统容量也获得相应改善。采用部分分布式线性卷积空时编码方案，能够明显降低由环路自干扰引起的错误概率。

虽然利用分布式空时编码实现异步协同满分集增益，可以提升传输数据速率，改善链路性能，在系统的信道容量，能量损耗，传输错误概率方面展现出一定的优势。但是当前提出的分布式空时编码方案大多局限性于单跳的分簇协同通信网络，理论证明，在排除一切技术难题的基础上，上述分布式时延空时码方案的异步特性可以更好地缓解多跳传输中对同步尤其敏感的问题，另外，由多跳传输引起的更加严重的传输干扰，也可以利用部分分布式线性卷积空时编码(partial DLC-STC)方案来解决。遗憾的是，分布式空时编码在分簇协同通信的多跳传输中的应用研究尚属刚刚起步阶段，各方面的成果还并不成熟。但其目前所得到的广泛关注度，让笔者有理由相信笔者深信随着新一代无线通信技术的不断发展，必将会有更多更新的技术方案应用到多跳协同通信网络中，为这一关键领域的研究注入新的活力，从而促进该领域研究的快速发展。

5. 结束语

本文从静态和动态两个方面，阐述了分簇方案的特性。从组合优化、阈值门限设定和网络映射三个不同侧面详细分析了静态分簇原理；并基于分布式空时码存储互信息积累和数据包传输速率两个层面，探讨了动态分簇方案的性能。

这为进一步探索新的分簇方案奠定了基础。此外，在众多理论分析的支持下，构建基于分布式空时编码的多跳异步协同通信系统是笔者将要待探讨的下一个课题。

致  谢

作者对安徽省自然科学基金(11040606M125)在本课题研究过程中给予的资助，表示感谢。

参考文献 (References)

NOTES

^*通讯作者。