王勇杰， 陈 静

(1. 山西大学 商务学院， 山西 太原 030031； 2. 中国航天科工集团第二研究院706所， 北京 100854)

无线中继网络部署方案设计

王勇杰1， 陈 静2

(1. 山西大学 商务学院， 山西 太原 030031； 2. 中国航天科工集团第二研究院706所， 北京 100854)

根据无线中继器来扩大无线网络的覆盖面积， 提升当前区域内网络质量的需要， 提出了一种无线中继设备部署策略来提升区域内用户的满意度. 对无线中继网络进行了建模， 对无线网络中信号传输过程进行了量化处理， 利用用户接收到的信号强度定义用户的体验度； 利用最速下降法， 使无线中继器能够自适应地向一些理想位置进行移动， 最终确定每一个无线中继设备的部署位置. 仿真实验表明， 本文算法能够很好地提升区域内用户的体验度， 具有较高的应用价值.

无线中继网络； 信号传输； 体验度； 最速下降法

0 引 言

由于无线网络信号源放置位置不合理， 发射功率不足以及障碍物的阻断， 导致了无线网络的覆盖范围小， 无线信号弱等问题， 无法满足用户的用网需求[1]. 近年来出现的无线中继器设备， 可以对接收到的无线信号进行转发放大， 满足了更多用户的需求， 扩大无线网络的覆盖范围[2-5]， 无线网络也就变成了无线中继网络， 使得无线网络的应用面更广， 作用更大. 因此， 人们对无线中继器的研究也越来越多.

2004年， Nosratinia等人[6]首先提出了无线中继协作这一概念， 即借助无线中继设备， 来完成数据包的传递， 并给出了三种中继转发模式， 针对三种不同的模式， 进行了详细的理论分析， 得出了每种模式的应用场景， 使得中继这一概念逐渐流行. 有很多研究集中在了无线中继网络的物理特性， 如无线转发机制的测试与评价[7]， 编码机制[8]， 以及无线信号信道特性[9].

2010年之后， 越来越多的研究者开始利用无线中继设备来扩大覆盖范围， 其中包括利用中继节点来扩大无线传感器网络范围， 帮助传感器来传输数据， 起到连接作用. Jiang等人[10]研究在无线传感器网络中， 利用无线中继设备将传感器连接到主干中心网络上， 扩大整个监控范围， 他们提出了一种分布式的算法， 首先解决传感器的部署覆盖问题， 之后部署无线中继器来连接传感器. Lang等人[11]针对下一代移动网络， 通过部署无线中继器来扩大整个网络覆盖范围， 根据不同区域的使用需求以及部署开销， 来确定最优的部署策略与方案. Pervin等人[12]研究在目标覆盖区域内的节点候选集合中选出联通的传感器网络， 实现区域的全覆盖， 他们提出了两种集中式的贪心算法， 相较于分布式算法， 能够减少计算的复杂性.

同时， 也有借助无线中继器来扩大无线网络范围， 提升网络质量. Ma等人[13]利用无线中继器延长整个网络的工作时间， 将问题转化为无线中继器部署问题， 覆盖所有的传感器节点， 提出了布局搜索的近似算法， 借助独立集和集合覆盖进行算法分析， 得到了较好的近似比. Gueguen等人[14]针对协作编码模式的无线中继器， 提出了一种奖励机制， 通过选择区域内的网络设备， 进行中转信号从而增大网络区域面积， 该网络设备的拥有者获得了一定的奖励， 实现了双赢.

这些研究都是通过部署无线中继器来实现整个无线网络中网络性能的提升， 但他们对于无线中继器的部署位置有着相对严格的要求， 即给出了相应的候选集合， 这样就导致无线中继器并不能自适应地进行调整， 存在一定的局限性； 另外， 单纯地联通传感器等一些节点并不能真实地反映连通结果， 信号传输快慢、 信号传输大小等具体指标才能够地直观反映无线中继器连通的作用. 因此， 本文主要研究无线中继器的部署问题， 提出最速下降算法， 使每一个无线中继器根据用户分布以及连通性要求进行自适应地移动， 从而对部署位置进行优化， 使更多的用户获得满意的无线信号.

