采用喷泉码的无线协同多跳信息累积广播协议

(解放军理工大学 通信工程学院，南京 210007)

1 引 言

在无线网络中，广播作为一种可以将信息从源节点发送到多个目的节点的传输方式，在多跳网络通信中起着重要的作用。广播方案的效率受多种因素影响，如系统的可靠性、能量效率、可扩展性、复杂度和延时等。针对不同的场合，不同因素所起的作用也不一样，如在广播流媒体时，延时是需要重点考虑的因素；当网络中的节点要更新软件时，传输的可靠性就显得十分重要。

在无线通信系统环境中，系统中节点的能量是受限的，因此降低系统的能量消耗显得十分重要，它已经成为广播协议的一个研究热点。Maric提出利用无线组播优势，节点可以接收可靠传输范围以外的信息，并进行信息的累积，系统通过获得分集增益来提高能量效率[1]。Kailas提出了带有判决门限的机会大阵列协议[2]，通过对接收信号信噪比的检测，系统只允许在下一次传输中发挥作用较大的节点进行发送，发挥作用较小的节点不发送。这种算法在节点密度较高的环境下适用，当密度节点较低时系统性能将受影响。

在广播通信中，一个节点发送数据，N个目的节点接收数据。如果有目的节点没有成功接收，为保证传输的可靠性，则发送节点需要重新发送。没有成功接收的节点通过反馈告知发送节点它需要哪些数据，由发送节点对应发送。由于通常这些未成功译码目的节点所需重传的数据是不同的，源节点向某一个节点重传的数据对于其它节点来说是没有用的，这样就浪费了系统资源。喷泉码的出现很好地解决了这个问题[3-5]。源节点的数据通过喷泉编码可以产生远大于原信息长度的编码信息，它发送的编码信息对于每一个没有成功译码的接收节点都是有用的。此外，喷泉码可以自适应信道链路状态，无需信道状态反馈信息就可以达到信道容量，因此考虑到将喷泉码引入到广播传输系统中来提高系统的能量效率。

本文提出了采用喷泉码的信息累积传输协议：接收节点利用可靠传输范围之外的信息，直至接收节点积累的信息量可以成功译码。根据节点是否拥有网络的全局链路信息，给出了集中式信息累积协议和分布式信息累积协议，并将提出的这两个协议与现有的能量累积广播协议进行了比较。

2 系统模型

在信息累积广播协议中，系统所需的最小能量可以通过两方面来实现，首先要确定由哪些节点进行转发，然后再确定节点的发送功率。这个问题与最小能量广播问题相似。在最小能量广播问题中，若广播树确定，则发送功率也就确定了[8-9]。广播树中一个父节点的发送功率由到达它所在组中信道质量最差的子节点决定，但是在信息累积广播中，节点从很多其它发送节点接收信息，节点之间没有明确的父节点和子节点的关系。除此以外，节点的发送功率的最优解可能不是正好使某个节点成功接收的功率值，因为这个接收节点还可以从将来发送的节点接收到所需信息。

信息累积广播协议最为关键的步骤是确定发送节点的发送次序，然后根据这个发送次序进行线性规划，确定节点的最优发送功率。文献[1]中指出寻找这样一个最优次序是不可实现的，基于此，下面就给出两种典型场景下的启发式算法。

3 集中式信息累积广播协议(CIABP)

在CIABP协议中，假设所有信道增益系数的信息在各个节点处都是已知的，还要求每一个成功译码节点的注水速率都是已知的，并且节点发送的功率可以确定，恰好使一个未成功译码节点在一个时隙内成功接收。网络中成功译码的节点集合记为S，如果节点j是在S之外的下一个要成功接收的节点，则S中的节点发送的功率应使j成功接收。如果说要使j成功接收所发送的功率使得节点i先于节点j成功接收，则应安排节点i作为下一个接收节点。这是因为节点j的发送不能使节点i获得信息，而节点i发送可能会使节点j获得信息。

算法代码如下：

S=[1];p=0

