三维Mesh网络

三维Mesh网络（精选7篇）

三维Mesh网络 第1篇

1 三维Mesh网络的容错数学模型

定义1(三维MESH网络):三维MESH网络Mm×n×q构成一个立方体,共有m×n×q个结点,其中结点按坐标(x,y,z)给出,x=1,2,…m,y=1,2,…n,z=1,2,…q。两个结点为邻接结点指的是它们的坐标值只有一位不同且差值为1。

定义2:三维Mesh网络Mm×n×q中的一个k-Mesh子网M(k)a,b,c(在本文有时也用Mk表示)由三个整数确定,0≤a≤m/k,0≤b≤n/k0≤c≤q/k(为讨论简单起见,这里假设m、n和q都可以被k整除)。这样,在Mm×n×q中的一个k-Mesh子网M(k)a,b,c就包含了k3个结点,组成其结点的坐标分别为(x,y,z)。这里x,y,z的取值范围分别为ak+1≤x≤(a+1)k,bk+1≤y≤(b+1)k,ck+1≤z≤(c+1)k。

定义3:如果三维Mesh网络Mm×n×q中每个k-Mesh子网相邻面上分别至少各有一个正确的结点相邻接,且每个Mk中所有正确结点构成一个连通图,则称三维Mesh网络Mm×n×q为局部k-Mesh子网弱连通的。

定理1:在三维Mesh网络Mm×n×q中,如果三维Mesh网络是局部k-Mesh子网弱连通的,则所有正确结点构成一个连通图。

证明:假设是三维Mesh网络Mm×n×q是局部k-Mesh子网弱连通的。由定义,每个Mk正确结点构成一个连通图,又Mm×n×q中任意两个有相邻面的Mk子网的相邻面上分别至少各有一个正确的结点相邻接,故局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q两个有相邻面的Mk子网正确结点是连通的。

下面我们证明局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q中的正确结点构成一个连通图。为证明这一定理,我们只需要证明Mm×n×q中的任意两个正确结点u和v之间存在一条正确结点构成的路径。假设结点u位于Mesh子网M(k)a,b,c中,结点v位于k-Mesh子网M(k)a*,b*,c*中。不失一般性,假设a≤a*,b≤b*,c≤c*(其它情况可以类似地被证明)。结点u所在的k-Mesh子网M(k)a,b,c和M(k)a+1,b,c有相邻面,故M(k)a,b,c中正确结点和M(k)a+1,b,c正确结点是连通的,又k-Mesh子网M(k)a+1,b,c和M(k)a+2,b,c有相邻面,故M(k)a+1,b,c中正确结点和M(k)a+2,b,c正确结点是连通的,得结点u和M(k)a+2,b,c正确结点是连通的,此过程一直继续可得结点u和M(k)a*,b,c正确结点是连通的。k-Mesh子网M(k)a*,b,c和M(k)a*,b+1,c有相邻面,过程如上,可得结点u和M(k)a*,b*,c正确结点是连通的。k-Mesh子网M(k)a*,b*,c和M(k)a*,b*,c+1有相邻面,过程类似,可得结点u和M(k)a*,b*,c*正确结点是连通的。故必定存在一条起始点为k-Mesh子网M(k)a,b,c中的结点u,终止点为k-Mesh子网M(k)a*,b*,c*中的结点v的正确结点构成的路径。证毕。

根据定义3,局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q的每个k-Mesh子网每个面上至少有一个正确的结点,每个kMesh子网共有6个面。因此,局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q中比k-Mesh子网连通的三维Mesh网络Mm×n×q可多达接近6(k2/2-1)×(m/k)×(n/k)×(q/k)个错误结点。且随着k的增大,局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q容错能力将逐渐增加,同时还增强了通用性。

2 单播算法

上述定理1的证明同时提出一个局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q单播容错路由算法,且算法是基于局部信息和分布式的。

算法基本思想:假设源节点u在k-Mesh子网M(k)a,b,c中,目的结点v在k-Mesh子网M(k)a*,b*,c*)中,算法首先在M(k)a,b,c和的相邻面寻找一对邻接的正确结点。然后在k-Mesh子网序列M(k)a,b,c,M(k)a+1,b,c,…,M(k)a*,b,c,M(k)a*,b+1,…,M(k)a*,b*,c,M(k)a*,b*,c+1,…,M(k)a*,b*,c*中构造一条由正确结点组成的路径。

算法Ⅰ:局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q中的单播路由算法

输入:含有错误结点的三维Mesh网络Mm×n×q中两个正确结点u=(xu,yu,zu)、v=(xv,yv,zv)。

输出:三维Mesh网络Mm×n×q中连接结点u和v的由正确结点组成的路径。

1)输入结点u=(xu,yu,zu)、v=(xv,yv,zv);

2)确定u所在的k-Mesh子网M(k)a,b,c及v所在的k-Mesh子网M(k)a*,b*,c*,这里:

3)令w=(xu,yu,zu),初始化路径:P←w;

{至此,己经构造了一条从u到w的正确结点的路径。}

(1)分别找到M(k)h,b,c和M(k)h+1,b,c相邻面一对邻接的正确结点w1和w2;

(2)扩展路径P:在M(k)h,b,c中从w扩展到w1,然后扩展到w2,w=w2;}

(1)分别找到M(k)a*,h,c和M(k)a*,h+1,c相邻面一对邻接的正确结点w1和w2;

(2)扩展路径P:在M(k)a*,h,c中从w扩展到w1,然后扩展到w2,w=w2;}

(1)分别找到M(k)a*,b*,h和M(k)a*,b*,h+1相邻面一对邻接的正确结点w1和w2;

(2)扩展路径P:在M(k)a*,b*,h中从w扩展到w1,然后扩展到w2,w=w2;}

7)扩展路径P:在M(k)a*,b*,c*中从w扩展到v。

(注:如果算法在任何一处无法继续,三维Mesh网络Mm×n×q不是局部k-Mesh子网弱连通的。)

算法分析:算法Ⅰ的主要时间花在第4)步、第5)步和第6)步上。第4)步的(1)步要求在k-Mesh子网M(k)h,b,c和k-Mesh子网M(k)h+1,b,c相邻面寻找一对邻接的正确结点w1和w2,所需时间为o(k2)。第4)的第(2)步要求在M(k)h,b,c中从w扩展到w1,然后扩展到w2,w=w2;,其时间复杂性为o(k3),第4)步所需时间为(a*-a)(o(k2)+o(k3))=(a*-a)o(k3)。同理第5)步、第6)步中所需时间为(b*-b)o(k3)、(c*-c)o(k3)。第7)步中所需时间和4.1步相同为o(k3)。

又所以算法Ⅰ的时间复杂度为当k取值很小,算法Ⅰ的运行时间满足线性时间复杂度。

3 广播算法

容错广播通信算法的基本思想是:首先把三维MESH网络Mm×n×q分为(m/k)×(n/k)×(q/k)个不相交的规模为k×k×k的k-MESH子网,确定源结点u所在的k-MESH子网M(k)a,b,c,算法首先在M(k)a,b,c内广播,然后沿着a±1、a±2、…;b±1、b±2、…;c±1、c±2、…方向在k-MESH子网之间广播。

算法Ⅱ:局部k-Mesh子网弱连通的三维Mesh网络Mm×n×q中的广播路由算法:

1)在k-Mesh子网M(k)a,b,c内部在含结点u=(xu,yu,zu)所在的连通图中构造以结点u为根的生成树的同时在该k-Mesh子网M(k)a,b,c内沿该树将其信息广播;其中;

2)分别找k-MESH子网M(k)j,b,c和M(k)j+1,b,c相邻面上一对邻接的正确结点Wj、Wj+1,并通过Wj把信息传到Wj+1,然后在M(k)j+1,b,c所在的连通图中构造以结点Wj+1为根的生成树的并且沿树将其信息广播(这里j=a,a+1,…,m/k-1),同时在k-MESH子网M(k)i,b,c和M(k)i-1,b,c相邻面上找一对邻接的正确结点Vi、Vi-1,并通过Vi把信息传到Vi-1,然后分别在M(k)i-1,b,c所在的连通图中构造以结点Vi-1为根的生成树的同时沿树将其信息广播(这里i=a,a-1,…,0);

3)对于k-MESH子网M(k)j,h,c(这里j=0,1,…,m/k-1))分别找k-MESH子网M(k)j,h,c和M(k)j,h+1,c相邻面上找一对邻接的正确结点Ujh、Uj(h+1),并通过Ujh把信息传到Uj(h+1),然后在M(k)j,h+1,c所在的连通图中构造以结点Uj(h+1)为根的生成树的并且沿该树将其信息广播(这里h=b b+1,…,n/k-1),同时在k-MESH子网M(k)j,k,c和M(k)j,k-1,c相邻面上找一对邻接的正确结点Vjk、Vj(k-1),并通过Vjk把信息传到Vj(k-1),然后分别在M(k)j,k-1,c所在的连通图中构造以结点Vj(k-1)为根的生成树的同时沿树将其信息广播(这里k=b,b-1,…,0);

