混合式无线Mesh网络路由与信道分配联合优化

张维维，何家峰,高国旺,任丽莉，申铉京

(1.吉林大学 计算机科学与技术学院, 长春 130012;2. 长春师范大学 国际交流学院,长春 130032；3.31693部队, 哈尔滨150062;4.西安石油大学 电子工程学院，西安 710065;5.长春师范大学 网络中心,长春 130032)

0 引 言

无线Mesh网络(WMNs)具有容量大、速率高、成本低和扩展性强等优点，近年来受到了业界和学术界的广泛关注。无线Mesh网络依靠无线节点之间的相互协作，以多跳的方式为终端用户提供服务。无线Mesh网络的出现为商业化的“最后一公里”无线宽带接入奠定了坚实的基础。然而，由于无线频谱受限、同信道干扰等因素，制约了无线Mesh网络的普及和应用。

Qos感知路由(Qos-aware routing)协议[1]通过在物理拓扑上构造的多层逻辑拓扑映射，实行两套路由机制：第一种路由是物理路由机制，这种机制负责路由表的创立和可用带宽估算任务；另一种机制是逻辑路由控制机制，这种机制在物理路由的基础上，为实时多媒体业务分配带宽最大、跳数最短的逻辑路径。

为了提高无线Mesh网络的吞吐量性能并缓解网络拥塞程度，Wang等[2]提出了一种基于网络编码的干扰感知路由协议(Coding-and-interference aware routing，CIAR),综合考虑了拓扑信息、流量模式、无线干扰和编码增益等因素，该协议基于实用网络编码技术和物理干扰模型，不但能够在路径建立过程中主动地探测潜在的编码机会，而且能够在路径选择阶段辨别出编码增益大、干扰代价小的路由线路，在获得较大的编码增益与缓解干扰程度之间取得良好的折中。与传统的编码感知路由方案相比，CIAR协议在付出较小控制报文开销的代价下，可以有效提高网络吞吐量性能，同时降低端到端延迟及节点的缓存溢出概率。Chen[3]提出了基于网络编码的差错容忍路由(Net coding fault-tolerant routing, NCFR)机制,该机制考虑到无线Mesh网络在某些节点处功能受限，信道、链路易受损伤等缺点，允许中继节点进行有限次编码操作，从而降低随机线性网络编码的计算开销与算法复杂度[4-5]。基于以上分析，本文提出了一种混合式无线Mesh网络路由与信道分配联合优化方法。

1 混合无线Mesh架构

Mesh传感器网络通过网状拓扑结构实现网络的全覆盖,网状拓扑如下：1)由称为Mesh基站(无线传感器基站)的中心节点(可以与网络)控制；2)基站作为连接到外网的接口；3)无线Mesh网络通过点到多点的无线接入系统802.15.4接入网络[6]。

某些移动用户希望在没有可用网络基础设施的情况下通信，例如消防队员需要在通往紧急站点的途中连接到救护车。在这种情况下，具有无线网络接口的移动自组织集合可以形成瞬时网络，而无需任何已建立的网络基础设施或集中式管理。在互联网工程任务组(IETF)内形成的移动自组织网络(MANET)组主要集中于开发新的MANET规范，并将其引入到互联网标准轨道。他们的目标是支持移动自组织网络，通过数百个移动自组织路由器支持移动自组织网络，并解决这种网络面临的挑战。然而，移动自组织网络面临诸多挑战，例如，除了引起变迁路径的移动性和电池限制之外，还限制了根据传动误差的无线传输范围、隐藏节点问题和分组丢失。根据所谓的认证因素，对用户的身份认证方式分为3类：根据你所知道的信息来证明你的身份；根据你所拥有的东西来证明你的身份；根据独一无二的身体特征来证明你的身份。每个认证因素包括一系列元素，其被用于授予访问权、批准事务处理请求、签署文件或其他工作产品、授予他人权限以及建立权限链之前的身份认证或验证中[7]。

无线传感网络存在分布的跨区域性，随着无线传感网络的扩张，传感器数目增多，将产生大规模的传感数据。两层分布式存储架构，使用分布式数据库HBase存储跨区域的无线传感网络数据和全局数据存储管理目录，实现了一个近实时的存储系统。从研究者的实验结果[8]可以看出，这种具有可扩展性强、存储和查询效率高的系统可以解决大量传感器数据存储问题。

