论文部分内容阅读
【摘要】本文提出了一种新的片上混合Mesh网络的路由算法SQOR (Selective Quality On-demand Routing)， SQOR与以前主要考虑单频的网络中的路由算法不同，它是基于对多频网络的路由特性的研究，具有一种新的路由优化判断准则。SQOR主要以提高吞吐量为目的，而不仅仅以跳数或者传输时延为准则。
【关键词】混合；路由；片上网络；算法
片上网络在基本概念和技术上与局域网（LAN)、广域网(WAN)以及并行计算机的互连网络类似，但是由于片上互连网络上作于不同的时间尺度和空间，它的设计原则有所不同[1]。片上混合Mesh网络具有自组织性和自愈的特点，并具有有效的移动用户管理和跟踪机制，是一种多跳的宽带网络结构，也是一种高容量、高速率的分布式网络[2]。目前主要观点认为，WMN是一种由线链路连接路由器和终端设备的静态网络。作为一种新型网络结构形态，Mesh结构已被纳入到802.16-2004, 802.16e和即将制定的802.11s标准中[3]。
1片上混合Mesh路由算法
最初设计的国防军用Ad-Hoc网络中各节点具有高速运动的特性，因而其主要的挑战之一在于如何控制其移动性。而对于针对商用的片上Mesh网络，更多的重点是放在如何提高其网络吞吐量、增大网络容量。微软公司最近提出了一种多RF收发器、多跳无线网络的路由协议MR-LQSR (Multi-Radio Link-Quality Source Routing)，在DSR协议的基础上采用最大吞吐量准则。通过研究表明，AODV路由算法有其固有优势，如不会形成路由环;当一条链路不可用时，可以高效地在整个网络中删除所有要利用这条无效链路的路由等。因此，在AODV的基础上，考虑多RF收发器，以提高网络吞吐量为目标，通过对各种影响网络性能的参数进行分析，实现最优路径的选择，从而提出一种新的路由算法SQOR-Selective Quality On-demand Routing.
2片上混合Mesh网络的路由机制
路由器一般采用三种基本的路山机制:基于运算的路由、基于源的路由和查表路由，分别说明如下:
1) 基于运算的路由：对于大多数规则的拓扑结构而一言，简单的运算足以选择输出端口。例如，在二维Mesh中，可以在每个数据包头中包含带符号的在各个维内传送距离。在路由器中的路由操作由以下运算给出:
方向条件
西(-x) △x<0 ；东(+x)△x>0
南(-y) △x=0，△y<0；北(+y )△x=0，△y>0
本处理器△x=0, △y=0
为了完成这类路由，路由器需要测试数据包头中的地址并对传送距离进行减1或加1。二维Mesh中决定路由的典型做法是先沿x方向运动，然后再沿Y方向运动，这称为维序路由。
2)基于源的路由：在这种方法中，源节点建立一个数据包头，它包含了沿路由各个路由器输出端口号，各个路由器只需要简单地从消息中分离端口号，然后把消息从指定的通道送出。这种方法的优点是路由器很简单，但是缺点是数据包头可能很大，而且长度不固定。
3)查表路由：每个路由器包含一个路由表，数据包头包含一个路由域，用它作为索引地址查表决定输出端口，该方法复杂度太高，更适合于LAN和VAN，而不适合片上网络。
本文处理器采用规则的多层Mesh拓扑结构，而且它的数据包大小固定，经过比较，决定采用基于运算的路由机制。
3片上混合Mesh网络的路由算法
根据划分方法不同，路由算法通常有:确定性路由、适应性路由，最短路由和非最短路由，分别说明如下:
确定性路由(Deterministic routing )：如果数据包的路由完全是由它的源和目的地决定的，与网络中其它流量无关，这种路由算法称为确定性路由。例如，在二维Mesh中，数据包先在x方向上路由，然后再在Y方向上路由，数据包不管其路径上的链路是否阻塞都要沿该路径走下去，这称为维序路由，它就属于确定性路由。
适应性路由(Adaptive routing )。适应性路由算法允许路径上的其它流量影响数据包的路由。例如，在二维Mesh中，如果沿维序路径链路阻塞或出错，数据包可以沿锯齿形的路由流向其目的地。与确定性路由相比，适应性路由最根本的优点是它允许节点对之间有多条合法路径，具各了容错的基本条件，而且还允许在可用链路上更广泛的分布流量，从而改善网络的利用率。它的缺点是增加了路由器的复杂度，导致路由时延的增加。
最短路由(Minimal routing)和非最短路由( Nonminimal routing ) ：如果路由算法仅选择通向目的地的最短路径，它就是最短路由，否则，它就是非最短路由。维序路由就是一种最短路由。
对于通信趋向于无规律的片上网络，其路由趋向于适应性路由;但是，对于通信可预测的片上网络来说，确定性路由可能更合适。片上网络通信是可预测的，而且它的多层Mesh网络可以通过双路由器来分布流量，减小阻塞对网络性能的影响，提高网络的容错能力。
【参考文献】
[1]张会霞.基于Wireless Mesh技术的宽带无线接入系统[J].山东通信技术，2003, 23(4):40-42
[2]杨群，杜新华.两种移动Ad Hoc网络协议及其性能比较[J].广东通信技术，2004, 24 (6):
作者简介：曹猛（1974.5--），男，大学本科，助理工程师，研究方向：计算机网络，实验教学
【关键词】混合；路由；片上网络；算法
片上网络在基本概念和技术上与局域网（LAN)、广域网(WAN)以及并行计算机的互连网络类似，但是由于片上互连网络上作于不同的时间尺度和空间，它的设计原则有所不同[1]。片上混合Mesh网络具有自组织性和自愈的特点，并具有有效的移动用户管理和跟踪机制，是一种多跳的宽带网络结构，也是一种高容量、高速率的分布式网络[2]。目前主要观点认为，WMN是一种由线链路连接路由器和终端设备的静态网络。作为一种新型网络结构形态，Mesh结构已被纳入到802.16-2004, 802.16e和即将制定的802.11s标准中[3]。
1片上混合Mesh路由算法
最初设计的国防军用Ad-Hoc网络中各节点具有高速运动的特性，因而其主要的挑战之一在于如何控制其移动性。而对于针对商用的片上Mesh网络，更多的重点是放在如何提高其网络吞吐量、增大网络容量。微软公司最近提出了一种多RF收发器、多跳无线网络的路由协议MR-LQSR (Multi-Radio Link-Quality Source Routing)，在DSR协议的基础上采用最大吞吐量准则。通过研究表明，AODV路由算法有其固有优势，如不会形成路由环;当一条链路不可用时，可以高效地在整个网络中删除所有要利用这条无效链路的路由等。因此，在AODV的基础上，考虑多RF收发器，以提高网络吞吐量为目标，通过对各种影响网络性能的参数进行分析，实现最优路径的选择，从而提出一种新的路由算法SQOR-Selective Quality On-demand Routing.
2片上混合Mesh网络的路由机制
路由器一般采用三种基本的路山机制:基于运算的路由、基于源的路由和查表路由，分别说明如下:
1) 基于运算的路由：对于大多数规则的拓扑结构而一言，简单的运算足以选择输出端口。例如，在二维Mesh中，可以在每个数据包头中包含带符号的在各个维内传送距离。在路由器中的路由操作由以下运算给出:
方向条件
西(-x) △x<0 ；东(+x)△x>0
南(-y) △x=0，△y<0；北(+y )△x=0，△y>0
本处理器△x=0, △y=0
为了完成这类路由，路由器需要测试数据包头中的地址并对传送距离进行减1或加1。二维Mesh中决定路由的典型做法是先沿x方向运动，然后再沿Y方向运动，这称为维序路由。
2)基于源的路由：在这种方法中，源节点建立一个数据包头，它包含了沿路由各个路由器输出端口号，各个路由器只需要简单地从消息中分离端口号，然后把消息从指定的通道送出。这种方法的优点是路由器很简单，但是缺点是数据包头可能很大，而且长度不固定。
3)查表路由：每个路由器包含一个路由表，数据包头包含一个路由域，用它作为索引地址查表决定输出端口，该方法复杂度太高，更适合于LAN和VAN，而不适合片上网络。
本文处理器采用规则的多层Mesh拓扑结构，而且它的数据包大小固定，经过比较，决定采用基于运算的路由机制。
3片上混合Mesh网络的路由算法
根据划分方法不同，路由算法通常有:确定性路由、适应性路由，最短路由和非最短路由，分别说明如下:
确定性路由(Deterministic routing )：如果数据包的路由完全是由它的源和目的地决定的，与网络中其它流量无关，这种路由算法称为确定性路由。例如，在二维Mesh中，数据包先在x方向上路由，然后再在Y方向上路由，数据包不管其路径上的链路是否阻塞都要沿该路径走下去，这称为维序路由，它就属于确定性路由。
适应性路由(Adaptive routing )。适应性路由算法允许路径上的其它流量影响数据包的路由。例如，在二维Mesh中，如果沿维序路径链路阻塞或出错，数据包可以沿锯齿形的路由流向其目的地。与确定性路由相比，适应性路由最根本的优点是它允许节点对之间有多条合法路径，具各了容错的基本条件，而且还允许在可用链路上更广泛的分布流量，从而改善网络的利用率。它的缺点是增加了路由器的复杂度，导致路由时延的增加。
最短路由(Minimal routing)和非最短路由( Nonminimal routing ) ：如果路由算法仅选择通向目的地的最短路径，它就是最短路由，否则，它就是非最短路由。维序路由就是一种最短路由。
对于通信趋向于无规律的片上网络，其路由趋向于适应性路由;但是，对于通信可预测的片上网络来说，确定性路由可能更合适。片上网络通信是可预测的，而且它的多层Mesh网络可以通过双路由器来分布流量，减小阻塞对网络性能的影响，提高网络的容错能力。
【参考文献】
[1]张会霞.基于Wireless Mesh技术的宽带无线接入系统[J].山东通信技术，2003, 23(4):40-42
[2]杨群，杜新华.两种移动Ad Hoc网络协议及其性能比较[J].广东通信技术，2004, 24 (6):
作者简介：曹猛（1974.5--），男，大学本科，助理工程师，研究方向：计算机网络，实验教学