4)对于k-MESH子网M(k)j,h,l(这里j=0,1,…,m/k-1;h=0,1,…,n/k-1)分别找k-MESH子网M(k)j,h,l和M(k)j,h,l+1相邻面上找一对邻接的正确结点Ujhl、Ujh(l+1),并通过Ujhl把信息传到Ujh(l+1),然后在M(k)j,h,l+1所在的连通图中构造以结点Ujh(l+1)为根的生成树的并且沿该树将其信息广播(这里l=c,c+1,…,q/k-1),同时在k-MESH子网M(k)j,h,p和M(k)j,h,p-1相邻面上找一对邻接的正确结点Vjhp、Vjh(p-1),并通过Vjhp把信息传到Vjh(p-1),然后分别在M(k)j,h,p-1所在的连通图中构造以结点Vjh(p-1)为根的生成树的同时沿该树将其信息广播(这里p=c,c-1,…,0);

(注:如果算法在任何一处无法继续,三维Mesh网络Mm×n×q不是局部k-Mesh子网弱连通的。)

算法分析:当源和目的结点在k-Mesh子网内的同一个连通图中时,在在k-Mesh子网内部沿连通图的生成树进行信息广播,因k-Mesh子网内部共k3个节点,故信息沿k-Mesh子网内部的生成树中进行广播,需耗时O(k3)。有相邻面的两个k-Mesh子网在相邻面上寻找一对正确的邻接点需耗时O(k2)。故广播共需耗时(mnq)/(k-1)3O(k3)+2(m/(k-1)-2)2(n/(k-1)-2)2(q/(k-1)-2)O(k2)=O(k3(mnq)/(k-1)3)。

4 结论

该文通过对对三维Mesh网络容错模型的研究,提出了局部k-Mesh子网弱连通的概念,在局部k-Mesh子网弱连通的三维Mesh网络中提出了基于局部信息和分布式的单播、广播容错路由算法。新的容错模型提高了三维Mesh网络的容错能力,而且增强了通用性,从而使得该算法具有很好的实际意义。

参考文献

[1]Alverson R.The tera computer system[C].Proceedings of the 4th international conference on Supercomputing,1990:1-6.

[2]Allen F.Blue gene:A vision for protein science using a petaflop supercomputering[J].IBM Systems Journal,201:310-327.

[3]清华大学.三维mesh网中无死锁的平面自适应路由方法[p].中国:200810101592,2008-09-17.

[4]向东,陈爱,孙家广.基于局部故障块三维mesh/torus网的容错路由[J].计算机学报,2004,27(5):611-618.

[5]Chen X,Wu J.Minimal routing in 3-D meshes using extended safety levels[C].Las Vegas:Proceedings of the 10th IASTED InternationalConference on Parallel and distributed Computing and Systems,1998,385-390.