while(S

k=argmaxi∈S∑j∈Uhj,i;

S←[S,j]

end

假定源节点为1，未成功译码的节点集合为U，任一节点k的注水速率定义为节点k到所有未成功译码节点的信道增益系数之和：

(1)

则CIABP协议的贪婪注水算法描述如下：

(1)找出成功译码节点中注水速率最大的节点k；

(2)确定节点k的发送功率，使得某一个节点j在下一个时隙可以成功译码；

(3)将节点j加到成功译码的节点集合S中去。

将源节点标识为1，其后续成功接收节点依次标记为2,3,…， 如果节点m在其它发送节点发送的基础上成功译码，则发送速率可表示为

(2)

式中，pk为节点k的发送功率，若节点k没有进行发送，则pk=0。

现将CIABP与文献[1]提出的集中式能量累积广播协议(CEABP)进行比较。系统仿真参数设置如下:信道带宽W为200 kHz，单边带功率谱密度N0设定为5×10-6，要求达到的通信速率为270.833 kbit/s，仿真次数为100。从图1中可以看到，在3种衰落系数下，CIABP性能都比CEABP好，但是随着衰落系数的增加，CIABP相比于CEABP的性能优势在减小。CIABP和CEABP都随着节点数目的增加，系统需要的总的能量降低，这是因为节点密度增加以后，发送节点和未成功译码节点的平均距离降低，未成功译码的节点可以从发送节点处接收更多的信息。当α=2时，在N=10时，CIABP比CEABP能量消耗少1.5 dB；在N=150时能量消耗少1.9 dB。当α=4时，在N=10时，CIABP比CEABP能量消耗少1.09 dB；在N=150时能量消耗少1.13 dB。

图1 两种集中式广播协议的能量消耗Fig.1 Energy consumed of the two centralized broadcast protocols

4 分布式信息累积广播协议(DIABP)

在CIABP协议中，不仅要求节点知道所有链路增益系数的信息，还要求每一个成功译码节点的注水速率都是已知的，并且节点发送的功率可以确定，恰好使一个未成功译码节点在一个时隙内成功接收。这些条件要求过于苛刻，下面提出一个只需要局部网络信息的分布式广播协议。

Si=S∩NR(i)，Ui=U∩NR(i)

(3)

式中，Si代表节点i的邻居节点中成功译码的节点的集合，Ui代表节点i的邻居节点中未成功译码的节点的集合，S代表成功译码的节点的集合，U代表未成功译码的节点的集合，NR(i)代表节点i的邻居节点。在发送之初，任一节点i初始化为Si=⟩。

(4)

式中，B为发送信息的长度，tk为节点k的发送时间。

(2)一旦节点i成功译码，节点i发送ACKi，促使节点i的邻居中任一未成功译码的节点k接收到ACKi后发送LGk给节点i。节点i接收到所有链路增益控制帧LG之后就可以计算出自己的注水速率，然后将它的注水速率用控制帧FRi广播给它的邻居节点。在本文中，如果两个节点同为某一个节点的邻居，则认为这两个节点可以可靠接收对方的控制帧FR。

(3)成功译码的节点i收到ACKj后，如果它正在发送，则停止发送。节点i更新Si、Ui和注水速率Ri，并将自己的注水速率用控制帧FRi广播给它的邻居节点，然后由Si中注水速率最大的节点进行发送，当节点i的所有邻居节点都成功译码时，这个过程停止。

在节点i的发送过程中，与能量累积协议中重复发送相同的编码信息不同，节点i一直在发送不同的编码信息，这依赖于喷泉码可以产生源源不断的编码信息的特性。在本算法中，节点的动作都是由ACK帧触发的。

图2对DIABP协议与文献[1]提出的分布式能量累积协议(DEABP)进行了比较，仿真参数设置如下：信道带宽W为200 kHz，单边带功率谱密度N0为5×10-6，帧长B为1.56，仿真次数为100。为保证网络节点的全连通，根据文献[10]，将节点的可靠发送范围设为r=2.6，节点的发送信息功率p=1.56，发送控制帧的功率pc=1.56。从图中可以看出，DIABP协议比DEABP协议的能量效率要高。更重要的是随着节点数目的增加，DIABP协议所需的能量逐渐降低，而DEABP则有缓慢上升的趋势。这是因为随着节点间距离的降低，复用增益产生的作用比分集增益的作用更加明显。在N=80时，DIABP比DEABP协议所需的能量少0.64 dB；在N=300时，DIABP比DEABP协议所需的能量少1.56 dB。图中也给出了CIABP协议和DIABP协议的比较，可以看出DIABP相比于CIABP协议性能还是下降较大。

图2 两种分布式广播协议的能量消耗Fig.2 Energy consumed of the two distributed broadcast protocols

5 结 论

本文将喷泉码引入到协同多跳广播传输系统中，令成功译码中注水速率最大的节点发送，接收节点成功接收后，再由更新后注水速率最大的节点发送。接收节点对接收到的喷泉编码信息进行累积，直至成功译码。针对不同的应用环境，提出了CIABP和DIABP协议，并将这两种协议与现有的能量累积广播协议进了仿真比较。结果表明，采用喷泉码的信息累积协议其能量效率要明显优于能量累积广播协议。下一步的研究方向是简化DIABP协议设计，提高协议的空分复用性。

参考文献：

[1] Maric I, Yates R D. Cooperative multi-hop broadcast for wireless networks [J]. IEEE Journal on Selected Areas in Communications, 2004, 22(6):1080-1088.

[2] Kailas A, Thanayamkizil L, Ingram M A. A simple cooperative transmission protocol for energy-efficient broadcasting over muti-hop wireless networks [J]. IEEE Journal of Communications and Networks, 2008, 10(2):213-220.

[3] Byers J W, Luby M, Mitzenmacher M , et al. A digital fountain approach to reliable distribution of bulk data[C]//Proceedings of ACM Special Interest Group on Data Communication.Vancouver,Canada: IEEE, 1998:56-67.

[4] Luby M. LT Codes[C]//Proceedings of the 43rd Annual IEEE Symposium on Foundations Computer Science.Vancouver,Canada:IEEE,2002:271-280.

[5] Shokrollahi A. Raptor codes[J].IEEE Transactions on Information Theory, 2006,52(6):2551-2567.

[6] Molish A F, Methta N B, Yedida J S, et al. Performance of fountain codes in collaborative relay networks [J]. IEEE Transactions on Wireless Communications, 2007,6(11):4108-4119.

[7] Castura J, Mao Y. Rateless coding for wireless relay channels [J].IEEE Transactions on Wireless Communications, 2007, 6(5):1638-1642.

[8] Li F,Nikolaidis I. On minimum-energy broadcasting in all-wireless networks[C]//Proceedings of Local Computer Networks.Tampa,FL,USA:IEEE,2001:193-202.

[9] Ahluwalia A, Modiano E, Shu L. On the complexity and distributed construction of energy-efficient broadcast trees in ad-hoc wireless networks [J].IEEE Transactions on Wireless Communications, 2005, 4(5):2136-2147.

[10] Li N, Hou C. BLMST: A scalable, power efficient broadcast algorithm for wireless networks[C]//Proceeding of Quality of Service in Heterogeneous Wired/Wireless Networks. Dallas, TX, USA: IEEE, 2004:44-51.