1 无线中继网络模型

由于无线中继网络涉及到无线中继设备之间的连通性， 以及用户与无线设备之间的信号传输， 因此分别对网络模型与通讯模型进行建模处理， 网络模型主要考虑无线中继网络之间设备的连通性， 通讯模型则主要考虑无线信号传输过程， 对用户体验等进行定义.

1.1 网络模型

针对一个目标区域Ω， 假设该区域连续、 平坦且没有障碍物妨碍， 区域内有n个用户， 记为U={u1,u2,…,un}， 每个用户使用一个移动设备， 进行无线信号接收. 区域内放置着一个无线基站B， 用来发射无线信号， 共有m个无线中继器可以放置在当前区域中， 记为R={r1,r2,…,rm}， 位置函数L(·)记录区域内用户、 无线基站以及无线中继器的位置.

由于无线中继器无法感应太弱的无线信号， 因此， 无线中继器之间以及无线中继器与无线基站之间的距离不能过长， 记该距离为通讯半径d， 即当两个设备之间的距离小于d时， 两者之间可以互相接收到满足工作需求的无线信号.

为了实现无线通信， 需要在区域内的所有无线中继器与无线基站之间进行若干条连接， 从无线基站获取最初的无线信号， 形成一个连通的网络.

1.2 通讯模型

在无线网络中， 用户所能够接收到的无线信号强度决定着用户在该网络下的体验度， 因此需要计算无线信号传播过程中， 用户所能够接收到的无线信号强度. 由于该区域平坦连续且没有障碍物， 无线信号发射源与用户的移动设备之间没有障碍物， 能够直接看到对方， 因此采用Friis自由空间传播模型来计算移动设备的接收信号功率， 即

式中：PR是接收功率；PT是发射功率；d是两个设备之间的距离；GT和GR分别表示发射和接收增益；λ为无线信号的波长. 因此， 移动设备的接收功率是一个随距离变化的函数， 不同的移动设备对无线信号的敏感度、 接收增益也不同.

在日常生活中， 常见的无线路由器的发射增益为3 dBi和5 dBi， 一些性能更强的无线路由器采用7 dBi的天线； 平时使用的手机等移动设备的接收增益一般为2～3 dBi， 一般的无线路由器的发射功率在50～100 mW之间， 我国现在常见的无线网络中， 信号频率通常是2.4 GHz和5 GHz.

可以看出， 移动设备的接收功率与无线信号源的距离平方成反比， 因此需要考虑路径损耗PL， 即发射功率与接收功率的相差值， 代表信号的衰减程度

由于用户大多使用移动设备， 因此记用户接收到的无线信号功率为无线信号接收强度， 即为需要优化的目标， 但由于这个目标难以量化， 因此定义用户体验度函数， 将用户接收到的无线信号功率转化为用户体验度， 这样更利于以后的计算.

一些移动设备接收到的信号强度过小， 并不能满足用户的基本需求， 因此设定一个基本信号强度的阈值T， 即当移动设备接收到的信号强度大于信号强度阈值T时， 该接收信号强度能够满足用户的基本需求， 才会被计算在内， 作为优化的目标. 用户体验度函数定义为

式中：Pmax表示移动设备能够接收到的最大无线信号功率. 这样就将优化目标进行了归一化处理， 便于之后的计算. 根据用户所连接的无线设备， 对体验度函数进行重新定义为

1.3 问题模型