[6]Jiang Z,Wu J.A limited–global-information model for dynamic routing in 3-D meshes[C].Louisville:the 15th International Conferenceon Parallel and Distribute Computing Systems(PDCS'O2-ISCA),2002.

[7]Wang G C,Chen J E,Wang G J.On Fault Tolerance of 3-Dimensional Mesh Networks[J].J comput sci&technol,2004,19(2):183-190.

[8]王高才,李陶深,陈建二.三维Mesh网络容错路由算法及其概率分析[J].小型微型计算机系统,2005,26(11):1996-1999.

移动Mesh网络定位系统研究 第2篇

关键词：网状网络,移动定位,正交频分多路复用,到达时间差

0 引言

近年来,无论是在军用还是民用领域,对移动目标定位的应用需求日益强烈。移动位置服务业务已成为最具增长潜力的增值业务之一[1]。当前,移动定位系统研究重点在于定位信息的获取和处理以及提高定位精度和准确度等方面。移动Mesh技术适合于区域环境覆盖和宽带高速无线接入。结合移动Mesh网络宽带高、频谱利用率高的优势,以及具有网络自组织、自维护等特点[2],提出了一种基于移动Mesh网络的定位系统,在对移动Mesh网络及TDOA(Time dispersion of arrival)定位算法分析的基础上,给出了在3 km×2 km无线覆盖区域中移动Mesh网络“锚”节点(含有卫星定位模块,具有自定位功能的移动Mesh节点)配置方案,利用Mesh节点作为“锚”节点,建立相对坐标系,移动终端通过测量与 “锚”节点之间距离,并通过TDOA定位算法获得自身相对位置信息,最后对系统定位性能进行了仿真分析。

1 移动Mesh网络定位技术及定位原理

移动定位是利用移动通信网络,通过对接收信号特征测量分析并计算,为移动终端用户提供相关的位置信息服务[3]。

移动Mesh网络(无线网状网络)也称为“多跳(multi-hop)”网络,它是一种与传统无线网络完全不同的新型无线网络技术,是真正无中心的网络。相对其他无线定位系统,移动Mesh通信网络实现定位有其显著的优势,第一,各Mesh节点均可自由移动,网络拓扑结构具有随机性,又因为Mesh网络无中心节点,因此其抗毁性是其他无线网络所不能比拟的;第二,采用纯IP网络技术,移动Mesh网络拓扑结构可以无限扩展,支持任意数量的节点随意接入;第三,Mesh采用同步网络技术体制,利用系统同步机制,可以方便地得到移动终端与Mesh节点之间的定时同步(信号延时),进而计算得到它们之间的距离,使其具有了自组织定位能力的先天优势;第四,Mesh支持移动(Point to MutiPoint)模式,为终端拓展提供了便利条件;第五,Mesh支持MAC层设计,具有QOS性能,安全性更高。

移动Mesh网络定位原理与步骤如下:① 建立区域内无线通信网络。建立无线通信网络,满足所有Mesh节点与移动终端之间的网络传输要求;② 实现网络内各单元的定位。以无线通信网络为基础,采用一定的定位方法实现各无线通信单元的定位。

无线通信网络主要考虑因素有:

① 建立无线局域网(WLAN),能够满足一定区域内所有节点之间的互联互通;② 保证每个移动终端最少与3个以上Mesh节点互联互通以实现定位计算。

采用符合IEEE 802.16e协议的移动Mesh通信网络体制,信道编码采用OFDM技术,选用5 GHz通信频段,最大物理层传输速率20 Mbps,通信距离2~5 km,采用QPSK/QAM自适应调制,TDD双工模式。

实现系统定位主要考虑因素有:

(1)利用OFDM符号定时同步实现测距

OFDM系统中,发送端信号经过IFFT,接收端要正确解调就必须确定FFT窗口的准确位置,这就产生了所谓OFDM系统符号同步问题[4]。确定FFT的窗口位置,关键是定时估计要准确,即在接收端,通过定时估计得到的时延估计值推算出OFDM符号的起始位置,并将FFT窗口位置调整到此位置。经过调整后,FFT窗口就能够包含OFDM符号上当前帧的全部样值点,最后实现正确的解调。如果对OFDM系统的定时估计不准确,位置没有定位在OFDM帧结构的第1个样值点上,就会引起符号间干扰,造成通信误码或中断。由上可见,OFDM符号同步的关键是定时估计。

这里采用了一种对称共扼序列作为训练序列的定时估计算法,序列结构示意图如图1所示。其中,A部分的序列是由Nu/4(Nu≤N)长的PN序列经过N/4点的IDFT产生,B*部分由A的共扼对称序列产生。

利用A和B的对称性,定时测度表达式为:

$\text{Μ}(\text{θ})=\frac{|\text{Ρ}(\text{θ})|{}^2}{(\text{R}(\text{θ})){}^2}$;

其中:

$\text{Ρ}(\text{θ})={\displaystyle \sum _{\text{k}=0}^{\text{Ν}/2-1}\text{r}}(\text{θ}-\text{k}+\text{Ν}/2-1)\text{r}(\text{θ}+\text{k}+\text{Ν}/2)$,

$\text{R}(\text{θ})={\displaystyle \sum _{\text{k}=0}^{\text{Ν}/2-1}|}\text{r}(\text{θ}+\text{k}+\text{Ν}/2)|{}^2$;

在接收端,将M(θ)取得最大值所对应的采样位置取为定时估计的位置,即定时估计值为:

$\widehat{\text{θ}}=\underset{\text{d}}{{\displaystyle max}}(\text{Μ}(\text{θ}))$。

在此算法中,由于R(θ)取值为始终正,从而对P(θ)进行了归一化,但同时也使运算量会增加一倍。由于P(θ+1)和P(θ)的数据不同,由序列的共扼对称性可知P(θ)只有在准确点时出现一个峰值,因此得到的定时估计的精度较高。

OFDM系统中,信号时延τ为收到信号起始时刻tr加上信号偏差θT,再减去信号发送时刻ts:

τ=tr+θT-ts。

通过对N个OFDM符号进行定时估计可以得到N个测距值,取其平均值,从而得到更为准确的估计值。一般情况下,N取值可为4n,比如256、1 024等,N值越大估计值越精确,但同时运算量也成几何倍数增加。

$\text{τ}{}_{\text{m}\text{e}\text{a}\text{n}}=\frac{1}{\text{Ν}}{\displaystyle \sum _{\text{i}=1}^{\text{Ν}}\text{τ}}{}_{\text{i}}$,

利用信号时延与距离的关系,很容易得到基站与终端之间距离为:

Ri=C×τmean(i),

式中,c代表光速,Ri指终端与第i个“锚”节点之间距离,τ(i)指终端与第i个锚节点信号时延。

(2)通过计算得到定位结果

测距算法采用TDOA,定位算法采用最大似然估计算法[5,6]。

最大似然估计算法是常用的定位算法。它对三边定位算法进行了改进,通过增加已知节点数量,利用冗余信息加权定位限制,使定位精度得到很大程度上的提高。所以最大似然估计算法也称作多边定位算法。

最大似然估计算法中,已知n个基站坐标分别为B1(x1,y1),B2(x2,y2),……,Bn(xn,yn),与移动终端M(x,y)测得的距离分别为d1,d2,……,dn,如图2所示。

类似三边定位算法,可以由已知条件建立方程组如下:

$\{\begin{array}{c}(\text{x}-\text{x}{}_1){}^2+(\text{y}-\text{y}{}_1){}^2=\text{d}{}_1^2\hfill \\ (\text{x}-\text{x}{}_1){}^2+(\text{y}-\text{y}{}_1){}^2=\text{d}{}_1^2\hfill \\ ⋮\hfill \\ (\text{x}-\text{x}{}_{\text{n}}){}^2+(\text{y}-\text{y}{}_{\text{n}}){}^2=\text{d}{}_{\text{n}}^2\hfill \end{array}$;

采用最大似然估计法(Maximum Likelihood Estimation,MLE)求解方程组,由上面方程中上式依次减去最后一项式可得:

$\{\begin{array}{c}\text{x}{}_1^2-\text{x}{}_{\text{n}}^2-2(\text{x}{}_1-\text{x}{}_{\text{n}})\text{x}+\text{y}{}_1^2-\text{y}{}_{\text{n}}^2-2(\text{y}{}_1-\text{y}{}_{\text{n}})\text{y}=\text{d}{}_1^2-\text{d}{}_{\text{n}}^2\hfill \\ \text{x}{}_2^2-\text{x}{}_{\text{n}}^2-2(\text{x}{}_2-\text{x}{}_{\text{n}})\text{x}+\text{y}{}_2^2-\text{y}{}_{\text{n}}^2-2(\text{y}{}_2-\text{y}{}_{\text{n}})\text{y}=\text{d}{}_2^2-\text{d}{}_{\text{n}}^2\hfill \\ ⋮\hfill \\ \text{x}{}_{\text{n}-1}^2-\text{x}{}_{\text{n}}^2-2(\text{x}{}_{\text{n}-1}-\text{x}{}_{\text{n}})\text{x}+\text{y}{}_{\text{n}-1}^2-\text{y}{}_{\text{n}}^2-2(\text{y}{}_{\text{n}-1}-\text{y}{}_{\text{n}})\text{y}=\text{d}{}_{\text{n}-1}^2-\text{d}{}_{\text{n}}^2\hfill \end{array}$。

令

A=$\left[\begin{array}{cc}2(\text{x}{}_1-\text{x}{}_{\text{n}})& 2(\text{y}{}_1-\text{y}{}_{\text{n}})\\ 2(\text{x}{}_2-\text{x}{}_{\text{n}})& 2(\text{y}{}_2-\text{y}{}_{\text{n}})\\ ⋮& ⋮\\ 2(\text{x}{}_{\text{n}-1}-\text{x}{}_{\text{n}})& 2(\text{y}{}_{\text{n}-1}-\text{y}{}_{\text{n}})\end{array}\right]$,

B$=\left[\begin{array}{c}\text{x}{}_1^2-\text{x}{}_{\text{n}}^2+\text{y}{}_1^2-\text{y}{}_{\text{n}}^2+\text{d}{}_{\text{n}}^2-\text{d}{}_1^2\hfill \\ \text{x}{}_2^2-\text{x}{}_{\text{n}}^2+\text{y}{}_2^2-\text{y}{}_{\text{n}}^2+\text{d}{}_{\text{n}}^2-\text{d}{}_2^2\hfill \\ ⋮\hfill \\ \text{x}{}_{\text{n}-1}^2-\text{x}{}_{\text{n}}^2+\text{y}{}_{\text{n}-1}^2-\text{y}{}_{\text{n}}^2+\text{d}{}_{\text{n}}^2-\text{d}{}_{\text{n}-1}^2\hfill \end{array}\right]$, X$=\left[\begin{array}{c}\text{x}\hfill \\ \text{y}\hfill \end{array}\right]$。

则利用最小均方差估计可以得到M坐标为:

X=(ATA)-1ATB。

此算法可以很大程度上克服由于测距误差带来的定位误差,定位精度会得到显著提高。

2 仿真分析

2.1 移动Mesh通信网络架构与仿真

根据需要,假定实际应用中要求在某个指定区域,比如3 km×2 km范围中,实际中,必须考虑设备体积与重量,因此,假设设计Mesh基站覆盖半径一定,那么通过计算机仿真,当Mesh节点随机布置到该区域中,取基站覆盖半径分别为1 km,2 km,则基站数量和平均覆盖率(可通信率)关系如图3所示。

仿真结果表明,当移动Mesh节点无线覆盖半径为2 km,随机接入的基站数目达到3个以上时,系统的可接通率达到99%(即系统可信度达到99%),可满足区域内一般通信网络需求。

2.2 移动Mesh网络定位架构与仿真分析

首先假设Mesh节点自身位置信息已经确定,作为“锚”节点,Mesh节点向终端发送定位信息。可以想象,由于本系统是一个随机拓扑结构的无线网络,Mesh节点的布局将直接影响终端能否实现定位功能。如果系统中移动终端同时必须接收到3个以上Mesh“锚”节点定位信号,就可以认为终端可以实现自身定位。假如在一种情况下,Mesh“锚”节点随机布置到3 km×2 km的区域范围中,节点覆盖半径为2 km,利用计算机进行仿真,则实现定位目的的节点数量与可实现定位的概率之间的关系如图4所示。

仿真结果表明,在当前确定网络架构内,当取基站节点数目为6个以上时,此网络基本具备定位能力。

2.3 测距仿真分析

利用OFDM系统定时计算单个Mesh节点与移动节点之间的距离。定时估计采用EC算法,在高斯信道下进行仿真,仿真中采用子载波数取2 048,循环前缀取64,QPSK调制,符号取224 μs,单个样值点0.109 4 μs,SNR取0~20 dB,对于每个SNR分别仿真1 000次求其平均值。信道采用四径多径衰落信道,时延分别设为0,10,20,40,信号衰减分别为0,10,20,25 dB。得到θ与信噪比(SNR)及测距误差关系如图5和图6所示。

2.4 定位算法仿真及误差分析

该文采用最大似然估计算法,主要对定位精度进行了仿真验证,其初始参数包括随机Mesh节点(“锚”节点)位置、随机移动终端位置,设测距误差分布服从N~(μ,σ)的正态分布,其中μ等于0,σ值由测距仿真计算得到。仿真结果如图7和图8所示。

综合考虑网络规划、测距误差以及信道状况等,这里所描述的Mesh定位系统定位误差主要包含2部分,第1个是测距误差,实际仿真结果表明在信噪比比较大,即信道质量较好的情形下,误差范围在米级,对系统定位影响不大;第2个是定位算法带来的计算误差,这里选择的最大似然估计算法,当“锚”节点数量足够多时,定位精度将显著提高,误差精度能够达到米级。

3 结束语

研究了Mesh节点在一定区域内随机布局,Mesh节点位置(坐标)已知情形下该区域中随机移动终端的定位问题。分析了基于OFDM技术下的移动Mesh通信网络中各单元的相对定位问题。对Mesh系统实现定位的关键技术及算法进行了阐述及仿真验证,并综合考虑了随机Mesh网络建立、测距算法及实现和定位算法及实现,分析了基于OFDM模式下Mesh网络实现自定位的可能性与误差分析。

通过仿真验证结论,找到了一种实现移动Mesh网络自定位的方法,其定位精度与定位能力满足一般地面通信系统定位使用的要求。

参考文献

[1]赛迪顾问通信产业研究中心.2009-2010年中国位置服务(GPS/LBS)市场竞争分析[R].北京:赛迪集团,2010:1.

[2]宋文,方旭明.无线网状网研究与发展[J].铁道学报,2007,29(2):96-103.

[3]刘瑾.基于测距的无线传感器网络的定位算法的研究[J].航空计算技术,2009(6):124-126.

[4]杨国庆.基于OFDM信号的无源定位技术研究[D].西南交通大学硕士论文,2008.

[5]WU Hao-yun,LU I-tai.A simple and Accurate LinearSolver for Hyperbolic Localization[C]∥IEEECommunications Socie-ty/WCNC 2005:1733-1736.

无线Mesh网络的路由协议探析 第3篇

无线Mesh网络中, 每个节点既是主机, 也是路由器。当发送信息节点 (源节点) 与接收信息节点 (目的节点) 不能直接通信时, 就需要其他一些中间节点通过存储转发帮助其完成通信, 这样也就构成了多跳网。从源节点依次经过多个中继节点到达目的节点就形成了一条通信“路径” (路由) 。如何寻找一条合适的路由就是路由发现问题 (也称路由计算;) 当网络拓扑发生变化时, 如何自适应地调整路由就是路由维护问题。路由计算和路由维护的方法合起来就是路由协议。然而, 如果直接将传统路由协议应用于无线Mesh网络, 就会因为周期性地广播拓扑信息过大, 占用大量的无线信道资源, 降低系统效率, 甚至在某些情况还会造成无穷计数和临时环路等问题。所以在无线Mesh网络中已经不再适合传统的路由协议。因此, 路由协议成为当前无线Mesh网络研究的一个重点问题。

1 无线Mesh网络中的路由协议

针对无线Mesh网络的结构特点, 要求路由协议必须采用分布式操作, 能尽量支持单向链路, 同时应避免路由环路现象。考虑到无线节点的特性, 路由协议还应尽量简单, 能够支持节点的“休眠”操作以节省电源, 能够提供安全性防护等机制。目前这样的路由协议主要有两大类:表驱动路由协议和按需路由协议。

1.1 表驱动路由协议

表驱动路由协议又被称为先验式路由协议, 它是一种基于路由表的路由协议。在表驱动路由协议中, 每个节点必须维护一个或多个路由表来记录路由信息。节点间通过周期性的交换路由信息来不断更新自身的路由表, 以便能够及时地反映网络拓扑结构的变化。表驱动路由协议的最大优点是, 当节点有路由请求时, 不需要发起路由发现机制, 可以立即得到到达目的节点的路由。这样即使在网络负载较大情况下, 数据源与目的地的端到端的时延会较小。路由协议开销虽然较大但较稳定。但是由于每个节点需要实时地维护路由信息, 这样在网络规模较大、拓扑变化较快的环境中, 大量的拓扑更新信息会占用过多的信道资源, 使得系统效率下降。

下面对DSDV、WRP两种典型的表驱动式路由协议进行介绍和分析。这些协议的主要区别在于, 每个节点维护了不同数量的表, 并且当网络拓扑变化时更新信息在网络中具有不同的传输方式。

1.1.1 DSDV (Destination-Sequenced Distance-Vector基于目的序号距离矢量协议) 路由协议

DSDV协议是先验式路由协议, 是由传统的Bellman-Ford路由协议改进得到的, 其最大优点是解决了BF算法的路由环路和无穷计数问题。在DSDV中, 每个节点保存一张路由表, 路由表维护本节点到网络内部所有可达的目的节点的路由。路由条目中保存目的节点的序列号 (Sequence Number) , 用以区别新旧路由。为维护路由表, 节点周期性地广播路由更新分组。收到路由更新分组后, 节点比较其中的目的节点序列号和自己保存的同一目的节点的序列号, 如果前者大, 就更新自己的路由。如果路由序列号相同, 则选择具有较少跳数的路由。路由更新分组要延迟一段时间发送, 以防止路由表的波动。

1.1.2 WRP (Wireless Routing Protocol无线路由协议) 路由协议

WRP协议是个基于路由表的路由协议, 目的是在所有网络节点中维护路由信息。在WRP中, 节点保存的信息表包括距离表、路由表、链路开销表、分组重传列表4个部分。节点的距离表中包含了每一个目标节点通过该节点到每个相邻节点的距离, 同时也包含了下游节点的信息。节点的路由表包含了每个目标节点到该节点的距离值, 该节点的前驱节点和后继节点, 还包含了一个标记。在表中存储前驱节点和后继节点非常有利于检测环和避免计数到无穷的问题。链路开销表则主要包含到该节点的每个相邻节点的链路成本。分组重传列表MRL中的每一个记录包含了更新信息的序列号、一个重传计数标志、是否响应的标志量, 以及更新报文中的更新信息。这些信息主要是用于让节点知道它的哪个相邻节点还没有确认它的更新消息, 并重传更新消息到该相邻节点。

1.2 按需路由协议

按需路由协议是根据发送数据分组的需要按需进行路由发现过程, 网络拓扑结构和路由表内容也是按需建立的, 所以其内容可能仅仅是整个网络拓扑结构信息的一部分。按需路由协议能够快速适应网络拓扑的变化, 但是在网络负载很重的情况下, 其性能较差。下面介绍两种典型的按需路由协议。

1.2.1 DSR (Dynamic Source Routing动态源路由) 路由协议

DSR是一种基于源路由的按需驱动路由协议。在DSR路由协议中, 当发送者发送报文时, 在数据报文头部携带到达目的节点的路由信息, 该路由信息由网络中的若干节点地址组成, 源节点的数据报文就通过这些节点的中继转发到达目的节点。DSR协议的优点是:节点仅需要维护与之通信的节点的路由, 协议开销较小, 而同时DSR使用路由缓存技术减少了再次路由发现的开销。此外, 一次路由发现过程可能会产生多条到目的点的路由, 这也将有助于DSR的路由选择。DSR的缺点在于, 由于每个数据包的头部都需要携带路由信息, 如果数据包较小, DSR额外开销就较大;由于缓存路由, 失效路由会影响路由选择的准确性。

1.2.2 AODV (Ad-hoc On-Demand Distance vector) 路由协议

AODV路由协议是一种对等的、基于目的的按需路由协议。它是DSR和DSDV的组合, 它借用了DSR的路由发现和路由维护机制, 利用了DSDV的按跳 (hop by hop) 路由、目的序列号技术和周期更新 (只在路由维护阶段) 机制。因而它的处理过程和存储开销都较小, 能对链路状态的变化做出快速反应。AODV的特点是使用目的序列号 (Destination Sequence Numbers) 和经典的距离矢量协议 (Distance Vector Protocols) 。AODV通过引入序列号的方法解决了传统DV协议中的如“计算到无穷”等问题, 确保了在任何时候都不会形成路由环。

2 两种路由协议的比较

表驱动路由协议和按需方式路由协议的路由延迟、控制开销、耗电量和带宽开销的比较如表1-1所示。

这4种路由协议的特点比较如表1-2所示。

3 结束语

本文简要介绍了无线Mesh网络中路由协议的两大类。列举了其中4种路由协议, 并对其进行比较, 希望对初次接触无线Mesh网络路由协议的读者提供一些参考。

摘要：无线Mesh网络是一种通过无线链路连接路由器和终端设备的无线多跳网络, 是一种新型宽带无线接入技术, 具有可靠性、自组织性和自愈性的特点。而且建网方便快捷, 成本低, 具有传统有线、无线网络系统无可比拟的优势和广阔的应用前景, 能为无线个域网、局域网、校园网甚至城域网提供无线宽带接入服务。无线Mesh网络中的每个节点都具有路由转发功能, 再加上网络中节点的频繁移动, 使得路由技术成了无线Mesh网络中的关键技术。

关键词：无线Mesh网络,路由协议,DSDV,DSR

参考文献

[1]王晓燕.无线Mesh网络路由协议的研究[D].西安:西安电子科技大学, 2005.

[2]谢世欢, 郭伟.实现Ad hoc按需路由协议的关键技术[J].计算机应用, 2006 (3) .

[3]杜欣军, 王莹.一种安全的Ad Hoc On demand路由协议[J].电路与系统学报, 2006 (2) .

[4]杨志成, 王军.移动Ad hoc网络组播路由协议的研究综述[J].现代电子技术, 2006 (1) .

Mesh网络中的关键技术研究 第4篇

20世纪90年代, 宽带无线接入技术快速发展, 其中Mesh网络是其主要技术之一。Mesh网络由一个中心节点控制, Mesh基站作为Mesh到外网的接口。Mesh子网分别有Mesh基站连接, 基站连接到回程点, 通过该回程接入点连接到因特网。无线Mesh网络的多跳连接将成为网络发展的必然趋势, 可以为用户提供无处不在的连接。

二、Mesh网络的关键技术

(一) OFDM技术。

OFDM传输技术是多载波传输技术的一种, OFDM的思想是把一个高速率的数据流分解成很多低速率的子数据流, 每个码流都用一条相互正交的子载波发送, 以并行的方式在多个子信道上传输。OFDM采用跳频方式选用那些即便频谱混叠也能够保持正交的波形, 因此OFDM既可以当作调制技术, 也可以当作复用技术。OFDM能够实现各个载波的正交, 允许各载波间频率互相混叠。与过去的FDMA有了很大的不同:不再是通过很多带通滤波器来实现, 而是直接在基带处理, 这也是OFDM有别于其他系统的优点之一。OFDM每个频带的调制方法可以不同, 这增加了系统的灵活性, 大多数通信系统都能提供两种以上的业务来支持多个用户, OFDM适用于多用户的高灵活度、高利用率的通信系统, 增强抗频率选择性衰落和抗窄带干扰的能力, 大大提高频谱利用率。

(二) 自适应调制编码技术。

自适应调制与编码 (AMC) 属于链路自适应的范畴。在接收端估计信道状态, 并通过反馈信道传回发射端, 针对当前的信道状态, 设计合适的发射功率、调制模式、编码形式等从而使系统的整体传输性能达到最优, 满足高效可靠传输的目的。在AMC系统中, 一般用户在理想信道条件下用较高阶的调制方式和较高的编码速率, 而在不太理想的信道条件下则用较低阶的调制编码方式。自适应编码调制技术根据信道的变化动态调整各项传输参数, 对于提高频谱利用效率具有很强的技术优势, 已被很多无线通信系统所应用, 随着技术的进一步完善以及应用范围的进一步拓宽, 从时域扩展到频域和空域, 从一维扩展到多维, 自适应编码调制技术必将在未来的无线通信系统中得到更加复杂灵活的运用, 并在通信技术领域发挥越来越重要的作用。

(三) 功率控制技术。

功率控制技术是无线资源管理的一项重要内容, 其目标是使系统所能同时容纳的用户量最大, 每个移动单元的发射功率最优, 则基站接收到的信干比达到可允许的最低水平, 系统的容量将会达到最大。因此需要建立一个高度复杂、动态的方案来控制接收到的功率, 从而最大化信道容量。在一个蜂窝系统中, 某个移动台可能很接近基站, 而另一个却较远, 从而产生“远近效应”导致系统容量下降。针对这种情况, 需要控制移动台的发射功率, 使得接收信号强度都处在统一水平。在保证用户信噪比的前提下尽可能地以最低功率传输, 可减少不必要的干扰, 最大化系统容量。这就是功率控制技术。

(四) 智能天线技术。

智能天线的原理是将无线电的信号导向具体的方向, 产生空间定向波束, 使天线主波束对准用户信号到达方向DOA, 旁瓣或零陷对准干扰信号到达方向, 达到充分高效利用移动用户信号并删除或抑制干扰信号的目的。同时, 智能天线技术利用各个移动用户间信号空间特征的差异, 通过阵列天线技术在同一信道上接收和发射多个移动用户信号而不发生相互干扰, 使无线电频谱的利用和信号的传输更为有效。并同时增加移动通信系统容量、提高移动通信系统频谱利用率、降低信号发射功率、提高通信的覆盖范围。和传统的没有智能天线的基站比较, 它在硬件上由一个天线阵和一组收发信机组成了其射频部分, 通过一组带有可编程电子相位关系的固定天线单元获取方向性, 并可以同时获取基站和移动台之间各个链路的方向特性;而在基带信号处理部分的硬件则基本相同。必须说明的是, 这一组无线收发信机将使用同一个本振源, 以保证此组收发信机是相干工作的。

(五) ARQ机制。

自动重发请求法 (ARQ法) 是一种实用的差错控制方法, 实施差错控制是使发送方将要发送的数据帧附加一定的冗余检错码一并发送, 接收方则根据检错码对数据帧进行差错检测, 若发现错误, 就返回请求重发的应答, 发送方便重新传送该数据帧。TCP的特点之一是对信道的传输质量有较高要求。这和无线信道不稳定的特点是相悖的, 因此IEEE802.16必须适应TCP/IP协议对信道传输质量的要求。SS和BS在连接开始建立时可以协商让该连接实现ARQ功能。因此, 802.16中的ARQ是基于连接的。在链路层加入了ARQ机制, 减少到达网络层的信息差错, 可大大提高系统的业务吞吐量, 在IEEE802.16中, 使用发送、接收有限状态机来维护一个ARQ过程。

三、结束语

无线Mesh网络是一种高速率、高容量的多点对多点网络, 可用无线的方式构建宽带家用网、宽带社区网、宽带企业网及临时组建的网络, 也可构建一个城域规模的宽带无线网。由于无线Mesh网络全面继承了Ad Hoc网络的多跳自组织、自配置及有基础设施的WLAN的优势, 能够快速方便低成本的部署网络, 因此无线Mesh网络必将对未来无线通信网络产生重要影响。

参考文献

[1]刘占军, 侯维娜.无线网状网的网络容量研究[J].科技资讯, 200 (85) ;

[2]张少蔚, 杨星海, 高振明.OFDM基本原理及其在移动通信中的应用[J].山东通信技术, 2003, 23 (2) ;

[3]苗强, 毛玉泉, 黄凯.第三代移动通信的关键技术-智能天线[J].电子科技, 2005, 1;

新型无线Mesh网络安全性研究 第5篇

无线Mesh网(Wireless Mesh Network,WMN)是一种多跳、具有自组织和自愈特点的宽带无线网络结构,即一种高容量、高速率的分布式网络。目前主要观点认为,WMN是一种由无线链路连接路由器和终端设备的静态无线网络,是Internet的无线版本。WMN不同于传统的无线网络,可以看成是WLAN(单跳)和移动Ad Hoc网络(多跳)的融合且发挥了两者的优势。作为一种新型网络结构形态,Mesh结构已被纳入到802.16-2004,802.16e和即将制定的802.1ls标准中。WMN可以通过一些中间节点连接互相远离不能直接连接的无线路由器。

在传统的各种无线接入网络中,拓扑结构主要采用点到点或点到多点的结构形式。一般都有一个中心节点与骨干网直接相连,中心节点负责控制各用户节点的接入和提供到骨干网的网络接口,功能上远比用户节点复杂,成本也比较高昂。无线Mesh网采用的则是一种网状结构,也被称为多点到多点的系统。各用户节点可以通过相邻的其他用户节点以多跳方式实现到骨干网的连接,新用户可以通过他周围的其他用户节点很方便地接入到网络中,由于在网络扩展时不再需要中心节点,无线Mesh网可以极大地减少整个网络的建设成本。

自愈性:WMN可以提供完全的端到端的多重冗余路由,这就意味着如果由于某种原因某个链路失效,网络能自动地更换路由。

可靠性:为了提高链路质量,可通过增加中间节点,即缩短节点之间的距离来实现。

自配置能力:WMN是一种自组织网络,不需要或很少需要人工配置网络。网络能够自动判断并更新网络相关配置。

分散管理问题:由于WMN的分散性,很难实现有线网络那样的集中管理,即使对于低移动性的WMN,网络配置与管理仍然是一个不易解决的问题。

共存干扰问题:对于非许可证频段的WMN必然存在与其他共存网络的无线干扰问题。

安全问题:由于WMN结构本身的脆弱性,极易遭受其他恶意节点的攻击、干扰和窃听,所以安全问题是WMN需要解决的重要问题之一。

2 WMN的安全问题

WMN从技术演化的角度而言,是WLAN技术和Ad Hoc网络技术的结合。基于基础设施的WMN,在STA和MAP之间是WLAN连接,在MP、MAP、MPP之间是一个Ad Hoc网络,因此WLAN和Ad Hoc的安全性都需要考虑。WMN主要存在以下安全问题:

2.1 可用性

有以下几个因素可能导致网络不可用。

1)信号阻塞:恶意节点长时间占用无线链路信道使得正常节点无法发送数据,导致节点不可用。

2)Dos攻击:通过恶意节点或被其控制的节点向正常节点不断发送无用信息,导致节点无法发送正常数据。

3)资源耗尽:节点都有CPU、电源、宽带等限制,攻击者可通过多种方式使节点资源快速耗尽而停止工作。