微处理器和传感器技术的新进展能够部署在大规模无线传感器网络中[9]。在某些环境中，传感器装置是一次性的。由于部署传感器网络的经济成本，传感器节点在通信和计算能力、内存和电池供电方面相对有限。传感器网络实现了许多应用，如车辆跟踪、战场侦察、生态和习惯监测等。

由于无线Mesh网络的低成本、快速部署的特点，Mesh作为一种新型通信范式被引入。应用场景有无线宽带互联网接入、智能传输系统、会议中心和疾病恢复中心即时网络。WMN被分为3类[10]：基础设施Mesh网络、客户端Mesh网络、混合Mesh。在基础设施Mesh网中，Mesh路由器提供一个无线的Mesh骨干基础设施。与传统的WLAN不同的是，有线骨干被无线多跳网络代替。Mesh客户端通过Mesh路由器简单、直接存取网络，客户端没有贡献Mesh网络基础设施,起了消极的作用。在客户端Mesh网络中，不包括专用的网络基础设施，仅由移动Mesh客户端组成，因此Mesh客户端需要完成网络功能，例如路由和包转发，使得客户端Mesh网络基本上与传统的ad-hoc网络相同。混合无线Mesh网络是最常见类型的WMN,结合了基础设施Mesh网络和客户端Mesh网络的概念，如图1所示。

图1 混合无线Mesh网络架构Fig.1 Hybrid wireless Mesh architecture

混合Mesh网络由静态Mesh路由器形成Level2骨干网络，其中一些Mesh路由器具有Level1网关功能和提供internet或其他网络的认知功能。此外，Level3的移动客户端能够实行静态网络基础设施部分的动态扩充，移动客户端实行路由和包转发功能。混合Mesh结构是最可行的因为Mesh客户端不仅能与别的Mesh客户端直接通信，而且通过Mesh路由器获得internet服务。本文中使用的是混合无线Mesh网络，Mesh客户端通过网关节点获得internet服务[11]。

混合无线Mesh网络是一个特殊类型的移动Ad-hoc网络类型，但是两者之间有明显的不同[12]。在混合Mesh网络中，Mesh路由器是相对强大的静态的节点，能够获得装有高容量电池的动力电源系统的能量[12]。通常Mesh路由器安装了分配不重叠信道多射频接口，明显增加了无线Mesh网络的传输性能。与Mesh路由器相反,Mesh客户端限制了连接设备，例如笔记本或PDA等客户端设备。在混合无限Mesh网络中，当Mesh客户端通过互联网络或其他网络的存取服务时，大多数通信量来源于网关或返回到网关。因此有效的策略需要考虑Mesh节点和通信量模式的不同。由于混合无线Mesh网络具有处理动态环境的能力，混合无线Mesh网络已经成为Ad-hoc网络路由协议的备选。

2 模型与算法

Mesh传感器网络通过允许网络自配置的办法应付网络配置问题。小的传感器通常叫做微尘,收集环境数据或者与附近低能量节点通信短距离无线接口。如果每个节点的定位能被决定，基于定位的路由算法可以使用[13]。这些方法中最简单的被称作前向贪婪，是因为一个节点前向包给其任何一个靠近目的节点的邻居节点。向前贪婪的操作如图2所示：包开始在h被向前到h的任意一个靠近目的节点g的节点，在本例中，是节点e。过程是当包被向前到节点f,m,d最终是g。向前贪婪不总是发现最优的路径但是它总是产生向目标节点的合理有效的路径。然而通过用这种方法结束节点堵塞对于包前向是可能的，在一个中间节点比任何邻居节点更靠近目标节点的地方，因此不能决定在哪里去前向包。例如包旅行从j到g,将被向前沿着路径j,k,l,当l没有邻居节点更比它本身更靠近g时，将被粘在l。例如(Greedy Perimeter Stateless Routing，GPSR)已经成为减轻当贪婪向前失败时使用的选择策略。

图2 向前贪婪Fig.2 Greedy forward