本文通过放置有限数目的无线中继器， 来使得区域内用户所接收到的无线信号强度之和达到最大， 每一个用户的移动设备都可能会接收到来自不同无线信号源发射的无线信号， 那么根据无线信号强度的大小排序， 每个移动设备都会选择信号强度最大的无线信号发射源进行连接， 定义此时已经在区域内放置的无线信号源的状态为A， 定义连接函数cA(u)为用户所选择的接收到在A状态下的最大信号强度u的无线信号源， 可以是无线基站B， 也可以是无线中继器R， 根据该连接函数确定用户与无线信号发射源的对应关系， 即

具体的问题定义为： 在目标区域Ω中放置着一个无线基站B， 在区域内分布着n个用户， 通过放置m个无线中继器， 保证中继器的连通状态， 使得区域内的用户接收到的无线信号， 其体验度之和达到最大， 即

2 梯度下降算法

梯度下降算法是一种经典的最优化方法， 一般用于无约束问题， 它的变量少， 要求不高. 一般的思想为， 从某个用户u所在位置出发， 取函数s(u) 在L(u)点时下降最快的方向作为移动方向， 经过多次迭代， 达到想要的目标值， 即在一定区域内的极值， 此时迭代过程结束.

对于该问题， 整个迭代过程如下： 首先， 区域内随机放置一个无线信号基站， 可以覆盖一部分区域， 接着在能够与无线信号基站连通的区域内随机放置无线中继器， 根据在该点放置无线中继器能够给予整个区域用户信号强度的增量之和， 寻找增量增加最多的一个方向进行一定长度的移动， 之后继续移动， 直到找不到能够使得信号强度之和增加的点， 即作为无线中继器的一个放置位置. 按照这个步骤放置k个无线中继器， 使得无线中继器分布能够尽可能满足区域内更多用户.

该算法的核心是寻找最优的移动方向， 由于用户接收到信号强度增量不是一个连续函数， 因此需要定义信号强度的求导公式， 便于之后计算. 当在该点放置无线中继器时， 用户与该无线中继器连接所获得的信号强度小于其接收到其他已放置好的无线信号源的信号强度， 即s(r,u)≤s(cA(u),u)， 其中A为当前无线中继器放置状态， 则定义信号强度增量的导数为0； 当在该点放置无线中继器， 用户与该无线中继器连接所获得的信号强度大于其接收到其他已放置好的无线信号源的信号强度时， 即s(r,u)>s(cA(u),u)， 则信号强度增量的导数为用户与该无线中继器所获得的信号强度的导数. 具体为

式中：Lt(rj)表示无线中继器rj在时刻t的位置；α为移动的步长.

输入： 用户集合U， 无线中继器集合R

通讯半径d， 用户体验度函数s

输出： 无线中继器的部署位置L(R)

1. 初始化： 随机部署无线基站r1， 生成相应的覆盖区域

2. fori=2 tomdo

3.α=α0

4. Whileα≥αTdo

5. 在覆盖区域内放置节点ri

9. end while

10. end for

11. returnL(R)

该算法同样可以扩展成分布式算法， 将所有的无线中继器节点集中在某一个区域， 之后根据最速下降法进行自适应移动， 但分布式算法会导致无线中继节点移动的方向过于统一， 最终结果可能是大多数中继节点都集中在某一区域， 无法很好地覆盖整个区域， 使得整体覆盖效果不如集中式算法， 需要对每个无线中继器设置相互排斥属性， 避免无线中继节点的统一趋势化移动.

该算法的结果在很大程度上取决于最初随机放置的位置， 因为最速下降算法很容易受到局部最优的影响， 因此需要进行多次模拟， 从中选择最优的情况作为最终的结果. 同样， 无线中继器在移动过程中也有可能陷入局部最优解的循环之中， 不能取得很好的结果， 因此也需要对这种情况进行一定的判断， 在适当时候增加移动步长， 使得节点能够跳出局部最优的峡谷， 在更大范围寻找更优的部署位置.

3 实验与仿真