2.2 节点的保护,防假冒或防俘获

根据Ad Hoc的属性WMN中的设备是变化和调整的,如果有一个假冒节点进入WMN,并成为信息传输中的一个节点,就会导致信息泄密;若假冒节点恶意广播非法路由,将导致网络拥塞或不可用。WMN中的MP设备往往部署在室外路灯上、室内走廊等环境,攻击者非常容易接近设备,获得节点的内部信息,如对称密钥、认证信息等,从而假冒节点,或者更改信息(如邻居节点信息),导致路由信息变更。

2.3 信息的完整性

从源节点到目的节点,信息流经多条无线链路和多个WMN节点,每条无线链路都可能被破坏使信息被截断甚至篡改,导致发送的信息和接受的信息不一致。

2.4 信息的机密性

采用无线链路传输信息,攻击者通过监听就能获得无线链路的数据。这种弱点WMN比WLAN更严重,因为不仅从STA到AP,同时MP之间的链路同样可能被监听。

2.5 路由安全

在WMN中每个节点通常需要多跳才能到达目的网络,因此如果有假冒节点广播恶意路由,将导致网络不可用。由于Mesh无线路由都采用无线链路,节电本身可能是移动的,因此路由是动态调整的(动态路由增加了对一些安全事件的检测难度,如蠕虫攻击),攻击者伪装成合法的节点,发布错误的路由信息,大量占用网络资源,使网络阻塞等,所以必须设计安全的路由协议以对抗针对路由协议的攻击。

