一种盲波束赋形与置零新算法
王骥1, 陈芳炯2, 谢仕义1
1.广东海洋大学 信息学院,广东 湛江 524088
2.华南理工大学 电子与信息学院, 广州 510641
通讯作者:谢仕义(1963-),男,教授.研究方向:海洋物联网.E-mail:shiyixie@126.com

作者简介:王骥(1972-),男,副教授.研究方向:无线传感器网络与无线通信系统.E-mail:zjouwangji@163.com

摘要

针对随着移动终端和业务的持续发展,企业级WLAN中采用传统的AP部署方式和信道竞争协议难以满足日益增长的吞吐量的需求的问题,本文提出了一种新的盲波束赋形与置零算法,该算法能够使得多个终端在同一时隙中进行传输,在有效提高信道利用率的前提下,同时较好地解决了通信的干扰问题,实验结果表明,本文提出的算法与传统的信道竞争协议和AP部署方式相比,能够有效减少开销并显著提高终端的吞吐率。

关键词: 通信技术; 无线局域网络; 盲波束赋形; 置零算法; 吞吐率
中图分类号:TN923 文献标志码:A 文章编号:1671-5497(2016)03-0972-07
Throughput expanding WLAN based blind beam forming and nulling algorithm
WANG Ji1, CHEN Fang-jiong2, XIE Shi-yi1
1.School of Information, Guangdong Ocean University,Zhanjiang 524088,China
2.Institute of Electronics and Information,South China University of Technology,Guangzhou 510641,China
Abstract

With the continuous development of mobile terminals and business, in enterprise WLAN, user demand for throughput is gradually increasing. The traditional way of AP deployment and channel competition protocol can not satisfy the increasing communication demand. Therefore, many new methods have been put forward, such as interference alignment and combined beam forming. However, the use of these methods has certain limits and it is difficult to achieve good effect in actual use. This paper proposes a blind beam forming and nulling algorithm. This algorithm allows multiple terminals to transmit at the same time slot, on the premise of effectively improving the channel utilization rate, and better solving the problem of the interference of communication. Experimental results show that, compared with the traditional way of channel competition protocol and AP deployment, the proposed algorithm can effectively reduce the cost and improve the throughput of the terminal.

Keyword: communication technology; WLAN; blind beam forming; nulling algorithm; throughput
0 引 言

随着移动智能终端的快速发展, 以及移动终端业务的不断扩大, 使得当前的移动智能终端无论是在数量上还是对带宽的需求上, 均有了较大的提高, 进而导致了WLAN中带宽资源的持续紧张。在传统的WLAN中, 所有移动终端接入点(Access Point-AP), 各个终端同时采用竞争信道协议, 共享AP的通信带宽[1]。随着当前移动终端数量和业务的飞速发展, 传统的WLAN越来越难以满足终端对于带宽的需求, 其主要原因有两点:首先, 多终端共享单个AP的带宽资源, 当接入终端数量过多时, 导致每个终端能够占用的资源有限; 其次, 采用竞争信道通信协议, 使得一个终端在通信的同时, 其他终端必须保持静默, 降低了系统的吞吐率[2, 3, 4]。为了解决以上两个问题, 学术界和企业界提出了不同的解决方案。通常情况下, 采用增加AP的方法, 能够在一定程度上缓解WLAN中带宽不足的情况, 通过使终端接入不同的AP, 可以有效减少一个AP上共享的终端数, 从而提高每个终端占用的带宽。但是, 在实际应用中, 移动终端的位置往往是不断变化的, 因此, 难以使得各个终端平均分配到各个AP上, 在某些终端较为密集的区域, 仍然会产生带宽不足的问题, 同时增加AP的方法开销较大, 难以扩展, 实用性较低。干扰对齐(IA)是另一种解决方法, 其主要是从终端和AP的通信过程入手, 旨在提高信道的利用率, 但是该方法的使用前提是, 必须要求所有的移动终端按照同样的时序发送数据包, 而这一同步过程难以在分布式的移动终端中实现, 因此难以实现实用[5, 6]。多用户MIMO是最近提出的一种方法, 采用多输入多输出的方法, 提高终端和AP的传输带宽, 但是为了实现多用户MIMO, 需要AP间利用骨干网传递采样信息, 而这一过程会消耗太多的带宽, 具有较大的成本, 难以获得较好的效果[7, 8]。联合波束赋形算法是近年的研究热点之一, 能够实现在同一时隙中的多用户同时传输, 但是其只工作在下行链路上, 且要求无线设备要能够共享发送的数据包, 而这一过程在无线环境下是难以实现的[9]