本次仿真实验主要使用 Matlab 实现， 设定一个目标区域Ω=100×100， 在区域中随机地分布着成百的用户， 每个用户都在使用移动设备， 并对无线网络有需求， 希望能够连接到该区域提供的无线网. 同时， 考虑异质网络， 即每一个用户之间存在差异， 因为其使用的设备不尽相同， 在一些接受参数上也难免产生一些差异. 设定的参数与第二部分中日常生活中的参数相近， 这样能更加贴近现实， 具体设定如表 1 所示.

表 1 网络模型参数设定Tab.1 Setting on network model parameter

进行仿真实验来探究最速下降算法对于区域内用户体验度的影响. 对于传统的网络部署问题， 大多采用网格的形式对部署位置的候选集合进行限定， 之后利用组合优化算法选择相应的部署位置， 在这里， 也采用网格部署法进行对比， 通过在区域内设置网格点， 利用贪心策略选择有限个数的无线中继节点.

首先， 利用无线中继器个数对于网络中用户体验度进行研究， 将用户数目设定为200人， 在一个无线基站的基础上， 可以部署5～10个无线中继节点， 扩大整个区域无线网络的覆盖范围， 则在这个网络中用户的体验度之和随着无线中继器数目的增加而增加， 如图 1 所示. 可以看到， 利用最速下降法得到的部署方案要优于网格部署法得到的结果， 这是因为网格部署法会局限于有限的候选位置， 无法进行一定范围的调整， 而通过最速下降法得到的位置， 没有特定集合的限制， 反而能够得到更优的结果. 同时， 由于边际效应或用户体验度函数是一个次模集合函数， 随着无线中继器数目的增加， 用户体验度之和的增量会逐渐递减[15].

图 1 用户体验度随中继器个数变化图Fig.1 Influence of relays number on QoE

图 2 用户体验度随用户人数变化图Fig.2 Influence of users number on QoE

当用户数目增加时， 用户的体验度之和也会随之上升， 这是由于用户的基数增大， 从而导致整体的体验度之和也会上升， 如图 2 所示. 由此可以看出， 本文提出的最速下降法也是网格部署法， 整体来看， 用户体验度基本与用户人数呈线性关系， 用户的平均体验度平稳中有上升的趋势， 这是因为用户数目的增多， 导致用户密度的增加， 从而使得更多用户获得了较好的用户体验.

图 3 为无线中继器布置的分布图， 图3(a)中为在区域内放置1个无线基站与5个无线中继器来尽可能满足100个用户的分布情况， 图3(b)中为放置1个无线基站和7个无线中继器来满足200个用户的分布情况. 其中， 浅色节点表示用户位置， 空心节点表示无线设备放置位置， 黑色大圆圈表示无线设备能够服务的范围， 可以看到无线设备之间形成了一个连通分支， 并覆盖了一些用户密集的区域， 而在现实场景中， 也能够很好地根据人流分布， 决策出相应的部署方案.

图 3 中继器分布图Fig.3 Relay distribution circumstance

统计表明， 利用无线中继设备扩大无线网络的覆盖范围， 在图3的场景下， 能够覆盖超过65%的用户， 由于算法是优化用户体验度， 因此这些用户中的绝大多数都能得到较优的服务质量， 也可以看到， 无线中继器会放置在用户密集的位置， 且距离一些用户特别近， 使其获得更好的用户体验， 而不是单纯地覆盖更多的用户， 为他们提供服务.

4 结 论

本文主要研究了无线中继网络中无线中继器部署问题， 通过深入学习无线信号的传输过程， 建立了无线中继网络模型， 考虑了无线网络的诸多特性， 使得该模型更加符合实际情况. 之后又提出了最速下降法来布设无线中继器的位置， 通过确定无线中继器的位置， 来提升用户在区域内的体验度， 并在仿真实验中取得了比较好的结果. 本文的研究内容结合了前人的研究基础， 建立了一套完整的无线中继网络模型， 对以后的工作具有一定的指导意义.

