无线Mesh网络关键技术
关键词：空间复用度；多信道；路由度量；负载均衡
Abstract:The Wireless Mesh Network (WMN) is a special kind of Ad hoc network with a hierarchical network structure. Its backbone transmission network has such characteristics as multi-hop, topology stability, no electricity supply constraints, convergence of flows. Improving the spatial reuse of spectrum is an effective approach to increase network capacity. The linchpin of this approach is to effectively control the interference range between wireless links. The multi-channel networking technology is one of the key technologies of WMN, and its core is the channel allocation through which the channel utilization can be maximized. The mutual interference between multi-hop wireless links should be considered when choosing the routing metrics in WMN. Through the load-balancing routing method, the network capacity and throughput of nodes can be improved.
Key words:spatial reuse; multi-channel; routing metric; load balancing
无线Mesh网络(WMN)是一种多跳、自组织的宽带无线网络，一般由Mesh路由器和Mesh客户节点组成。其典型结构是一种分级网络结构：Mesh路由器互联构成多跳无线骨干网，负责数据的中继；骨干网一般通过网关节点与其他网络互联，而Mesh客户节点通过Mesh路由器接入到WMN。通过WMN最终实现Mesh客户节点间、客户节点与Internet等其他网络间的互联互通。
与蜂窝移动通信系统不同，WMN是一种多跳的，具有自形成、自愈和自组织能力的无线网络。虽然WMN具有上述无线Ad hoc网络的特性，但是WMN与无线Ad hoc网络之间仍然存在许多重大差别。首先，Ad hoc网络中节点是移动的，所以其网络拓扑结构具有动态变化特性；而在WMN中，负责中继的Mesh路由器一般是静止的，所以骨干网的拓扑结构保持相对稳定。由于节点的移动性使得设备供电受限，在Ad hoc网络的组网协议设计中必须考虑功耗因素，而WMN的中继节点保持静止，便于实现外部供电，所以功耗的限制相对减弱。另外，Ad Hoc网络的设计目标是为了实现移动节点间的对等网络通信，而WMN 着眼于为各种业务需求的客户节点提供无线宽带接入功能。
对于任何一种无线网络来讲，提高网络传输容量都是组网协议首要的设计目标。与一般的多跳无线自组织网络相同，WMN中无线链路间也存在较强的相互影响，这使得“提高WMN网络传输容量”的设计目标更具挑战性。目前WMN组网协议设计的基本思路是：充分挖掘WMN自身特点，采用跨层联合设计，提高网络容量，同时提供一定的QoS保障。本文围绕“提高WMN网络容量”这一核心问题，从提高频谱空间复用度、多信道技术以及路由优化等方面分析并总结当前WMN组网协议中的相关关键技术。
1 提高WMN的空间复用度
WMN是一种多跳无线网络，由于无线信道的广播特性，网络中任意一条链路都和地理位置与其相邻的无线链路间存在相互干扰，制约了网络的传输容量。另一方面，由于无线信道的衰减特性，多跳网络具有潜在的空间复用特性。设法提高网络的空间复用度，就能增加并行传输的链路数目，从而提升网络容量。
具有高空间复用度的组网协议的WMN基本设计思想是：有效控制无线链路间的干扰范围。本文重点介绍采用高级物理层技术如定向天线、多输入多输出(MIMO)等的WMN和结合物理层功率控制的媒体接入控制(MAC)协议。
1.1 基于定向天线技术的WMN
与传统的全向天线不同，定向天线(智能天线)可以将能量集中于某一方向传输，使天线在该方向上具有最强的增益，而其他方向上增益较小。而正是由于定向天线的传播具有这种波束方向性，可以提高WMN的空间复用度。但是，在提高空间复用度的同时，定向天线也给共享信道的访问引入了新的问题：定向隐藏终端问题、“耳聋”问题以及接收节点定位问题。
定向隐藏终端问题是指：物理上相邻的节点，由于传输方向的不匹配彼此互不可见，形成隐藏终端。例如在图1中，相邻节点A、B分别向节点C发送，由于A、B在发送之前都无法通过载波侦听发现对方正在发送，即节点A、B是一对隐藏节点，所以传输会在节点C处发生碰撞。显然这种隐藏终端问题在全向天线网络中是不会发生的。“耳聋”问题是指：发送节点不能与某个节点建立无线通信，原因是该节点正在另一个方向上侦听或者接收。接收节点定位问题是指：在通信前，发送节点必须首先确定接收节点的位置，才能确定发射波束的方向，所以节点必须对邻居节点位置进行跟踪和定位。
D-MAC协议是基于IEEE802.11 分布式协调功能(DCF)的定向天线MAC协议。该协议通过定向发送请求发送(RTS)、数据(DATA)、确认(ACK)帧，达到减少暴露终端数目以及提高空间复用度，而允许发送(CTS)帧仍然采用全向传输，从而减少潜在的隐藏终端；协议采用全球定位系统(GPS)定位邻居节点。
基于带外音的定向MAC协议[1]提出采用全向带外音解决“耳聋”问题。协议采用定向传输RTS、CTS、DATA和ACK，当数据传输完毕后，收、发节点都调整回全向发送带外音，提示邻居节点可以与其通信。
文献[2]在IEEE802.11 DCF基础上提出定向虚拟载波侦听(DVCS)机制，协议通过对控制帧接收功率的测量，估算出信号的入射角度(AOA)，进而控制波束方向，实现定向传输。并且在DVCS机制中，节点为每一个方向都设置相应的网络分配向量(NAV)。
1.2 WMN中的功率控制
在无线Ad hoc网络中，由于移动性节点一般采用电池供电，所以需要通过功率控制来降低节点的能耗；而与Ad hoc网络不同，WMN中节点一般不存在供电限制，所以在WMN中，功率控制的目的是：节点控制共享信道的覆盖范围，从而减小邻近无线链路干扰，增加网络的空间复用度，提高WMN的网络容量。
在WMN中，节点可以根据网络环境动态控制发送功率，也可以动态调整载波侦听的门限参数以控制功率，或者是二者协同控制。功率控制仍需要解决一些技术问题，例如：如何在保持网络连通性的前提下，提高网络空间复用度；发射功率与载波侦听门限在控制空间复用度方面存在何种关系；如何确定节点的发射功率以实现网络性能最优化。其中，确定每个节点的发射功率是一个难题。减小节点的发射功率可以提高信道的空间复用度，但是可能造成节点间数据传输率减小，数据流端到端时延增加。如果增大发送功率，节点间通信距离随之增加，数据流端到端时延可能降低，但这样又会使信道的空间复用度减小，降低网络容量；同时如何在WMN中实现分布式的功率控制也具有相当难度。
早期的功率控制研究大多集中在基于图模型的拓扑控制方面。在图模型中，如果两个节点间的距离在其传输范围之内，那么这两个节点就是邻居节点，这两个节点间就存在一条边。而传输范围取决于发射功率，路径损耗，以及接收灵敏度等因素。在这种模型下，功率控制的目标是在保持连通性的前提下，尽量减小节点的度数。这一目标是建立在一个基本观点之上：低节点度数，意味着较小链路干扰。而最近研究[3-4]认为：图模型并不能完全刻画无线链路间的相互干扰，转而采用基于信干噪比值(SINR)的物理模型研究功率控制。载波侦听的门限值决定了通信节点能够在多大覆盖范围内不会因其他传输而干扰。文献[5]提出了一种能够动态调整载波侦听的门限值提高空间复用度的功率控制算法。
2 WMN中的多信道技术
基于多信道的WMN组网技术是提高WMN容量的最有效的方法，受到研究者的高度重视。
2.1 多信道网络模型
多信道MAC模型可以分为以下3种类型，如图2所示：
- 单接口(网卡)多信道。只有一个收发器可用，每个网络节点在同一时间只有一个信道是活动的。不同的节点在同一时间可以工作在不同的信道上，从而提高系统容量。
- 单接口多收发器多信道。一个接口上采用多个收发器共用一组信道。多个物理层实体通过一个MAC层来协调多信道的功能。
- 多接口多信道。一个网络节点有多个具有独立MAC和物理层的接口。这些接口的通信是相互完全独立的。因此，需要虚拟一个子层协议，实现在多个MAC实体之上协调所有信道的通信。
2.2 多信道分配
信道分配是多信道技术中的一个关键问题。多接口WMN环境下的信道分配，主要目的是在保证网络连通度的基础上，获得最大信道利用率。信道分配主要包括固定信道分配方式、动态信道分配方式和混合信道分配方式。
(1) 固定信道分配方式
固定分配机制将信道永久地、或者是长时间(相对接口切换时间)地分配给某一个接口，在信道分配后不再考虑拓扑和负载的变化。这种方式适合网络稳定、拓扑和负载变化小的环境中。这种机制又可以细分为公共信道分配(CCA)模式和差别信道分配(VCA)模式。
CCA模式是最简单的一种机制。在CCA模式中，给每个节点分配相同的一组信道。如图3(a)所示，每个节点有两个接口，使用相同的两个信道。由于这种方式过于简单，并不能高效地利用网络资源。
(2) 动态信道分配方式
动态信道分配方式适应于网络负载变化大的情况。该方式仍然允许任何接口被分配到任意的信道上，但是和固定分配方式不同的是，在初始化分配后，动态信道分配方式仍然允许接口从一个信道切换到另一个信道。因此，在动态信道分配中，需要有一个协调机制，以保证需要互相通信的节点能够处于一个共同的信道。
一种典型的协调机制是，所有的节点周期性的访问一个预先制定的信道，在这个信道上协商下一个周期的信道使用。分时隙种子化频道跳变(SSCH)[10]提出了另一种机制，在该机制下，每个节点依照一个伪随机序列同步的切换信道，以保证所有的邻居能够周期性的拥有相同的信道。采用控制信道方式也是常见的一种协调机制。这种方式下，一个接口被固定分配到一个公共信道上，用于信道控制；其他的接口可以在剩余的信道上切换，用于数据交换。文献[11]中提出根据负载变化动态分配信道，以提高网络总吞吐量，并获得较好的负载平衡。算法中以每个网关节点为根，建立多棵生成树拓扑。
动态信道分配方式的好处在于能够把接口切换到任何信道，从而提供了在少量的接口上使用多个信道的潜在能力。动态切换方法的主要问题在于如何决策何时切换信道，以及将接口切换到哪一个信道。
(3) 混合分配方式
混合信道分配方式[12]结合了固定分配和动态分配的特点。在这种方式下，一部分接口使用固定分配方式，其他接口使用动态分配方式。固定接口可以分配一个专门的控制信道，或者是一个数据/控制混合信道，而其余的接口可以动态地在信道间进行切换。
3 WMN中的路由优化
在多跳网络中，由于相邻无线链路间存在相互干扰，使得中继节点的转发过程将会抑制其邻居节点的发送，所以，在WMN中，不同路径的数据流间，同一路径上相邻链路间都存在某种程度的干扰，制约着WMN的网络容量。
另一方面，WMN的骨干网具有拓扑相对稳定，无功耗约束，多跳中继，业务流量汇聚于网关等特点，所以可以通过对路由的合理优化，减小无线链路干扰，提高网络容量。
3.1 WMN中路由度量的选取
路由度量是路由选择的基础，传统无线Ad hoc网络中所普遍采用的跳数不能反映出多跳网络中的干扰特性，对QoS支持力度很弱。所以WMN应该采用支持QoS的路由度量机制，根据无线链路状态以及高层需求等信息，综合评估链路度量值，并形成最优路由，有效增加网络可用带宽和容量。
无线信道通信质量依赖于背景噪声、障碍物、信道衰减以及其他通信产生的干扰等。一般链路层协议在有数据帧发生丢失时，通常会进行重传操作。根据此特点，De Couto等人提出了基于期望传输次数(ETX)的路由度量方法[13]，ETX定义为WMN网络节点的MAC层在一条无线链路上成功交付一个数据帧所需传输次数的期望值。基于ETX的路由算法认为，降低帧重传次数也就是增大了网络的吞吐量。所以，这类路由算法选择最优路径上所有链路的ETX的总和应为最小。
Koksal等人通过研究指出[14]，由于无线网络信道状态的时变性，ETX不能够准确的度量无线信道质量。为了解决这个问题，Koksal等人在ETX的基础上提出了修正EXT(mETX)方法作为路由度量参数[15]，在度量值中引入表示信道的相对较快变化特性的参数。
在最优路径的选取过程中，还应采用跨层协作机制，综合考虑高层与链路层对误比特率的要求，例如传输控制协议(TCP)要求在某条链路上误帧重传次数不能超过给定门限值，若超过门限，将引起传输层重传，触发TCP慢启动机制，造成网络性能的降低。有效传输次数(ENT)[15]度量方法的引入较好地解决了这个问题。研究表明，在真实的WMN网络中使用ENT路由方式，相对于ETX方式，平均丢帧率可以降低50%。
3.2 WMN中负载均衡路由
负载均衡的主要动机是通过均衡网络资源的使用，从而提高网络容量和节点的吞吐率。在WMN网络中，负载不均衡主要体现在网关节点、网络中心部分以及瓶颈节点处。
WMN网络中，大量流量将在网关节点汇聚，网关节点的处理能力将制约整个WMN网络的容量。对于多网关节点的WMN网络，要考虑如何在网关节点间分配流量，避免负载不均。特别的，当各个网关节点具有不同类型、不同带宽的外部接入链路时，还需要综合考虑到这些不同外部接入链路的传输能力对负载均衡分配方案的影响。
在网关节点间进行负载均衡通常采用的策略有：基于移动边界的负载均衡(MBLB)、基于节点分割的负载均衡(PHLB)、基于概率分条的负载均衡(PSLB)。在MBLB和PHLB方法中，每个Mesh节点各自仅利用一个网关节点作为出网通道；而PSLB方法中，每个Mesh节点可以分别同时利用多个网关节点作为出网通道，这样在理论上可以达到完全负载均衡。
WMN网络中心区域的节点与其他节点相比，容易产生过载现象，原因是大部分采用“最短路径”的路由算法会使的中部节点正好位于大多数“最短路径”上。该问题的解决方案是通过路由的方式，将负载动态分布在较轻负载的节点上，避免对中心区域节点的过载。解决方案大都采用基于环状路由的负载均衡方法[16]，其基本思想是：将整个WMN网络区域划分为多个同心环，每个节点都位于一个环中。从环i中的源节点到环j中的目的节点的流量尽可能的不传递到环i和环j外的节点上去。
现有的基于环的负载均衡算法有：外环优先路由法(PORS)、内环优先路由法(PIRS)、目的环优先路由法(PDRS)、源环优先路由法(PSRS)。其中PORS和PIRS分别将主要流量集中在外环或内环中，而PSRS和PDRS是前两种方法的综合，将流量分配在内外环中，进一步均匀了负载。从图4中可以看出，相对于传统的最短路径算法，以上4种方法可以分散流量，有效减轻中心区域节点的负载。
4 结束语
WMN是一种特殊的Ad hoc网络，具有分层的网络结构，其传输骨干网具有多跳、拓扑稳定、无供电约束等特性。同时作为宽带无线接入网络，WMN通过网关节点与其他类型的网络实现互联，业务流量相对汇聚。如何针对WMN的特点，提高网络的通信性能仍然是目前研究的热点问题，而增加WMN的网络容量是其中关键而又基础的问题。除此之外，尚有一些关键技术问题有待进一步解决，如WMN的QoS保障、分布式网络管理、控制机制、WMN安全机制等问题。尽管如此，我们相信WMN必将成为下一代无线网络中的主流技术之一。
5 参考文献
[1] Choudhury r r, Vaidya n h. Deafness: A MAC problem in ad hoc networks when using directional antennas[C]//Proceedings of IEEE 12th International Conference on Network Protocols (ICNP’04), Oct 5-8, 2004. Berlin, Germany. Piscataway, NJ, USA: IEEE, 283-292.
[2] Takai m, Martin j, Ren a, et al. Directional virtual carrier sensing for directional antennas in mobile ad hoc networks[C]// Proceedings of 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’02), Jun 9-11, 2002, Lausanne, Switzerland. New York, NY, USA: ACM, 2002: 83-193.
[3] Burkhart m, Rickenbach p, Wattenhofer r, et al. Does topology control reduce interference？ [C]// Proceedings of 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’04), May 24-26, 2004, Tokyo, Japan. New York, NY, USA: ACM, 2004: 9-19.
[4] Fuemmeler j a, Vaidya n h, Veeravalli v v. Selecting transmit powers and carrier sense thresholds for CSMA protocols[R]. Urbana-Champaign, IL, USA: Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 2004.
[5] Zhu j, Guo x, Yang l, et al. Adapting physical carrier sensing to maximize spatial reuse in 802.11 mesh networks[J]. Wireless Communications and Mobile Computing, 2004, 4(8): 933-946.
[6] Raniwala a, Gopalan k, Chiueh t. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks [J]. ACM Mobile Computing and Communications Review, 2004, 8(2): 50-65.
[7] Marina m, Das s r. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[C]// Proceedings of the 2nd IEEE International Conference on Broadband Networks: Applications and Services Symposium (BroadNets'05), Oct 3-7, 2005, Boston, MA, USA. Piscataway, NJ, USA: IEEE, 2005: 381-390.
[8] Subramanian a, Gupta h, Das s r. Minimum-interference channel assignment in multi-radio wireless mesh networks[C]//Proceedings of 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks( SECON '07), Jun 18-21, 2007, San Diego, CA, USA. Piscataway, NJ, USA:IEEE, 2007: 481-490.
[9] Rad a h m, Wong v w s. WSN16-4: Logical topology design and interface assignment for multi-channel wireless mesh networks[C]// Proceedings of IEEE Global Telecommunications Conference (Globecom' 06), Nov 27-Dec 1, 2006, San Francisco, CA, USA. Piscataway, NJ, USA: IEEE, 2006:1-6.
[10] Bahl p, Chandra r, Dunagan j. SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks[C]// Proceedings of 10th Annual International Conference on Mobile Computing and Networking (MOBICOM'04), Sep 26-Oct 1, 2004, Philadelphia, PA, USA. New York, NY, USA: ACM, 2004: 216-230.
[11] Raniwala a, Chiueh t. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05): Vol 3, Mar 13-17, 2005, Miami, FL, USA. Piscataway, NJ, SA:IEEE, 2005: 2223-2234.
[12] Ramachandran k, Almeroth k, Belding-Royer e, et al. Interference-aware channel assignment in multi-radio wireless mesh networks[C]// Proceedings of 25th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’06): Vol 3, Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: IEEE, 2006: 1-12.
作者简介：
吴凡，电子科技大学通信与信息工程学院在读博士研究生。先后参加多项国家“863”项目，主要研究领域为无线自组织网络、无线路由技术。 毛玉明，电子科技大学通信与信息工程学院教授、博士生导师。先后主持多项国家“863”项目，拥有多项专利。目前主要研究方向为宽带无线通信网络、宽带通信网技术和高速信息处理技术。 张科，电子科技大学通信与信息工程学院在读博士研究生。先后参加多项国家“863”项目，主要研究领域为无线自组织网络QoS、网络测量技术。