本文所使用的分布式贪婪生成树路由(Greedy distributed spanning tree routing，GDSTR)是一种新型的地理位置路由算法,该算法能找到更短的路由,生成树实现节能[14,15]。由于节点随时间不断发生变化及其无法实时更新，本文采用信道分配算法直接代替总线数据采集。主要目标是通过适当的配置存储区域来解决热点问题，避免多维搜索。人们的生存环境是真实的，会产生大量的监测数据，但是只有其中的一小部分会被查询。假设存在一个传感器领域，其中传感器节点统一部署并且初始过程时间同步。传感器节点的位置是固定的，并且可以利用全球定位系统(Global position system，GPS)技术应用设备精准确定自己的位置。本文使用GDSTR进行传感器网络中的各个分组传输。紧凑几何路由(Compact Geometric Routing，CGR)，GPSR与GDSTR的不同连接展度比较，如图3所示。展度(Stretch)指从源点到某一个成员之间在应用层组播树链路上的延时和在直接单播路径上延时的比值[9]。GPSR使用两种算法来实现路由过程，首先，传感器节点利用贪婪算法逐步向最接近目的地位置的邻居节点转发分组；如果贪婪算法无效，则使用周边前向算法。

图3 在相同节点数情况下不同连接展度比较Fig.3 Comparison of different connection stretchwith the same numbers of nodes

本文使用CIAR路由判据，图4为由G2网格和(G-1)2个交点构成的全局网格结构，即存储区域(SA)。

构建全局网格结构后，在传感器场中生成库容曲线。图5为SAi(i=1, 2, … , (G-1)2)标记的交点。库容曲线被传感器网络中的所有传感器节点所知。

图4 全局数据结构Fig.4 Globe data structure

图5 库容曲线Fig.5 The curve of storage capacity

如图6所示，定义一个参数Tp，将其分裂成(G-1)2个部分，其中每个时间段(TP)具有与其相关的存储区域(SA)。

图6 每个时间段与存储区域之间的关系Fig.6 The relations between each time periodand storage area

基于不完全信息的博弈模型的Mesh传感器网络，本文对路由和信道分配算法进行联合，提出了多接口路由与信道分配(Multi-interface routing and channel allocation game-local,MRCAG-Local)算法。仅考虑节点接口数量(α×β)大于信道数量(ω)的情况，即α×β>ω，算法伪代码如表1所示。

模型的数学描述如下：

路由算法基本公式为：

(1)

基本函数方程为：

(2)

表1MRCAG-Local算法伪代码

Table1PseudocodefortheMRCAG-Localalgorithm

1：随机为每一个节点的各个接口分配信道

2：do