[1] Ma L, Teymorian A Y, Cheng X. A hybrid rogue access point protection framework for commodity Wi-Fi networks[C]∥The 27th Conference on Computer Communications, IEEE, 2008: 1220-1228.

[2] Zhou H, Ji Y, Gu Y, et al. A resource allocation algorithm for SVC multicast over wireless relay networks based on cascaded coverage problem[C]∥Global Communications Conference (GLOBECOM), IEEE, 2012: 5681-5686.

[3] Jing T, Zhu S, Li H, et al. Cooperative relay selection in cognitive radio networks[J]. IEEE Transactions on Vehicular Technology, 2015, 64(5): 1872-1881.

[4] Gueguen C, Rachedi A, Guizani M. Incentive scheduler algorithm for cooperation and coverage extension in wireless networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 797-808.

[5] Ono H, Takeyoshi H. Mobile node, packet relay device and packet forwarding method: U.S., 10/786,411[P]. 2004-02-26.

[6] Nosratinia A, Hunter T E, Hedayat A. Cooperative communication in wireless networks[J]. IEEE communications Magazine, 2004, 42(10): 74-80.

[7] Zhou H, Ji Y, Gu Y, et al. A resource allocation algorithm for SVC multicast over wireless relay networks based on cascaded coverage problem[C]∥Global Communications Conference (GLOBECOM), IEEE, 2012: 5681-5686.

[8] Mohammed A H, Dai B, Huang B, et al. A survey and tutorial of wireless relay network protocols based on network coding[J]. Journal of Network and Computer Applications, 2013, 36(2): 593-610.

[9] Dai M, Wang P, Zhang S, et al. Survey on cooperative strategies for wireless relay channels[J]. Transactions on Emerging Telecommunications Technologies, 2014, 25(9): 926-942.

[10] Jiang J, Wen J, Wu G, et al. Constructing minimum relay connected sensor cover in heterogeneous wireless sensor networks[C]∥International Conference on Ad Hoc Networks. Springer Berlin Heidelberg, 2009: 477-492.

[11] Lang E, Redana S, Raaf B. Business impact of relay deployment for coverage extension in 3GPP LTE-Advanced[C]∥IEEE International Conference, 2009: 1-5.

[12] Pervin N, Layek D, Das N. Localized algorithm for connected set cover partitioning in wireless sensor networks[C]∥Parallel Distributed and Grid Computing (PDGC), 2010 1st International Conference on IEEE, 2010: 229-234.

[13] Ma C, Liang W, Zheng M, et al. A novel local search approximation algorithm for relay node placement in wireless sensor networks[C]∥Wireless Communications and Networking Conference (WCNC), IEEE, 2015: 1518-1523.

[14] Gueguen C, Rachedi A, Guizani M. Incentive scheduler algorithm for cooperation and coverage extension in wireless networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 797-808.

[15] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions—I[J]. Mathematical Programming, 1978, 14(1): 265-294.

DeploymentStrategyDesigninWirelessRelayNetworks

WANG Yong-jie1, CHEN Jing2

(1. College of Business, Shanxi University, Taiyuan 030031, China;2. No.706 Institute, The Secnod Academy of China Aerospace Science and Industry Corporation, Beijing 100854, China)

Based on the demand of extending the wireless coverage area and improving the networks quality with wireless relay, a deployment strategy for wireless relay was presented to increase the users' quality of experience (QoE). Wireless relay network model was built, and the transmission process of wireless signal was quantified. The QoE was defined according to the signal strength that users receive. By using the steepest descent method, the wireless relay could move adaptively to some ideal locations, and deployment point could be determined. The results of simulation experiment show that our algorithm can improve the QoE of users in the region, and has strong application value.

wireless relay network; signal transmission; QoE; steepest descent method

1673-3193(2017)05-0633-06

2016-12-21

王勇杰(1967-)， 男， 副教授， 主要从事计算机网络， 数据挖掘研究.

TP301

A

10.3969/j.issn.1673-3193.2017.05.022