2.6 STA认证

上述诸多因素的存在,导致STA被攻击或假冒的可能性大大增加,如认证信息由于信息的机密性无法在多跳之间保证,大大增加了泄密的可能。

2.7 管理信息的安全

作为网关的无线路由器从与它相关联的节点收集管理信息并发送到管理服务器,并使用AES加密这些流量,必须保证这些信息的安全性。

因此,必须针对WMN中特有的安全问题制定相应的策略和解决办法方案。

3 WMN安全解决方案

WLAN主要采用的安全技术有访问控制、认证、加密、数据完整性及不可否认性等,目前主要有WEP(wired equivalent privacy)、WPA(Wi-Fi protected access)和802.11i等协议标准。

访问控制主要利用ESSID、MAC限制,防止非法设备入侵;数据加密采用WEP。WEP是IEEE 802.11b协议中最基本的无安全加密措施,主要提供接入控制,防止未授权用户访问网络。WEP加密算法对数据进行加密,防止数据被攻击者窃听、篡改或伪造。由于ESSID、MAC限制,WEP密钥必须通过人工手动设置。这些基本的无线安全措施特别适合小型企业、家庭用户等场合,无需额外的设备支出,配置方便,且安全防护性好,从终端的访问控制到数据链路中的数据加密都定义了有效的解决方案。但对于银行、证券等大型网络,其现有的网络结构比较复杂且对网络的安全性要求很高,仅使用基本的安全措施并不能完全达到其安全需求。为了进一步加强无线网络的安全性,IEEE 802.11工作组目前正在制定IEEE 802.11i,其标准草案中主要包含TKIP(temporal key integrity protocol)和AES(advanced encryption standard)加密技术以及IEEE 802.1x认证协议。在IEEE 802.11i标准最终确定前,WPA技术将成为代替WEP的无线安全标准协议,为IEEE 802.11无线局域网提供更强大的安全性能。