3： {repeat

4：获取当前信道分配方案

5：对于每一个参与竞争节点wido

6： if 退避计算器=0

7： {

8：对于所有接口do

9： e=接口当前使用的信道

11： {

12：以一定概率将接口换至信道d*∈(D/Di)∩XI

13: }

14：重置退避计算器(从{1,2,…,δ}中选择初始值)

15： else退避计算器-1

16： }

17：while(未收敛至满足条件的信道分配方案)

隐藏层节点输出为：

(3)

输出节点的输出为：

(4)

其中，θ为输出节点阈值，wij为权值。

在线性关系下，基本方程为：

∂j(eijkl∂kul-ηkij∂kφ)=0

(5)

考虑到存在无限的情况，则使用如下公式：

(6)

考虑到存在扩展的情况，则用式(7)代替式(6)：

(7)

本文在研究了基于基站调度、随机和基于优先级调度方法中的服务节点的总数和延迟时间。在随机方法中，所有节点被随机排序，并且首先发送请求的节点将被首先调度。基于上述算法描述，将前述的MRCAG-Local算法联合基站调度算法综合分析后,研究了基站调度联合多接口路由信道分配算法(Basic station scheduling -multi-interface routing and channel allocation game-local, BSS-MRCAG-Local)伪代码如表2所示，MSSd为不同Mesh客户端(Mesh subscriber stations)。

表2BSS-MRCAG-LOCAL算法伪代码

Table2PseudocodefortheBSS-MRCAG-LOCAL

algorithm

输入:N<—MSSd, K<—第一层节点数,Mi <—通过节点i传递数据的节点数,a<—网络拓扑结构;

1：for i <—1 to k

2： {

3： Rgi=i/gi

4： μ=μ+rgi

5： Tri=ci*gi

6： }

7：for i<—1 to m

8： {

9： repeat

10： {

11： tri=tri+Traij

12： tri=tri+Tri

13： j=j+1

14： Until j>n

15： }

16： ABWi=tri*rgi

17： Pi=(rgi/μ)*NPi

18： }

输出: tri*rgi=ABWi分配带宽给每个客户端, (rgi/μ)*NPi=Pi为第一层的节点分配优先权;

假设模拟环境在100 m×100 m的观测区域内随机抛出100个传感器节点。具体仿真参数设置如下：节点初始能量为1 J，随机部署网络拓扑，节点通信传输范围100～200 m，数据传输能量消耗为45 nJ/bit，接收数据消耗为30 nJ/bit，分组大小为64 bit，通道衰落参数为0.3，仿真时间为300 s。最大迭代次数是1000次。

3 结束语

为了提高混合式无线Mesh网络的有效性和可靠性，本文提出了BSS-MRCAG-Local算法。本文所使用的GDSTR路由在相同节点数情况下与CGR、GPSR比较连接展度最低。采用了不完全信息动态博弈，即在动态博弈中，行动有先后次序。本文所使用的具有不完全信息的博弈模型，是在当前信道分配过程中，对于每一个参与竞争的节点，全部接口使用情况不全部知晓的情况下，以一定概率将接口切换至信道，并修正自己的初步判断的过程。

[1] Vieira L F M, Gerla M, Misra A. Fundamental limits on end-to-end throughput of network coding in multi-rate and multicast wireless networks[J]. Computer Networks, 2013, 57(17):3267-3275.

[2] Wang Q, Kim M, Shi Y, et al. Predict brain MR image registration via sparse learning of appearance and transformation[J]. Medical Image Analysis, 2015, 20(1):61-75.

[3] Chen J, He K, Du R, et al. Dominating set and network coding-based routing in wireless Mesh networks[J]. IEEE Transactions on Parallel and Distributed Systems , 2015, 26(2): 423-433.

[4] Zhi Jian, Yin Bao, Wang Jun-hui, et al. Design of a node architecture for logic-calculation nased all-optical network coding scheme[J]. Journal of China Universities of Posts & Telecommunications, 2013, 20(5):110-116.

[5] Li L, Gu R, Ji Y, et al. All-optical OFDM network coding scheme for all-optical virtual private communication in PON[J]. Optical Fiber Technology, 2014, 20(2):61-67.

[6] Chi K, Zhu Y H, Jiang X, et al. Practical throughput analysis for two-hop wireless network coding[J]. Computer Networks, 2014, 60(5):101-114.

[7] Kanagasabapathy A A, Franklin A A, Murthy C S R. An adaptive channel reconfiguration algorithm for multi-channel multi-radio wireless Mesh networks[J]. IEEE Transactions on Wireless Communications, 2010, 9(10):3064-3071.

[8] Saifullah A, Xu Y, Lu C, et al. Distributed channel allocation protocols for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems , 2014, 25(9): 2264-2274.

[9] Jung S, Sung J, Bang Y, et al. Greedy Local Routing Strategy for Autonomous Global Load Balancing Based on Three-Dimensional Potential Field[J]. IEEE Communications Letters, 2010, 14(9):839-841.

[10] Amalia F Foka, Panos E Trahanias. Probabilistic autonomous robot navigation in dynamic environments with human motion prediction[J]. International Journal of Social Robotics, 2010, 2(1):79-94.

[11] Jung S, Sung J, Bang Y, et al. Greedy local routing strategy for autonomous global load balancing based on three-dimensional potential field[J]. IEEE Communications Letters, 2010, 14(9):839-841.

[12] 王继红, 石文孝, 尚硕, 等. 无线Mesh网络负载与干扰感知传输时间路由度量[J]. 吉林大学学报: 工学版, 2015,45(1): 297-303.

Wang Ji-hong ,Shi Wen-xiao ,Shang Shuo ,etal .Load and interference-aware transmission time routing metrics for wireless mesh networks[J]. Journal of Jilin University (Engineering and Technology Edition), 2015, 45(1): 297-303.

[13] Liang Q, Yao D, Deng S, et al. Potential field based routing to support QoS in WSN[J].J Comput Inform Syst, 2012, 8(6).

[14] Maamar H R, Pazzi R W, Boukerche A, et al. A supplying partner strategy for mobile networks-based 3D streaming - proof of concept[C]∥ IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum,IEEE, 2010:1-6.

[15] Wu T Y, Chan H L. Integrate airtime metric and geocast over P2P-based VoD streaming cache[J]. Tamkang Journal of Science and Engineering, 2010, 13(1):99-106.