在当前的企业级WLAN中, 通常采用AP的密集部署, 一方面能够使得WLAN覆盖较大的通信范围, 另一方面也使得一个移动终端同时处于多个WLAN的覆盖范围内。同时, AP之间采用有线链路连接, 能够通过有线网传递数据, 且AP的部署通常是静止的, 因此也就导致AP与终端进行传输的信道也是静止的。针对以上应用环境, 本文在仔细分析WLAN中用户已有成果和方法的基础上, 对比各种方法的优缺点, 提出了一种盲波束赋形与置零算法(Blind beam forming and nulling algorithm, BBN), 该算法克服了原先信道竞争协议的缺点, 能够使得多个终端在同一时隙中进行传输, 在不增加延迟与能耗的情况下大大提高了终端的吞吐率。并设计了物理层和MAC层中算法的实现方法, 实验仿真结果证明本文提出的算法有效性, 相比传统的方法具有更好的性能。

1 新算法的数学模型和设计
1.1 算法实现的数学模型

本文对于智能硬件信号处理领域内的波束赋形技术的具体算法进行了研究。无线智能终端信号模型如式(1)所示:

sx, t=Aexpjωt-kxx-kyy-kzz=Aexpjωt-x·k=Aexpt-x·α(1)

式中: α=k/ω,由式(1)得,对于多用户系统,则s(t)为:

st=st-x1·αst-x2·αst-xM·α=Aexpt-x1·αAexpt-x2·αAexpt-xM·α=stexp-x1·αexp-x2·αexp-xM·α=staθ(2)

在多AP情况下, K为系统中的用户数; M为AP个数; 则在频率选择性衰落情况下, 接收到的第 k个用户的信号矢量为:

xkt=l=1Lkαk, laθk, lskt-τ(3)

式中:Lk为第k个用户的多径数, 表示第k个用户第l径的复信道增益, 则在平坦衰落情况下, 接收到的第k个用户的信号矢量转化为:

xkt=l=1Lkαk, leτk, laθk, lskt-τ(4)

本文研究波束赋形技术是指利用测量或估算的参数, 实现信号最优-次优组合或者最优-次优分配的过程。因此无线移动信道的建模与估计是波束赋形技术的基础, 无论是算法描述、性能分析以及仿真都必须以此为基础。

1.2 BBN算法设计

在盲波束赋形与置零算法中, 主要存在两个时隙, 其中在第一个时隙中终端(Client)进行工作, 发送自己的数据包; 在第二个时隙中AP进行工作, 对多个client发送的数据包进行解码, 获得正确的发送内容。其中第一个时隙的工作场景如图1所示。

图1 时隙1工作场景Fig.1 The situation of slot 1