根据无线连接特性,可将WMN分成两大部分:一是STA到MAP的单跳无线网络连接,二是MAP、MP、MPP等组成的Mesh网络。对于第一部分,可以假设MAP与MP等建立的Mesh网络是安全的,因此这一部分的安全需求等同于WLAN的安全需求,可以采用目前成熟的安全措施,如WAP、802.11i或WEP。考虑到WEP存在一些安全缺陷,如使用重复密码流和共享密钥等,因此在WMN中不建议采用,可采用IEEE802.1X和TKIP替代。目前WMN主要有以下安全解决措施:

3.1 节点身份认证

WMN中节点分为多种角色。其中STA和MAP间的认证与WLAN类似,而MP认证有所不同,每个MP在加入Mesh网络时,都应该向相邻节点进行认证,此时新节点作为申请者,其相邻节点作为认证者。认证可以采取分布式和集中式两种模式。分布式主要可以采用数字证书(CA)或共享密钥模式(PSK),但需要注意,PSK模式无法提供源身份识别。集中式采用AAA服务器。在认证通过后,方能参与后面的密钥协商、密钥交换、路由更新等。802.11s主要推荐使用802.1x。

3.2 路由加密和完整性

为防止路由信息被窃取和篡改,可采用路由信息加密和数字签名来确保安全。在交换路由信息前,节点必须通过认证并协商密钥,但这种模式无法防止被捕获的节点产生错误路由。为防止这种问题,可以采取定期更新路由表以及选举等方式,选出正确路由(因为被捕获这数量应该是比较少的),从而绕开捕获者,确保路由正确。目前有SEAD、CSER、SRP、SAAR、BSAR、SBRP等。

3.3 密钥管理

无论是节点认证还是路由信息的保护,都需要用到密钥,因此WMN需要建立密钥体系,避免每次都重新认证和协商。802.1s的密钥体系可以分为Link Security和Key Distribution两个部分,Link Security用于MKD(mesh key distribute)、MA(mesh key)和Supplicant MP间的密钥生成和分发,Key Distribution用于保障MA和MKD间的安全通信以及PMK-MA密钥的安全分发。

3.4 入侵检测

WMN入侵检测有以下几种模式:

1)独立的入侵检测系统:每个节点自己运行检测程序,并独立对事件进行反应。

2)分布合作式入侵检测:部分节点运行入侵检测程序,通过相互协作实现入侵检测,并对事件进行反应。

3)层次式入侵检测:有一个主控节点对于子节点进行控制,有主控节点负责分析和反应。

3.5 信息的加密和完整性

根据Mesh网络的特点,IEEE专门提出了一个称为Mesh安全关联(MSA)的安全方案。与802.11i方案相比,MSA使用新的密钥体系,建立密钥体系的结构如下。

通过细化MP角色,建立分支和层间隔离强化安全醒。加入新的角色MKD行使代理AS的部分功能,MP与MA和MKD与MA不同的分支间通信使用不用的密钥。

简化认证过程。MP只见关联后不需要每次都进行802.1x验证,即通过一次初始认证后的MP间可以直接关联并进行密钥交换,不需要与MKD或SA进行交互。

MSA节点认证机制实现了MP加入一个Mesh网络时必要的身份认证和相关密钥生成,一个完整的MSA认证过程大致可以分为3个阶段:由一双双向的Peer Link Open/Confirm消息构成的关联阶段;可选的MSA初始认证阶段;MSA 4次握手阶段。

WMN属于对等网络,但是在MSA认证阶段需要组成临时的C/S结构,由Selector MP担任密钥集的确定者,其中角色的确定一般通过对双方MAC地址进行比较得出。在关联阶段,各MP分别像对方发送包含Peer Link Open消息的关联请求帧,Peer Link Open消息通过包含其中的各种IE(information element,信息元素)向对方通告各种后续协商所需的安全参数,这些IE例如通告支持对/组密钥/AKM集和本地储存密钥的RSNIE,通告MSA安全角色信息的MSCIE和通告MSA能力,初始认证参数和选定对/组密钥AKM集的MSAIE等。

在收到Peer Link Open消息后双方比较各自支持的密钥并选择一个用于后续操作。如果从Peer Link Open消息中发现本地储存密钥的存在那么说明密钥体系已经建立,由于有可能通信双方在本地都保存了对双方的PMK-MA,因此需要进行一个密钥选择操作协商选定一个密钥。如果密钥选择操作失败,那么说明必须进行初始MSA认证重新建立密钥体系,这时双方将进行802.1x角色协商,为后续的EAP认证做准备。Peer Link Open消息处理无误后MP将向对方发送Peer Link Open消息确认选定的各种密集、是否进行初始MSA认证及角色协商结果。Peer Link Open主要用于消息同步和和信息一致性,其中不含有新的信息。对Peer Link Confirm消息进行验证并通过后,MP根据配置的策略进行初始MSA认证或加载密钥MSA 4次握手。

如果需要进行MSA初始验证,通行双方开始一个802.1x/EAP认证过程。认证成功后,Supplicant MP和MKD分别计算;MKD为MA生成A Nonce和PMK-MA并使用Mesh Key Transport协议将它们分发个MA;最后MKD将为每个MKD-Supplicant MP对建立一个PMK-MKD SA,并为每个PMK-MA建立一个PMK-MA SA。

如果密钥体系已经建立,即双方已经存在一个共享的PMK-MA并且通过前面的密钥选择操作顺序选定使用的PMK-MA,那么就不需要在进行802.1x/EAP认证了。通信双方使用共享的PMK-MA直接进行MSA 4次握手。在4次握手结束后双方就完成了相互认证,建立并加载了密钥体系。

4 结束语

WMN是下一代无线网络中非常有生命力的技术,但是安全问题限制了其进一步推广,安全问题的解决将会加速其发展。一些新的技术也在研究以解决这些问题。

摘要：随着无线通信和移动计算技术的发展以及越来越高的宽带接入要求,WMN技术受到广泛的关注。然而WMN在设计之初,考虑的主要目标是快速便捷的组网和网络的可扩展性,安全性没有作为重点,各种篡改、假冒用户及窃听等恶意行为将对无线Mesh网的应用造成巨大威胁。如何提高WMN的安全性,成为亟待研究的问题。