在第一个时隙内, 三台智能终端同时发送数据, AP1~AP4同时接收数据, 其中 yj(i)为APj在时隙(i中接收到的数据, 其中xi为第i台终端发送的数据, 则 hjk(i)为在时隙i中, APj和终端 k之间的信道系数。则对于APk在时隙 t内有信号:

yik(i)=hik1xi(5)

式中: yik(i)为APk收到终端 i发送的数据的分量。

在第二个时隙内, 所有的AP分为两部分, 一部分AP发送自己接收到的数据, 而另一部分AP接收, 如图2所示, 此时AP3和AP4发送, 而AP1和AP2收听。则AP1和AP2利用各自收到的数据, 通过解方程组的方式, 依次解出每个终端发送的真实数据。

图2 时隙2工作场景Fig.2 The situation of slot2

假设在一个时隙中共有 M个AP, vk为APk的信道系数向量, 则:

yij2=k=3Mhkj2vkyik1=k=3Mhkj2vkhik1xi(6)

为了确保AP1上的x2x3 的分量为线性组合, 可以令si为Api中的信道相关系数, 则:

y212=k=3Mhkl2vkh2k1x2=s1y211=s1h211x2(7)

y312=k=3Mhkl2vkh3k1x3=s1y311=s1h311x3(8)

对等式(7)(8)进行简化得到:

k=3Mhkl2vkh2k1-s1y211=0k=3Mhkl2vkh3k1-s1y311=0

则根据以上等式, 可以在每个AP上解出 x1, x2, x3同时根据以上的公式, 如果在网络中有N个终端, 那么需要(N2-N-2)/2个未知数解出所有的x, 为了保证方程组有非零解, 需要至少(N2-N-2)/2个AP才能完成, 因此, 对于N个终端的网络, 使用本文提出的方法, 共需要(N2-N-2)/2个AP进行合作。

综上所述, 以上算法的流程图如图3所示。

图3 算法流程图Fig.3 The flowchart of algorithm

由以上算法过程可以看出, 本文设计的盲波束赋形与置零算法, 能够支持WLAN中多个移动终端的同时发送, 改变了原先竞争信道协议的发送模式, 能够有效地提高终端的吞吐率。同时, 计算过程在AP上实现, 能够向用户隐藏算法实现的细节, 简化终端的设计, 具有较好的灵活性和实用性。

2 算法实现

随着网络结构和规模的日益复杂与拓展, 网络中的各种类型、业务、技术进一步融合, 传统的靠经验进行的网络设计方法和规划算法已经无法满足目前的需要。所以, 本文提出了BBN算法及其实现原理, 并给出了理论基础, 然而在实际使用过程中, 仍然需要设计物理层和MAC层的具体机制, 才能够实现算法预期的效果。

2.1 物理层设计

在算法的时隙2中, 需要AP采用同步的方式完成数据的发送和接收动作, 从而使得AP能够正确地解方程组, 获得每个终端发送的内容, 虽然在本文提出的方法中, 并没有要求终端发送的同步, 但在物理层(见图4)中仍然需要AP动作的同步。

图4 物理层时序图Fig.4 The timeline of physical layer

整个物理层的实现步骤可以分为4步:

(1)client传输过程

①AP发送允许帧(Approve), 指示了哪些client能够发送消息; ②通过等待IACS, 使得几个client能够同步发送数据包; ③所有的AP计算各个client的信道系数; ④AP之间的信道相关系数也需要计算, 所以各个AP依次发送sample。

所有计算出来的信道系数都通过骨干网传输给控制中心, 控制中心使用这些信道系数计算哪些AP用来传输, 哪些AP用来接收; 为了保证所有的AP都接收到了控制中心发送的结果, 需要等待一个BIFS[9, 10, 11]

(2)盲波束形成

在这一过程中, slot2中的发送AP将自己接收的信号乘以信道系数向量, 然后发送给接收AP。

(3)数据包解码

第一个AP解码一个包, 然后把这个包给第二个AP, 然后第二个AP根据第一个包和自己收到的消息, 解码第二个包, 依次类推, 直到所有的包都被解码。

(4)计算解码顺序

在之前的研究中, 均假设按照次序 x1, x2, x3等解码, 同时预编码的过程不会引入噪声, 然而在实际过程中这个假设是不成立的, 因此要计算解码的次序, 即要计算期望信号的接收强度。

整个过程可以看做是由Client i发送数据包到各个AP, 然后各个AP再发送给APj, 那么当RSS很高时, 意味着存在至少一条路径使得两个步骤的RSS都很高, RSS的计算方法为:

PSSijP0×max(min(hik12, hkj22))(9)

则对于 xi, APj可以容忍的噪声为: RSSijTi, 则按照降序排列所有的x, 获得解码的次序。

2.2 MAC层设计

MAC层需要解决的主要问题是如何在保证物理层设计发挥效果的前提下, 将本文提出的算法机制从单冲突域的情况扩展到多冲突域的情况[12, 13]

由于在实际使用过程中, AP并不一定能够听到所有的终端, 因此需要将所有的AP分为小的集群, 分集群的算法是多项式时间的贪心算法, 由于AP是不移动的, 所以改划分群算法一次运行之后能够使用很长的时间[14, 15]。算法在MAC层中实现时序图如图5所示。

图5 算法MAC层时序图Fig.5 The timeline of algorithm in MAC layer

如图5所示, 在多个AP集群中, 算法在MAC层中的实现过程有如下步骤:

(1)由于各个集群之间可能存在干扰, 因此首先要计算不同集群之间的邻居关系, 即指那些会互相干扰通信的集群, 而不能同时进行通信, 利用AP定义集群和集群邻居的概念, 使得即便有一个client同时存在于两个集群的覆盖域, 也不会产生问题。

(2)为了保证邻居集群不同时进行通信, 本文提出的方法采用了一个中心服务器, 这个服务器计算在接下来的两个时隙里, 能够通信组别。

(3)为了保证AP和client的协调, client是无状态的, 它只监听附近AP发送的poll包(轮询包, 询问client是否有包发送), 当client收到允许发送的信号时, 则立即发送自己的包。

(4)按照本文之前介绍的方法进行解码, AP解码包之后, 发送ACK给相应的client。

(5)在本文提出的算法中, 上行链路和下行链路可以同时工作, 每个组可以不受其他组干扰的进行上传和下载。

需要说明的是, 由于BBN算法的建立以通信环境与系统模型为基础, 要设计出更符合实际需要的性能算法必须考虑到环境因素以及各系统间的相互影响。所以首先需要建立系统模型及其信号描述方法, 而后结合实际工程中系统性能需求, 利用数学模型研究信号的组合或分配的最优解问题。

3 实验验证

为了验证本文提出算法的有效性, 除本文提出的盲波束赋形与置零算法(BBN)之外, 本文采用了两种方案对比试验:一种是全局TDMA, 在全局TDMA中存在一个全局服务器, 通过该服务器能够了解:①每个client的发送队列; ②client和AP之间的所有信道; 另一种是在2.4 GHz频段使用正交频分复用(OFDM)调制技术的IEEE802.11g, 使数据传输速率达20 Mbit/s以上; 后向兼容性好, 即能够与Wi-Fi(IEEE802.11b)共存于同一AP的网络里互联互通。

在本文的仿真过程中, 将从吞吐率、公平性、平均延迟与能耗四方面对三种方法进行比较。系统仿真参数设置见表1

表1 仿真数据的典型值 Fig.1 The simulation data of the typical values

仿真以数据帧平均长度为变量, 单位为时隙, 在0~200 s内变化。平均长度越长, 表明AP需传输的数据越频繁。在本节中, 通过多种情况的仿真, 对比基本机制与BBN方法的WLAN吞吐率和介质访问延迟等性能, 从而验证本文算法比基本机制下经典方法有更好的性能表现。

3.1 吞吐率

在单位时间内在信道上成功传输的信息量称为吞吐率。通过仿真实验, 三种方法吞吐率(Throughput)实验结果见图6。由图6可见, 与全局TDMA和802.11g相比, 本文提出的方法具有较高的吞吐率, 且随着AP个数的增多, 本文提出算法的优势越明显。其主要原因是当AP个数增多时, 在一个集群中能够支持的用户终端数就越多, 同时, 每个终端能够占用的带宽资源也获得了增加, 导致吞吐率获得了较为明显的提高。如图6所示, 当AP数量达到2000时, 每个集群的平均AP个数为76。在此种AP部署密度下, 其吞吐率相当于802.11g的5倍, 相当于全局TDMA的30倍左右。

图6 吞吐率实验结果图Fig.6 The result of throughput simulation

3.2 公平性

本文采用Jain公平性指数作为评价标准。仿真结果如图7所示。随着AP个数的增加, 三种方法的公平性均有所降低, 但是本文提出的方法仍然具有更好的公平性。IEEE 802.11g的公平性较差, 是因为当一个终端处于不同AP传输范围同时覆盖的区域时, 其可能会产生“ 饥饿” 现象而得不到服务。而本文提出的算法, 能够使集群中所有的终端同时进行传输, 因此其公平性相比于802.11g较好。同时, 对于任意终端, 其并不依靠单一的AP进行传输, 而是有众多的AP可以选择, 因此, 其产生“ 饥饿” 现象的概率大大降低, 从而能够实现较好的公平性。

图7 公平性实验结果图Fig.7 The result of fairness simulation

3.3 延迟分析

网络延迟性能实验结果如图8所示。延时分析指AP数据端到端传输过程中的所有时延, 如发送缓冲器等待时间、接口队列排队时间、MAC层重传时间、包的转发时延等。端到端平均时延等于目的AP分组接收时间到源AP分组或终端发送的平均时间。

图8 延迟比较Fig.8 Delay comparison

网络开始与AP数目较少时, BBN算法虽然优越于其他两种常规方法, 但不明显; AP数目在1600以上时, 本文的设计算法有较大优越性。原因是AP数目多, 算法吞吐率上升, 算法的优点更加明显; 在AP数目少时, 算法先进性没能体现出来。原因在于本算法在包转发的过程中与其他算法一样, 初始转发要进行重复包检查, 所以平均延时较大。但随着网络中参与数据传输的AP数量增加, 虽然总传输时延会渐渐地增加, 但算法公平性吞吐率优越性增加了算法先进性, 因此相比常规方法, 本文研究方法更适合大型网络。

3.4 算法能耗

算法能耗实验结果如图9所示。

图9 能量消耗Fig.9 Energy Consumption

由于AP数量的增加, 经典方法将很快地增加它们的能耗。本文提出的BBN算法阻止了AP终端进行不期望的电能消耗。因此, 整个网络的能量由于其公平性好将被平衡地消耗。因此, 本文算法能支撑大规模的自由网络, 提高了对随机的AP终端连接失败的容忍度。特别是大规模无线网络多终端接入时, 本文提出的算法可使能量消耗比其他方法更加平衡。

4 结 论

(1)提出了一种盲波束赋形与置零算法, 该方法能够实现在一个冲突域内, 多个AP和多个移动设备之间的互相通信。

(2)设计了AP间的有线连接和互相通信方式, 将解码的复杂性转移到了AP上, 保证了移动设备的设计能够尽量简单。

(3)利用AP固定性特点, 使得BBN能够更具实用性, 尤其是对无法使用干扰对齐技术的移动设备。

(4)在USRP测试平台上开发了原型系统, 并通过仿真展示了它的可行性、灵活性和高效性。

The authors have declared that no competing interests exist.

参考文献
[1] Adib F, Kumar S, Aryan O, et al. Interference alignment by motion[C]//Proc of ACM Mobi Com, 2013. [本文引用:1]
[2] Annapureddy V S, El Gamal A, Veeravalli V V. Degrees of freedom of interference channels with CoMP transmission and reception[J]. IEEE Transactions on Information Theory, 2012, 58(9): 5740-5760. [本文引用:1]
[3] 丁君, 王珺, 郭陈江, . 一种对任意线阵天线的主波束赋形方法[J]. 电波科学学报, 2004, 19(5): 89-95.
Ding Jun, Wang Jun, Guo Chen-jiang, et al. Mainlobe shaping method for arbitrary arrays[J]. Chinese Journal of Radio Science, 2004, 19(5): 89-95. [本文引用:1]
[4] Bansal T, Zhou W J, Srinivasan K, et al. RobinHood: Sharing the happiness in a wireless jungle[C]//In Proc of ACM HotMobile, Miami, USA, 2014: 1-6. [本文引用:1]
[5] Bansal T, Chen B, Sinha P, et al. Symphony: Cooperative packet recovery over the wired backbone in enterprise WLANs[C]//Proceedings of the 19th Annual International Conference on Mobile Computer & Networking, 2013: 351-362. [本文引用:1]
[6] 罗巍, 郭爱煌, 谭维锴. LTE-A中的SLNR联合校准多用户多流波束赋形方案[J]. 系统工程与电子技术, 2012, 34(11): 2351-2354.
Luo Wei, Guo Ai-huang, TAN Wei-kai. SLNR-based channel calibration multi-user multi-stream beamforming for LTE-A[J]. Systems Engineering and Electronics, 2012, 34(11): 2351-2354. [本文引用:1]
[7] Cadambe V R, Jafar S A. Interference alignment and the degrees of freedom for the K user interference channel[J]. IEEE Transactions on Information Theory, 2008, 54(8): 3425-3441. [本文引用:1]
[8] Geng Q, Kannan S, Viswanath P. Interactive interference alignment[DB/OL]. [2013-06-17]. http://arxiv.org/pdf/1211.0985vl.pdf. [本文引用:1]
[9] 贾向东, 李凡, 郑建光. 智能天线基带幅度加权波束赋形及其CDMA应用性能分析[J]. 电波科学学报, 2010, 25(3): 505-512.
Jia Xiang-dong, LI Fan, Zhen Jian-guang. Beamforming scheme for smart antenna by using base-band amplitude weighing and performance analysis in CDMA[J]. Chinese Journal of Radio Science, 2010, 25(3): 505-512. [本文引用:2]
[10] Gesbert D, Kountouris M, Heath R, et al. Shifting the MIMO paradigm[J]. Signal Processing Magazine, IEEE, 2007, 24(5): 36-46. [本文引用:1]
[11] 黄莹, 吕刚明, 朱世华. 接收矢量估计辅助的协调波束赋形算法[J]. 通信学报, 2014, 35(2): 194-201.
Huang Ying, Lyu Gang-ming, Zhu Shi-hua. Coordinated beamforming algorithm assisted byreceive beamforming vector estimation[J]. Journal on Communications, 2014, 35(2): 194-201. [本文引用:1]
[12] 董可, 廖学文, 朱世华. 毫米波通信系统中利用随机逼近的波束赋形算法[J]. 西安交通大学学报, 2011, 45(10): 72-76.
Dong Ke, Liao Xue-wen, Zhu Shi-hua. Beam-forming in millimeter-wave radio system via stochastic approximation[J]. Journal of Xi'an Jiaotong University, 2011, 45(10): 72-76. [本文引用:1]
[13] 吴文君, 王文博, 王健全. 多点协同系统中的协同波束赋形干扰抑制[J]. 北京邮电大学学报, 2011, 34(3): 103-107.
Wu Wen-jun, Wang Wen-bo, Wang Jian-quan. Coordinated beamforming interference suppression in coordinated multi-point systems[J] . Journal of Beijing University of Posts and Telecommunications, 2011, 34(3): 103-107. [本文引用:1]
[14] Gowda M, Sen S, Roy Choudhury R, et al. Cooperative Packet Recovery in Enterprise WLANs[J]. IEEE InfoCom, 2013, 12(11): 1348-1356. [本文引用:1]
[15] Jafar S A. Interference Alignment: A New Look at Signal Dimensions in a Communication Network[M]. Boston: Now Publishers, 2011. [本文引用:1]