关键词：WMN,无线网络,MSA

参考文献

[1]张勇,郭达.无线网状网原理与技术[M].北京:电子工业出版社,2007.

三维Mesh网络 第6篇

关键词：MESH,无线网络,报警响应

我们研究的无线Mesh网络设计成没有中心节点, 系统主要由Mesh路由器和Mesh客户端组成。整个系统是以自组织形式建立与维持通信链路, 节点与节点间通过多跳的方式进行通信。我们把它应用在监测中时候, 可燃性气体的浓度会被它所“感知”[1]。在我们设计的系统中, 可将浓度信息发送给上位控制主机并由主机进行浓度分析, 根据经验数据库的对比, 做出报警处理决策。

同时, 系统自动将该信息和报警处理决策上传到管理中心的后台数据处理服务器。当小区管理处值班人员就可以根据显示的数据进行整体综合的情况分析, 而且可以通过系统查看具体的浓度信息和报警信息。我们在小区的后台报警系统中定义了报警级别, 如果发现高危险报警信息时, 系统立即可自动上传至消防报警中心, 119报警服务台即可对当前的报警信息进行人工确认, 与小区值班人员沟通, 若事态紧急或严重, 就可调度消防车赶往事发现场, 从技术上做到事前监控, 事后及时处理, 为人民的生命和财产安全做到根本的保障。

1 MESH网络特点

1) 自组织:在MESH网络中, 它的节点和授权最终用户可根据自组织形式加入网络, 这样的话可以随时扩展网络覆盖范围, 并可与其他节点进行通信与定位[2]。

2) 自愈:无线MESH网络中如果出现设备故障或其拓扑位置上改变, 网络能自动适应这种改变就叫做自愈。在网络中进行信息传输时, 即使存在多台中继设备, 网络也可自动找到新的链路进行传输。

3) 多跳式:网络中信息传输需要经过多个节点和用户端设备时, 当转发数据包时还能选择并确定一个从发端到收端的最佳路由策略。

4) 高带宽:我们在设计无线Mesh时, 采用的是802.11a/b/g/n标准。如果组成异构网络, 就可以兼容WIFI在802.11N的标准和模式并可以获得高速率和高带宽支持。

5) 移动性:我们设计的Mesh保留了并且继承了AD hoc网络的高移动性, 可以使系统能获得很高的稳定性[3,4,5,6]。

2 燃气报警关键技术组成

我们在设计煤气报警系统时候, 主要使用到的关键技术包括:传感器采集技术、无线MESH技术、后台管理控制技术, 并把几种技术进行结合和集成总体设计了燃气报警系统如图1燃气报警关键技术流程:

1) 传感器采集技术:通过前端传感器采集设备, 我们可以采集到具体的监控数据, 然后将采集到的数据上传至控制机, 通过控制机对上传的信息进行分析, 然后做出报警等级处理。

2) 无线MESH技术:组网技术采用无线MESH技术, 它可以将最前端的传感报警主机信息通过mesh网络技术及已有的局域网技术、设备, 把信息发送到调度指挥中心的后台管理设备或系统上。

3) 后台管理控制技术:报警主机可以控制数据采集前端节点进行数据收集, 并根据专家数据库进行有针对性的数据分析, 做出声、光报警。同时, 将传感器采集的浓度信息和报警信息传到后台管理系统, 该系统集成了信号采集、数据分析、报警输出和音、视频的显示技术。

3 燃气报警系统核心设计

1) 燃气报警系统流程

报警系统的信息采集是通过前端的探头, 可以采集到多种有用信息, 如可燃性气体的浓度值、温度等。当我们将采集到的数据上传至上位机时, 上位机就根据接收到的气体浓度信息进行数据分析、比较。当发现危险状态, 比如探头上传的浓度过高时, 则进行报警信号输出;若浓度值在安全范围内, 则继续监听探头上传的数据信息。

此时, 上位控制机将采集到的信息和报警处理信息上传至上一级管理系统。通过后台管理系统进行整体控制, 以便形成集中性控制管理和调度指挥, 具体系统报警流程如图2所示:

2) 燃气报警系统机制

首先, 在设计的报警机制中采集设备使用的是多种传感器, 直接安装在用户和关键节点上, 用它监测其危险成分。如果发现可燃性气体浓度有变化, 如图3报警系统机制图所示, A栋住户3发现危险信息, 就会立刻将该信息发送给单元内的上位控制主机, 然后马上与经验数据库进行对比分析, 并做出报警处理决策。同时, 系统需要将报警信息和处理决策通过综合局域网上传到小区物业管理处本地管理后台服务器上, 该后台系统就会根据上传的数据进行整体综合的监控分析, 并可以在设计系统平台上查看当前管道探头的浓度信息与报警信息。此时, 小区监管员看到报警消息, 就可以根据系统提示进行调度安排。

在后台系统设计时候, 需要加入自定义报警级别设计, 在设计报警级别时候, 可以将有高危险报警信息时直接自动联动上传至消防报警中心后台。当119报警服务台收到信息, 对当前服务器发出的报警信息进行人工确认, 若事态紧急或严重, 就可以及时出动消防车, 从技术上做到事前监控, 事后及时处理。整体系统报警机制如图3所示:

4 结束语

本报警机制的基础是部署的无线网络, 在室外环境中部署网络时, MESH无线架构允许无线网络绕过大的物体, 但是需要注意信号的衰减, 在部署时候需要考虑无线网路的健壮性。由于是通过中继节点进行数据包的转发, 而不是直接穿过障碍物, 所以在有很多障碍物的城市环境或者有丘陵、山区等传统无线网络覆盖有困难的区域, 有较大的应用空间。

建立在复杂城市环境下基于MESH网络的燃气报警平台具有很强的现实意义, 但是该系统还存在部分问题, 比如在部署节点时候, 如何加强网络的健壮性及节点的安全性需要在后续研究中加以改进。

参考文献

[1]李云洁.新兴低速近距离无线通信技术简介[J].移动通信, 2008, (6) :10-11.

[2]彭瑜.低功耗、低成本、高可靠性、低复杂度的无线电通信协议ZigBee[J].自动化仪表, 2005, (5) :1-4.

[3]王瑞荣, 陈碧.低功耗自组织无线传感器网络[J].计算机测量与控制.2005, (9) :881-883.

[4]于锐华, 益晓新, 于全.ZigBee与Bluetooth的比较及共存分析[J].测控技术, 2005, 24 (6) :50-56.

[5]金纯, 罗甜秋, 罗凤, 等.ZigBee技术基础及案例分析[M].北京:国防工业出版社, 2008:11-12.

无线mesh网络多径路由算法研究 第7篇

无线mesh网络是一种新型的宽带无线接入系统, 是由无线链路连接路由器和终端设备的静态多跳无线网络。它可以看做是WLAN和移动Ad hoc网络的融合, 因此, 无线mesh网络结合了Ad hoc和WLAN网络的拓扑特点, 具有可靠性、自组织性和自愈性的特点。随着人们对互联网依赖和移动通信需求的不断提高, 人们希望在任何时间、任何地点都能够与任何人进行快速、高质量的通信, 而且能够连接到互联网随时随地地获取互联网上丰富的资源和服务, 无线mesh网络技术的逐渐成熟加速了宽带无线互联网时代的到来。

由于无线mesh网络是一种具有自组织、自管理的智能型网络, 它不需要主干网就可以构造出动态的、富有弹性的网络结构, 具有前期投入少、覆盖范围广、抗干扰能力强、扩展能力强、网络结构灵活、维护方便、可靠性高和兼容性好等特点。

路由技术向来是任何网络结构中的研究重点与难点, 是保证网络得以部署和运行的关键。目前, 无线mesh网络中主要采用的单路径路由算法。单路径是否最优并不重要, 由于无线mesh网络动态性较强, 若花费太多的代价去寻找最优路径, 那么可能该路径还没有使用就失效了。在单路径环境中, 自适应的路由方式还容易产生振荡现象。因此, 单路径路由算法很难对网络的拥塞进行控制。针对无线mesh网络本身的特性, 国内外不少专家学者开始对多路径技术进行研究, 主要思路是在源节点与目标节点之间建立多条路径进行传输, 来实现网络负载均衡、充分利用网络资源。本文在这个基础上提出一种基于无线mesh网络中自适应流量分配算法。它从无线mesh网络路径的动态信息中得到各路径的权值, 根据权值大小自适应地按比例分配数据流量到各条路径上进行传输。

2 系统模型的建立及权值的计算

图1为一个简单的网络拓扑结构, 从图中可以看到, 从源节点 (s) 到目标节点 (d) 之间存在n条跳数最小的路径, pmin表示跳数最小的路径集, 用palt表示可选路径集。那么所有可用的路径集为p=pminUpalt。这里源节点s和目标节点d之间由n条非交叉的路径1p、p2、…、pn相连。假设对于源节点s来说已知路径pk的带宽容量为ck, 并且设定源节点s的数据流以平均速度λ到达, 服从泊松分布;停留时间为, 服从指数分布。为了方便, 设定每个流消耗1单位的带宽, 也就是说, 路径pk能在任何时间供给ck条流。

于是, 问题转化成研究如何沿着这n条路径传输数据流使得整体的阻塞可能性最小, 吞吐率最大。本文的思路是根据源节点s和目标节点d之间不同路径的权值来调整各路径中的流量分配。即根据路径权值的大小按比例分配数据流量, 从而解决流量分配的均衡问题。

路径可靠性的权值, 这里选择延时参数, 这是由于路径询问消息 (RREQ) 和路径回复 (RREP) 中的路径质量参数都包含了延时参数。对于任意节点, 可以得到2个相对于目标节点的最小延时值, 一个是RREQ消息的延时时间, 另一个是RREP的延时时间, 本文取两者的平均值, 假设从源节点到目标节点第k条路径的传输延时为该路径的长度, 其大小为源节点收到的RREP消息累计延时的一半记为

假设从源节点到目标节点的最短延时为最短长度, 记为lmin (s, d) , 对于链路 (i, j) , 如果lmin (j, d)

于是可以得到有效链路 (i, j) 的权值为

其中, 记为与节点i相连的所有有效路径的平均长度, k为分配参数, 由与节点相连的链路数决定取值, 通常取3.0～3.5。

综上可知, 节点i的权值为节点i所邻接的各有效链路的权值之和

得出各路径的权值为

可靠性与路径的权值直接相关, 路径的权值越大, 可靠性就越大, 这是对每条路径进行数据流量分配的基础。

3 路径选择

在源节点与目标节点之间可能存在多条跳数最小的路径pmin和可选路径palt。因此, 所有可用的路径为p=pminUpalt。不过, 这中间可能有部分路径的性能很差, 以至于不能用来传输数据, 在分配流量时, 就不再使用这些路径。也就是说在分配流量比例的时候, 只需要用到那些性能比较可靠的路径。对于一组合格的路径pelg, 采用加权轮询路径选择方式, 根据它的权值选出一条路径p∈pelg, 算法选择使用一个确定的算法来保证流量比例维持在一个尽可能小的时间窗内。它采用确定的路径队列, 队列中的路径都以一个与流量比例相近似的频率周期性地发布。它通过生成一个路径队列来实现, 这些路径在尽可能小的时间窗内维持流量比例。这个队列由加权轮询路径选择方式快速地产生, 对于每个流入的数据, 加权轮询路径选择方式生成队列中的下一条路径, 数据流量分布到这条路径上去, 具体过程用程序表示如图2:

4 流量分配比例计算

根据前面建立的多路径模型以及计算得出的所有路径的权值, 按照路径权值的大小顺序进行排序, 确定使用的n条路径为权值排在前列的n条路径。显然, 流量分配比例与路径的权值大小成正比, 即权值越大的路径分配到的流量比例也相应越大, 权值小的路径相应分配的流量比例也小, 甚至由于部分路径的权值太小而导致性能太差, 可能根本不会使用。因此, 在这里设rpk为分配到路径pk的流量比例, 则有rpk>rpk+1。

对于每条路径的流量比例分配, 应考虑到流量小的情况。如果数据流量较小, 根本不需要使用多条路径来进行传输, 因为较小的数据流量采用多条路径进行传输, 所花费的开销过大, 效率反而不高甚至更低。所以在数据流量较小的情况下, 我们选择其中的最优路径来传输, 也就是权值最大的第一条路径。即这条路径此时的传输比例为1。多路径主要是针对数据流量较大的业务。分配给各条路径的流量比例计算方式如下:

这里, 考虑到由于无线mesh网络的动态性, 网络拓扑结构经常发生变化, 路径状况必然也是经常改变。所以对路径权值的计算要周期的进行更新。

本文的算法中, 所有节点均采用分布式推进方法交换信息, 每个节点保留它能侦听到的相邻节点的IP地址。每个节点规则地广播一个HELLO消息。HELLO消息包括以下几个域:{节点i的地址, 相邻节点j的地址, 链路 (i, j) 状态参数。当节点i收到相邻节点j返回的HELLO消息时, 可得到链路 (i, j) 的延时参数, 以这个参数更新节点中记录的路由状态信息的延时参数, 从而更新路径权值, 保证路径权值能适时的反应当前的网络拓扑情况。当一个节点i连续三次没有收到其邻居节点j的HELLO消息时, 就认为它们之间的连接中断, 链路延时为无穷大, 权值相应变为0。

网络拓扑每次发生变化就马上进行权值的更新, 其代价很大没有必要。本文设置一个时间周期, 在每个时间周期结束时就重新计算流量的分配比例{rpk, pk∈P}。一个时间周期由η个循环组成, η是用来控制统计流量的健壮性和稳定性的可配置的系统参数, 主要由网络拓扑变化情况和负荷稳定程度来确定, 如果变化较慢就设置值大一些, 变化快时设置值相对小一些。流量分配得越正确, 时间周期就越稳定。η的取值一般在1～3之间。在每一个时间周期里, 如果网络拓扑不发生巨大变化, 每条路径分配的流量比例就相应的稳定。在一个时间周期结束后, 才根据更新后的权值重新计算流量比例。

如果在一个时间周期内网络拓扑发生巨大变化, 比如说多数路径都中断了, 这时必须重启路径发现程序, 触发权值计算过程, 重新计算各路径的数据流量分配比例。

5 仿真结果及分析

本文采用NS-2仿真平台对算法进行验证。利用random waypoint model作为节点的移动模型。主要参数设置为:MAC层使用IEEE802.11协议, 信道带宽为2Mbit/s, 节点数量为50个;在区域1km×1km上的数据包发送率为10包/s, 数据包大小为64B;业务流类型为CBR (constant bit rate) ;移动距离为250m, 整个仿真时间为300s。仿真结果如图3～图5所示:

从图3可以看出AODV算法与本文提出的算法ADMR的负载情况。ADMR有效地限制了控制包的洪泛区域, 也减少了路由的负载。并且由于ADMR根据路径权值的大小去掉了不稳定及效率低的路径, 所以有更小的路由负载。

图4显示了节点移动的速度对路径平均延迟的影响:ADMR的路由平均延迟随速度的增加比AODV的增加明显更小。

两个算法的数据包投递率如图5所示。随着速度的增加, AODV的数据包投递率也有一定的下降。ADMR采用多条路径进行传输, 减少了丢包的可能性, 并且高质量的路由也保证了数据包的高投递率。

6 结论

本文提出的基于动态网络拓扑的自适应流量分配算法ADMR, 通过计算各路径的权值, 根据权值去掉不稳定及效率低的路径;流量依据权值的大小按比例自适应的分配到各条路径进行传输, 保证了数据包稳定传输, 提高了网络的数据包的高投递率。

摘要：无线mesh网络以其鲁棒性、覆盖区域广、低成本、接入便利等特点日益成为无线接入网络的主要形式, 在无线通信技术中扮演越来越重要的角色。针对无线mesh网络的特点, 本文提出一种基于动态拓扑的多路径自适应流量分配算法。此算法根据路径质量的权值动态地给各路径分配数据流量比例。仿真结果表明, 此算法保证了数据包的稳定传输以及提高了数据包的投递率。

关键词：多路径,mesh网络,自适应

参考文献

[1]Jun J, Sichitiu M L.The nominal capacity of wireless mesh networks[J].IEEE Wireless Communication, 2003, 10 (5) :8-14

[2]Xiao J T, Kunz T.Traffic balancing in wireless mesh networks[C]//2005International Conference on Wireless Networks, Communications and Mobile Computing.Las Vegas, USA, 2005:169-174

[3]Whitehead P.Mesh networks:a new architecture forbroadband wireless access systems[C]//2000IEEE Radio and Wireless Conference.Denvor, USA, 2000:43-46

[4]Lee S J, Gerla M.Split multipath routing with maximally disjoint paths in ad hoc networks[C]//Proceedings of the IEEE ICC.Helsinki:IEEE Press, 2001:3201-3205

[5]Peter P P.Congestion Avodiance Using Multipath Routing and Power Control In Mobile ad hoc Network[D].Adelaide, University of South Australia, 2002

[6]An H Y, Lu X C, Peng W.A cluster-based multipathrouting for MANET[A].Proc of Med-Hoc-Net2004[C].Bordum, 2004.405-413

[7]Wang L.Multipath source routing in wireless ad hoc networks[J].Canadian Conf Elec Comp Eng.2000 (1) :479-483