无线Adhoc-盘古文库

无线Adhoc（精选8篇）

无线Adhoc 第1篇

无线移动ad hoc网络 (Mobile Ad Hoc Network, MANET) 是由一组带有无线收发装置的移动终端组成的多跳、临时性的自治系统, 无线终端兼有路由器和主机功能, 具有动态和分布式的拓扑结构。它以其组网灵活性强、支持移动性、易于迅速展开、系统整体抗毁能力强、系统成本低等优点, 成为通信领域中的一个热点。移动ad hoc网络的应用领域非常广泛, 如搜寻与营救、灾难重建、移动办公、虚拟教室、传感器网络等。本文在介绍ad hoc网络体系结构及特点的基础上, 分析了其面临的各种安全威胁, 对其安全策略进行了探索。

1 ad hoc网络的体系结构及主要特点

1.1 ad hoc网络的体系结构

ad hoc通常采用完全分布式结构 (见图1) 和分层分布式结构网络 (见图2) 。在完全分布式结构中, 每个节点都具有路由功能, 节点之间的实现方式及在网络中的地位是等价的, 功能灵活, 但节点实现代价较高。分层分布式结构综合了集中式和分布式结构特点, 它以簇 (Cluster) 表示一个子网, 节点被划分成若干个簇, 簇中只有一个节点具有路由功能。在簇内部, 节点可以通过路由节点转发, 也可以直接通信。不同簇中的节点通信, 则需要通过有路由功能的节点来转发。如果网络规模太大, 可以采用聚类分层的管理模式。

1.2 ad hoc网络的主要特点

(1) 无中心自组织

ad hoc网络是无控制中心的对等式网络。网络中所有节点的地位平等。网络具有很强的健壮性和抗毁性, 任意一节点的加入和离开都不会影响整个网络的运行, 节点通过分层协议和分布式算法协调各自的行为, 可以在任何时刻任何地点快速展开并自动组网。

(2) 动态拓扑

没有固定的通信设施和中央管理设备, 网络节点可以随机地以任意速度向任何方向移动, 加上无线发射装置发送功率的变化、环境的影响以及信号之间的互相干扰等因素, 都会造成网络拓扑结构的动态变化。图3中节点A、B、C、D构成了一个ad hoc网络。圆圈表示节点A的无线电通信范围。网络的最初拓扑结构如图3 (a) 所示。当节点D移到A的无线电通信范围之外时, 网络的拓扑结构发生变化如图3 (b) 所示。

(3) 无线传输带宽受限

ad hoc网络采用无线传输技术作为底层通信手段, 由于无线信道本身的物理特性, 它所能提供的网络带宽相对于有线信道要低得多, 并且无线信道的质量较差。此外, 考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等因素, 移动终端得到的实际带宽远远小于理论上的最大带宽, 并且会随时间动态变化。此外, ad hoc网络终端一般依靠电池供电, 节省电能以延长工作时间也成为一个重要问题。

(4) 多跳路由

节点有限的发射功率决定了其有限的覆盖范围, 当它要与其覆盖范围之外的节点进行通信时, 需要中间节点的转发。此外, ad hoc网络中的多跳路由是由普通节点协作完成的, 而不是由专用的路由设备 (如路由器) 完成。

2 ad hoc网络的安全目标

2.1 可用性

即网络服务对用户而言必须是可用的, 也就是确保网络节点在受到各种网络攻击 (主要指拒绝服务攻击) 时仍然能够提供相应的服务。在ad hoc网络中拒绝服务可以发生在任何一层上:在物理层和媒体接入层, 攻击者可以通过无线干扰来扰乱物理通信信道;在网络层, 攻击者可以攻击路由协议;在高层, 攻击者可以攻击各种高层服务。针对ad hoc网络还有一种“剥夺睡眠”的攻击, 它能够使移动节点的电池迅速耗尽, 以实现拒绝服务。

2.2 机密性

机密性保证相关信息不泄露给未授权的用户或实体。采用无线信道的ad hoc网络容易受到窃听攻击, 所以必须要保证在网络中传输的敏感信息的机密性。特别是路由信息也要在一定程度上保证其机密性, 因为在战场上路由信息的泄露会使敌方能够判断出移动节点的标识和位置。

2.3 完整性

完整性保证信息在传输的过程中没有破坏或中断。这种破坏或中断包括网络上的恶意攻击和无线信号在传播的过程中的衰弱以及人为的干扰。

2.4 认证

一个移动节点需要通过认证来确保和它通信的通信对端就是真正的通信对端, 也就是说要确认通信对端的身份。如果没有认证, 那么网络攻击者就可以假冒网络中的某个节点来和其他的节点进行通信, 就能够获得那些未被授权的资源和敏感信息, 进而威胁整个网络的安全。

2.5 不可否认性

不可否认性保证一个节点不能否认其发送出去的信息。这样就能保证一个移动节点不能抵赖它以前的行为。在战场上如果被占领的节点发送了错误的信息, 那么收到该信息的移动节点就可以利用不可否认性来通知其他节点该节点已被占领。

3 ad hoc网络的安全策略

3.1 路由协议

其安全威胁来自两个方面:一是网络外部的攻击者通过发送错误的路由信息、重放过期的路由信息、破坏路由信息等手段, 来达到致使网络出现分割、产生无效的错误路由、分组无谓的重传, 网络发生拥塞并最终导致网络崩溃的目的, 攻击者还可以通过分析被路由业务流量来获取有用信息;二是网络内部的攻击者可以向网内其他节点发布错误的路由信息和丢弃有用的路由信息。两种攻击都能造成网络中合法节点得不到应有的服务, 因此也可以看作为一种拒绝服务攻击。可以使用数据安全中的各种加密机制来解决第一种威胁, 比如带有时间戳的数字签名。解决第二种威胁的可行方法是要求合法节点周期性的交换标识序列符, 标志序列符由节点的标志符和序列号组成。占领某个节点的入侵者虽然能够获得合法的密钥, 但他很难知道标志序列符, 因此可以在一定程度上减少这种攻击带来的威胁。

3.2 密钥管理

移动ad hoc网络与分布式系统一样, 其安全依赖正确的密钥管理系统, 包括信任模型、密码系统、密钥生成与分发以及密钥存储。信任模型确定网络中相互信任的成员类型, 根据网络环境和应用的不同而异, 不同类型成员间的信任关系直接影响网络的密钥管理系统;密码系统指密钥管理中使用的加密机制, 通常为非对称或对称加密机制;密钥生成确定网络中哪一部分成员能够生成密钥, 并指出密钥的所有者。同时, 密钥管理服务必须保证生成的密钥被安全地发送到其所有者, 保证通信的私密性、完整性和可用性;密钥存储指密钥管理服务保存私密密钥的方式和方法。

3.3 访问控制

在网络层, 路由协议必须保证不允许非授权节点加入网络, 保证没有敌对节点加入和离开网络而不被检测到。在应用层, 访问控制必须保证非授权用户不能访问服务。访问控制常与身份识别和认证相关联, 确保合法用户有权访问服务。在一些系统中可能不需要身份识别和认证, 节点通过证书来访问服务。根据不同的网络结构和安全级别, 访问控制的实现方式也不同, 集中式的低安全级别网络, 可以采用服务器控制的方式, 用户ID加密码等措施。

3.4 入侵检测

入侵检测系统有入侵检测和隔离两项职能。入侵检测按检测数据源分为基于主机的检测和基于网络的检测;按分析和检测方法分为误用检测和异常检测。ad hoc对入侵检测技术提出了重大挑战: (1) 开放的环境。使用知识库的更新是困难的, 因为节点可能工作在不相连状态。异常检测模型是建立在对用户行为的长期学习基础上的, 而ad hoc中的节点生命周期短并不断移动。 (2) 审计数据是局部的, 缺少集中控制。ad hoc中没有流量集中点, 没有集中式服务器。 (3) 正常/异常行为没有清晰的区别, 如网络拓扑的改变使得很难判别一个提供了错误消息的节点是Byzantine式还是仅仅失去同步。 (4) 有限的资源。这个特性使得入侵检测系统必须是轻负载、低计算量的。

4 结语

无线ad hoc网络具有的特点使得其有着巨大的应用前景, 必将会在未来的通信领域发挥巨大作用。值得注意的是ad hoc网络的安全要求随应用环境的不同而有所差别, 有些环境很低, 而有些环境的要求是很高的, 比如在战场环境。因为安全要求和解决的方案的不同, 一个统一的安全架构的还未完全建立, 还有大量安全性方面的工作需要进一步研究。

摘要：无线ad hoc网络是一种新型的无线移动网络。介绍了ad hoc网络的体系结构和主要特点, 归纳了ad hoc网络的安全目标, 提出了解决其安全问题的安全策略。最后, 展望了无线ad hoc网络的研究方向。

关键词：ad hoc,网络安全,安全策略

参考文献

[1]RFC2501.Mobile Ad Hoc networking (MANET) :Routing protocol performance issues and evaluation considerations[S].

无线Adhoc 第2篇

无线Ad-hoc网络的安全问题

与传统的无线网不同，无线Ad-hoc网络作为一种新型的无线移动网络，不依赖于任何固定设施，而是通过移动节点间的相互协作保持网络互联。由于该网络的独特性，它正逐步运用于商业环境。设计这种网络面临的一个主要挑战就是它易受到安全攻击，比如受到、伪造、拒绝服务等攻击。

在无线Ad-hoc网络中没有基站或中心节点，所有节点都是移动的，网络的拓扑结构动态变化。节点间通过无线信道相连，没有专门的路由器，由节点自身充当路由器，同时也没有命名服务、目录服务等网络功能。这就导致了在传统网络中的安全机制不再适用于Ad-hoc网，所以应提出专门针对无线Ad-hoc网络的安全机制。目前提出的安全策略有：基于口令的认证协议，它与传统的口令认证不同的地方是密钥和口令的产生是由多台机器决定，而不是集中由一台机器产生，并且还提供了一种完善的口令更新机制;“复活鸭子”的安全模式，它主要针对传感器网络里，传感器与控制者之间可能存在的不安全问题，提出传感器在“死亡”之前，只受其拥有者的控制;异步的分布式密钥管理，它提出密钥管理服务是由多个节点(一个集合)来管理，而不是单个节点来管理，

无线Ad-hoc网络的互联

无线Ad-hoc网络是一种多跳网，上述的路由算法都属于单个网内的，现在多数的文章也都集中在这个方面讨论，却很少涉及如何把多个Ad-hoc 子网联接成一个大网及如何与有线Internet相结合，由此便提出将无线Ad-hoc网络互联的问题。

通过使用网关路由器，可以实现将几个Ad-hoc网络互联以及网内节点可以访问互联网的功能。这种形式可以向位于多个分散地理位置上的工作小组提供协同通信能力。

无线Ad-hoc网络与Internet和广域网的互联，从外部来看，可以认为Ad-hoc网是一个IP子网。网内部分分组的传送是由网内路由协议完成(分组到达目的地可能要经过多跳)，而当分组进入或离开子网时，采用标准IP路由机制。这就要求网关节点要能运行多种路由协议。

无线Adhoc 第3篇

Ad hoc网络是由一组带有无线通信收发装置的移动终端节点组成的多跳无线网络,各节点之间通过无线信道对等的信息包传送来完成相互通信。而组成它的每一个移动终端都可以自由移动,地位平等。它的网络拓扑会随着用户终端随意移动,开机,关机,无线电发射功率变化,无线信道间相互干扰以及地形等综合因素影响而动态变化。ad hoc网络的这些特性,使得对于其性能的测量存在很大的困难。吞吐量是评价一个网络性能的重要参数,如何估计和提高ad hoc网络吞吐量一直都是研究的热点。我们采用全球定位系统GPS,实时地获取各个移动节点的位置信息,周期性的调整网络的拓扑结构;同时,通过控制节点的功率和相应的转发策略,来估算ad hoc网络的吞吐量。

2 ad hoc网络模型及其吞吐量的计算

2.1 ad hoc 网络模型

为了能够比较准确计算无线ad hoc网络的容量,我们首先对整个网络系统假设如下:

1):假设这个ad hoc网络共有n个节点,分别为s1,s2,,sn,每个节点均有发射机和接收机,各个节点之间可以通过单跳或者多跳通信,各节点的缓冲区无限长,节点在平面上随机分布,各节点的位置信息通过全球定位系统GPS来获取;

2):假设在一个时隙内每个发送节点在发包时的发送功率pi(t),pi(t)的大小可以调节;

3):在同一个时隙内,各个节点发包的概率为P。

2.2 吞吐量的计算

通过GPS我们可以获取收发节点的位置信息,假设发送节点的位置为Xi(i=1,,m),各接收包的位置Xj(j=1,,n-m)。根据参考文献[2],如果pi(t)为发送功率,传输信道的信噪比为SNR,节点个数为N,当α>2时,如果

$\frac{p_{i} (t) ∥ X_{i} - X_{j} ∥^{- α}}{Ν + \sum_{k \neq i} Ρ_{k} (t) ∥ X_{i} - X_{j} ∥^{- α}} \geq S Ν R (1)$

那么从发送端i发出的信息可能会被接收端节点j接收到,因为节点i 可以和节点j 之间存在一条无线信道,能够保证i和j节点保持在连通状态。连通是任何拓扑控制算法都必须保证的一个性质,也就是从任何一个结点都可以发送消息到另外一个结点。

传输信道的信噪比可以通过各个单条信道的信噪比累加来确定。假设每条链路的信噪比为SNR ,则传输信道的信噪比:

$S Ν R = \sum S Ν R_{i j} (2)$

因为节点i向节点j发送包的时候的功率为pij(t),假设增益为Gij,σ2为接收节点的热噪声功率,则每条收发链路上的信噪比为

$S Ν R_{i j} = \frac{p_{i j} G_{i j}}{σ^{2} + \sum_{k \neq i, l \neq j} Ρ_{k l} (t) | G_{k l}} (3)$

链路增益Gij与传输距离d的α次方(α≥2)成反比,可以表示为

$G_{i j} = k / d^{α} ‚ 其中 k 为常量 (4)$

将(4)代入(3),(3)代入(2)式,(2)式代入(1)式,就能确定ad hoc网络中所有接收节点的状态R1。令

$R_{1} = [\begin{matrix} Ρ_{11} & Ρ_{12} & \dots & Ρ_{1, j - 1} & Ρ_{1 j} \\ Ρ_{21} & Ρ_{22} & \dots & Ρ_{2, j - 1} & Ρ_{2 j} \\ \dots & \dots & \dots & \dots & \dots \\ Ρ_{i - 1, 1} & Ρ_{i - 1, 2} & \dots & Ρ_{i - 1, j - 1} & Ρ_{i - 1, j} \\ Ρ_{i 1} & Ρ_{i 2} & \dots & Ρ_{i, j - 1} & Ρ_{i j} \end{matrix}] (5)$

根据文献[3],一般控制每个节点的与其距离最近的6～8个节点进行连接就能使网络拓扑满足网络的各种不同的性能指标。适当的调整R1的值来满足上述原则,并周期性的对网络拓扑结构进行更新。

为了方便,我们构建的ad hoc网络均采用电池供电,因此能量在无线网络中显得尤为珍贵[4]。一般情况下,有的结点都会以最大无线传输功率工作,这对于ad hoc网络来说存在很大浪费的现象:节点有限的能量会被快速消耗,使得网络的生命周期大大减少,同时,网络中各个结点的无线信号将会影响到其他的结点,造成无线信号冲突频繁,影响网络的通信质量,降低网络的吞吐率;另一方面,有些节点为了节约自己的能量,延长使用周期,往往会拒绝为别的节点转发数据,这种'自私'的策略[1],也会使整个网络系统的性能受到严重的影响,从而影响网络的吞吐量。

为了能够延长网络生命周期,提高网络吞吐量,降低网络干扰,节约节点资源,我们提出了如下算法:

POSITION:各个移动节点当前的位置信息,这个可以通过GPS来获得。

TIME:是记录每个包的发送时间或者接收时间。在发送端,标记其发送的时间,当该包能够被正确接收时,记录其接收时间。

COUNT:用来记录节点接收包的个数,对于每个节点,如果能够成功接收到其他节点发来的包,则其包的个数增加1。

SUM:记录其转发数据的次数。

CONTROL:是否转发其他节点传来的数据。转发控制的策略如下:

1) 当从源端到目的端只有一个节点可以转发该数据时,则该节点强制性的转发数据,并适当的增加其功率;

2) 当从源端到目的端有多个节点可以转发该数据时,则所有转发节点根据转发的次数进行比较,并按照转发次数的多少来分配转发任务,转发次数少的节点优先转发数据,并适当的增加转发节点的功率,而暂时不转数据的节点分配小一点的功率,只要保证网络连接即可。

ADJACENT:与该节点相邻的节点的信息。每个节点都会周期性检测相邻节点的变化。当检测到相邻的节点有变化时,那么它就更新当前网络拓扑结构并决定是否更新网络连接,如果更新的拓扑没有保持连接,则节点试图修复这个网络拓扑,并将更新的信息传给相邻节点。

接下来我们计算网络的吞吐量。根据Ad hoc网络吞吐量的定义,即一个时隙内网络中平均成功接收到的数据包个数[4]。为了精确的计算网络的吞吐量,严格时钟同步是有必要的。目前对时钟同步的算法有很多种[5,6],这几种算法的精确度都存在一些的缺陷。利用全球定位系统GPS就可以精确地实现各个移动主机间的时钟同步。

假设接收节点个数为有R个,各个接收节点的接收到的数据包分别为Si(i=1,,n-m),则整个网络的吞吐量为:

$Τ Η R = R \sum_{i = 1}^{r} S_{i}$

3 实验结果和分析

我们的实验是由9个智能节点构成的移动adhoc网络,各个节点的能量都有限,采用电池供电。在实验中,采用的参数如下:所有节点均匀的分布于一个250m的区域并能随机移动,移动的速率均匀分布于(0,Vmax),Vmax=0.3m/s,各个节点的发包概率为p,在实验中我们让p的概率在0到1之间每隔0.025增加。实验的结果如图 1所示。

图中,深色的线条是采用了转发策略和功率控制时测得的吞吐量,浅色的线条是没有采用任何策略的吞吐量。从图上可以看出,采用我们的算法计算出来的吞吐量有明显的增加。

4 结论

本文通过GPS获取各个主机间的位置和时间信息,调整网络的拓扑结构,并采用一种新的转发策略和功率控制策略。实验证明,该方法能够有效的提高ad hoc网络吞吐量。

参考文献

[1]Vikram Srinivasan,Pavan Nuggehalli,Carla F.Chiasse-rini,Ramesh R.Rao Cooperation in Wireless Ad HocNetworks[J].In Proceedings of IEEE INFOCOM,vol-ume 2,pages 808-817,Mar 2003.

[2]KNOPPR,HUMBLETPA.Information Capacity and Pow-er Conctrol in Singal-cell Mulitiuser Communications[J].Pro c.IEEE Int.Conf.Commun.,vol.1,Jun.1995,pp.331-335.

[3]MAYW,CHEN CM.The application of the random graphmodel for the reliability of dynamic computer network[A].IEEE INFOCOM[C],pp:43-48.

[4]Dinesh Kumar Ramaiyan Venkatesh,Anurag Kumar EitanAltman Capacity Optimizing Hop Distance in a Mobile AdHoc Network with Power Control[A].Proceedings of the4th International Symposium on Modeling and Optimiza-tion in Mobile,Ad Hoc,and Wireess Networks(WiOpt'06)[C],Boston,Massachusetts,April 3-7,2006.

[5]王洪波,林宇,金跃辉,程时端.一个消除单向时延测量中时钟频差和时钟重置的新方法[J].电子学报,2005(4):584-589.

无线Adhoc 第4篇

无线Ad Hoc网络是由无线移动节点组成的复杂的分布式网络系统。其中所有节点在同一层次,地位平等,无任何中心控制节点的设置,具有较强的容错性、鲁棒性和抗毁性[1,2]。但是无线Ad Hoc网络若要实现有线网络所支持的有服务质量保证的各种业务,还需要在很多方面做研究。无线Ad Hoc网络会受到的影响大多来自现实因素:比如带宽有限、拓扑动态变化和无线链路可靠性差等。这些都使得无线Ad Hoc在服务质量方面面临很大挑战。目前无线Ad Hoc路由协议主要可以分为表驱动、按需路由以及混合式路由协议。典型表驱动路由协议有DSDV,OLSR等;典型的按需路由协议有:AODV、DSR等;典型的混合式路由协议有:DDR、ZRP等[1]。

AODV协议是目前在无线Ad Hoc网络中应用比较广泛的路由协议。其特点是采用了序列号来确保始终无闭环。AODV协议由路由发现和路由维护两部分组成,有3种类型的消息控制帧:路由请求RREQ、路由应答RREP和路由错误RERR。协议不需要维护到达所有目的节点的路由,仅在没有相应目的节点的路由时才按需进行路由查找。

AODV协议[3]的路由发现过程使用目的节点序列号机制,每个节点维护一个本地“序列号”和一个“广播标识”ID,再加上本节点IP地址,就能唯一标识一次路由请求,保证了路由信息的及时性并避免了循环路由的产生。

如果有效路由不存在,源节点首先进行路由查找,广播RREQ,因此在网络建立初期,会频繁发起路由请求,从而导致初始路由延迟问题。同时AODV采用最短路径路由算法,以跳数作为路由评价标准,跳数相同时,选择序列号大小进行评价,而没有考虑节点的负载、节点流量等代价问题,因此,所查找到的最短路由未必是最优路径,可能会降低传输效率,甚至导致网络拥塞、数据包丢失,引发数据重传等情况。文献[4]提出了一种改进的算法M＿EAODV采用备份路由的方式,避免了重新寻找路由带来的开销,部分减少了链路的时延,由于备份需要占用一定的资源,传输性能并没有得到更好地提升。

本文提出了一种改进的WAODV(Wardrop-AODV)路由算法,利用Wardrop均衡理论对AODV协议进行优化,实现每组数据包选择经过的路径时延是最小的。经过多次的调整,可以认为数据流会根据WAODV路由算法近似均匀的分配到不同的路径上,使得网络中所有可以选择路径上的时延近似相等。WAODV算法能够调整网络上由于AODV路由协议的最短路径算法选择下一跳造成的拥塞情况,数据包丢失等问题,提高网络传输效率的目的。仿真结果表明,WAODV算法在数据包送达比例、数据包平均端到端延迟时间上得到了有效改善,提高了网络的传输效率。

1 WAODV路由原理及算法

1.1 Wardrop均衡

Wardrop均衡[5]是由著名交通问题专家Wardrop于1952年提出来的,是研究交通规划问题的重要方法,又称为“用户平衡(User EquilibriumUE)条件”。假设每个节点都是“自私”的,当没有一个节点可以通过改变自己的路径能够降低自己的阻抗(时延、链路利用率等等)时,就说网络实现了Wardrop均衡。通俗来说就是保证了每个用户所要通过的路径是阻抗最小的,即对单个用户来说是最优的。假设用户都是自私的,每个用户都会选择对自己来说最优的路径,经过一段时间的选择,整个交通网络就会达到Wardrop均衡,从而可以有效减轻交通网络阻塞。Wardrop均衡用数学表达式表示如下:

其中,是源节点r到目的节点s在路径k上的流量,是源节点r到目的节点s在路径k上的阻抗,μrs可以被认为是从起点r到终点s的路径集合中最小阻抗路径的总阻抗。如果路径k上没有数据流经过(),则等式(*)自然满足;如果有流量经过路径k (),则右侧的必须为0才能满足该条件。数据流总是尽可能地分配到那些拥有最小阻抗的路径上()。从网络整体数据流流量来看,当某条最小阻抗路径因为用户选择而导致阻抗上升时,随后新到的用户就会被重新分组到该时刻的最小阻抗路径上,最终促使整个交通网络的各链路的阻抗趋向均衡。

本文借助Wardrop均衡理论在计算机网络上进行了尝试,假设每个路由都是“自私”的,并且都会选择对自己来说“代价”最小的路径,经过一段时间的选择,整个网络就会达到Wardrop平衡,从而优化计算机网络上的拥塞问题,仿真实验证明确实起到了很大的优化效果。

1.2 WAODV路由描述

WAODV(Wardrop-AODV)路由算法利用Wardrop均衡理论对AODV路由算法进行了优化。当AODV路由算法发起到目的节点的路由查找时,WAODV路由算法增加路径最小“代价”作为选择下一跳路由的条件,从而使得整个网络达到Wardrop均衡。

根据Wardrop均衡理论,网络中的所有节点路由都是“自私的”。每个源节点都希望通过能够通过网络以最快的速度、最高的性能发送数据包到目的节点。本文把Ad Hoc网络描述为连通图G(V,E),其中V为网络中的节点,E为相邻节点间的路段。本文采用文献[6]的方式,把Ad Hoc网络抽象为一棵路由树,以目的节点为根节点,让每层的节点借助所计算的最小“代价”确定其最优的下一跳节点。为了确保从数据源节点r到目的节点s之间的路径是最优路径,本文采用泛洪[7]广播方式寻找最小“代价”路径,保证各节点可以找到到目的点s的最小“代价”路径。Ad Hoc网络抽象的路由树的建立过程如下:

(1)目的节点s采用泛洪方式确定第i个节点到目的节点s的深度di(目的节点的深度定义为0,距离目的节点跳数为1的节点深度记为1,距离目的节点跳数为2的节点深度记为2,其他深度的节点以此类推)。

(2)从目的节点开始,各个节点(如i节点,设其深度为di)逐次向其下一跳的深度为的di+1的节点发送数据包传输到目的节点的最优路由代价估计Ti。

其中,Ti表示节点i到达目的节点的最小代价路由的总代价,值为该路径上各跳传输代价之和,本文中每跳传输的代价用时延表示,由泛洪广播到本跳计时得出(目的节点的时延为0即Ts=0)。对于第i个节点,Ti=min{Ta+Tia,Tb+Tib,}。

(3)第i个节点收到上一深度级相邻节点a,b传送的节点信息后,为每个相邻节点建立路由信息表(见表1)。

表1中,Tia是a节点到达i节点的时延,Ta是目的节点s经由a节点到达i节点所经历的总时延(目的节点的时延Ts=0,若节点x为目的节点的下一跳,就能够计算出Tx=Ts+Txs;若节点y也为目的节点s的下一跳,则计算出Ty=Ts+Tys,若节点z是节点x和y共同的下一跳,则计算出Tz=min{Tx+Txz,Ty+Tyz},依次计算能够得到到达源节点的最小路径时延)。上述信息在目的节点得到Ad Hoc网络全局拓扑后,告知所有节点。至此,最小代价路由树建立完成,我们进而建立了一个新的达到Wardrop均衡的WAODV(WardropAODV)路由算法。基于本算法,作为源节点的节点发送数据包后,将按照最小代价路由方式将数据包传输到自的节点。每次有新的节点作为目的节点时,重新生成路由树并接收各点数据。

无线Ad Hoc网络在每个周期内都会进行若干次路径的重新选择,各节点总是根据WAODV路由算法将数据包发送到路由“代价”最少的路径上(类似于最小“代价”路由)。将这些小的片段连起来观察就会发现,随着链路上的时延增大,当链路上的代价发生变更后,后续的数据包就可能会回避该路径,而选择那些整体时延小的路径进行传输。经过多次的调整,可以认为数据流会根据WAODV路由算法近似均匀地分配到不同的路径上,从而网络中所有可以选择路径上的时延近似相等。从而能够调整网络上由于AODV路由协议的最短路径算法选择下一跳造成的拥塞情况,提高网络的整体传输效率。

1.3 算法流程

流程如下:

(1)任选一个节点作为目的节点s0,初始化信息M (详见表2);

(2)由目的节点s0发送泛洪广播信息M;

(3)广播到达下一节点,更新信息M,同时更新本节点的路由表信息;

(4)判断本节点是否是源节点r0,如果是则广播停止,如果不是则转步骤(3);

(5)找到源节点r0,根据路由信息表中代价最小的Tr0进行路由查找,传输信息;

(6)选择节点作为目标节点{s0,s1,s2,,sn},进行1到5步骤的计算,每次都按照最小代价路径进行信息传输;

(7)经过N次迭代,所有有流量经过的路径最小代价值近似相等(Tr≈Ts),网络达到Wardrop均衡。

1.4 模型验证

为了验证WAODV路由算法的有效性,可以对该路由问题建立相应的数学最优化模型(W)并进行分析。

规定数据传输过程中链路a (1跳)的“代价”函数为za(x)=xta,,A为所有链路的集合。规定Ad Hoc网络的一个周期中,x表示所有路径经由该链路a (1跳)传递的数据包,ta为链路a的时延。从起点r到目的节点s之间若干可选的路径(路由)集合Krs中,经过路径k传输的总“代价”可以表示如下:

Ad Hoc网络会进行若干次路径的重新选择,各节点总是根据WAODV路由协议将数据包发送到路由“代价”最少的路径上(类似于最小“代价”路由)。随着某条链路上的时延增大,此链路上的“代价”变大后,后续的数据包就会避开该路径,而选择那些链路“代价”小的路径进行传输。经过多次的调整,可以认为数据流会根据WAODV路由协议近似均匀的分配到不同的路径上,促使网络中所有可以选择路径上的时延近似相等。

为了在网络中体现传输的总“代价”最小,可以构造目标函数如式(2)。目标函数本身做了必要的数学等价变换,并没有什么直观的经济含义。实现Ad Hoc网络传输“代价”最小采用的最优化模型(W),是交通规划中对流量分配问题的一个重要的等价数学变换,也被称为Beckmann[7]变换。

Ad Hoc网络传输“代价”最小的最优化模型可描述如下[5]:

其中,约束条件式(3)为流量守恒条件,要求从源节点到目的节点的所有数据流量等于传输过程中各个路径的流量之和。k为所对应的某条路径。qrs是源节点到目的节点的流量。式(4)为数据流非负约束,是源节点r到目的节点s在路径k上的流量。式(5)是路径流量与弧流量的转化关系。表示如果弧a在链接r-s的路径k上,则其值为1;否则为0。模型(W)中描述的路由分配策略确保每次找到的路径都符合最小“代价”路由的特点。

可以证明,模型(W)的一阶必要条件满足本文提出的路由选择方式。模型(W)的Lagrange函数可以表示为:其中,μrs是式(2)的对偶变量(Lagrange乘子),则目标函数的一阶必要条件为:

其中:

目标函数的一阶必要条件可以简化为如下形式:

满足Wardrop均衡的条件。如果路径k上没有数据流经过(),则式(8)自然满足;如果有流量经过路径k (),则右侧的必须为0才能满足该条件。在Ad Hoc网络中,与μrs可以看成是具有相同单位的两个指标,且由目标函数的一阶必要条件的性质,μrs可以被认为是从起点r到终点s的路径集合中最小“代价”路径的总代价,即数据流总是尽可能地分配到那些拥有最小“代价”的路径上()。从网络整体数据流流量来看,当某条最小“代价”路径由于传输数据而导致“代价”上升时,随后新到的数据流就会被重新分组到该时刻的最小“代价”路径上,最终导致整个网络的整体“代价”趋向均衡。

在模型(W)中,目标函数的表达形式相对复杂,如果在优化模型中,直接按约束条件求解模型是非常困难的。针对此类路径难以求解的问题。Beckmann[7]提出采用Frank-Wolf[8]方法将一般网络流问题中难以计算的路径流量转换成为相对容易计算的弧流量,带入到模型中,并用较为简单的“全有全无”方法进行求解,这是一种启发式的方法,先将O-D对(即由源节点到目的节点组成的网络)阵均分成N等份,然后在每次迭代中只将一份O-D阵加载到网上,计算积累的弧流量和相应的弧阻抗,并转入到下一轮迭代中,利用这种方法,能较好的逼近结果[3]。本文也将该方法引入到求解算法中,并针对所提出的模型(W)构造如下的求解算法:

第一步将O-D矩阵均分成N等份,,置n=1,且。

第二步计算。

第三步根据将第n等份O-D矩阵加载至网络上,并计算由其形成的弧流。

第四步计算。

第五步如果n=N,停止迭代,则即是问题的解;否则置n=n+1,转第二步。

当整个网络达到了Wardrop均衡时,由此求出的最优化模型的解,是一个相对精确的最小“代价”值,理论上近似等于我们上面通过寻找最小“代价”路径时,得到的最小“代价”值。

2 仿真实验

2.1仿真环境及参数

在Ubuntu 10.0环境下,采用NS-2.35仿真平台来进行仿真,所有试验编码采用C++语言TCL脚本语言实现。采用的仿真环境是由20个无线节点组成的网络拓扑图(如图1所示),分布在300m*400m的仿真区域内,仿真时间为100s,暂停时间设为100s。也就是在仿真这段时间里没有移动,另外设置使用CBR流,每一条数据流每秒送出50个数据包。

在同一仿真场景中,WAODV算法在数据包送达比例、数据包平均端到端延迟时间两个性能上跟未修改的AODV协议进行比较。

2.2数据包送达比例

数据包送达比例:由CBR来源段产生的数据包传送数目与到成功到达目的地端数据包数目的比值,用来衡量路由算法对传送数据包的优劣[8,9]。

图2显示了随着时间的推移两种协议下数据包送达比例的情况。时间越久,链路上的拥塞程度越大,两种协议的数据包送达比例都会下降。但是由于MAODV采用了选择代价最小路由,在一定程度上减轻了链路拥塞,数据包送达比例会比AODV情况下有所提高,而且随着时间增长,优势趋于明显。

2.3数据包平均端到端延迟时间

数据包平均端到端延迟时间:这包含所有可能的延迟时间的总和,如发现路径的缓冲时间、MAC层的重传时间、传递时间等,用来衡量路由算法时间效率。尤其对于语音通信,延迟过大会严重影响通信质量[10]。

从图3中可以看出,随着时间的推移,两种协议下端到端延迟都会增大,但是MAODV算法端到端的延迟要比AODV协议小些。这是因为MAODV算法在找到达目的节点路径时,选择时延最小的链路进行传输,必然是要比AODV协议的时延小。

3 结语

通过对无线Ad Hoc网络路由协议的深入研究,针对AODV路由协议的不足,本文提出了一种新的WAODV路由算法。当AODV路由算法发起到目的节点的路由查找时,WAODV路由算法增加路径最小代价作为选择下一跳路由的条件,使得整个网络能够满足Wardrop均衡的条件。利用这一理论,经过一段时间的调整,网络上的时延会近似相等,达到了控制链路拥塞的目的,提高了数据包的送达比例、减小了平均端到端延时时间。仿真结果表明,WAODV路由算法的传输效率得到了很大提高。

摘要：无线Ad Hoc网络的AODV路由协议容易引起链路拥塞,进而可能导致链路中断,从而造成网络传输效率的下降。提出一种WAODV路由算法,利用Wardrop均衡理论对AODV协议进行优化,使得网络的传输效能达到最优。算法根据路径的最小代价选择路由的下一跳,从而调整网络中数据包的分配,使整个网络处于一个优化平衡状态,达到减少链路拥塞、提高网络传输效率的目的。仿真结果表明,WAODV路由算法在数据包送达比例、数据包平均端到端延迟时间方面得到了有效改善,提高了网络的传输效率。

关键词：无线Ad Hoc网络,WAODV,Wardrop均衡,仿真

参考文献

[1]陈林星,曾曦,曹毅.移动Ad Hoc网络—自组织分组无线网络技术[M].北京:电子工业出版社,2012.

[2]于宏毅,陈万寿.无线移动自组织网[M].北京:人民邮电出版社,2005.

[3]Li Jinyang,Blade Charles,Douglas S J,et al.Capacity of ad-hoc wireless network[C]//Proceedings of MOBICOM,2001.

[4]沈奔,秦军,万丽.无线Ad Hoc网络中AODV路由算法的研究与改进[J].计算机技术与发展,2011(3):150-153.

[5]黄海军.城市交通网络平衡分析—理论与实践[M].北京:人民交通出版社,1994.

[6]赵彤,郭天德,杨文国.无线传感器网络能耗均衡路由模型及算法[J].软件学报,2009(20):3023-3033.

[7]Beckmann M,Mcguire C B,Winsten C B.Studies in the Economics of Transportation[M].New Haven:Yale University Press,1955.

[8]Yuan Y X,Sun W Y.Optimization Theory and Methods[M].Beijing: Science Press,1997.

[9]吴东亚,侯朝桢,侯紫峰.Muhipath Source Self Repair Routing Algorithm for Mobile Ad Hoc Networks[J].Journal of Beijing Institute of Technology,2005(2):5 -6.

[10]黄江,朱守业.移动Ad Hoc网络AODV路由协议改进[J].火力与指挥控制,2009(3):19-20.

无线Adhoc 第5篇

1.1 Ad Hoc网络概述

Ad Hoc网络最初应用于军事领域, 它的研究起源于战场环境下分组无线网数据通信项目, 该项目由DARPA资助, 其后, 又在1983年和1994年进行了抗毁可适应网络SURAN (Survivable Adaptive Network) 和全球移动信息系统Glo Mo (Global Information System) 项目的研究。由于无线通信和终端技术的不断发展, Ad Hoc网络在民用环境下也得到了发展, 如需要在没有有线基础设施的地区进行临时通信时, 可以很方便地通过搭建Ad Hoc网络实现。

Ad Hoc网络即自组网 (Self Organized Network) , 是一种特殊的对等式网络, 它使用无线通信技术, 由一组带有无线收发装置的移动节点组成, 网络中所有节点的地位平等, 无需设置任何的中心控制节点, 网络中主机同时还是路由器, 担负着寻找路由和转发报文的工作。在Ad Hoc网络中, 每个主机的通信范围有限, 因此路由一般都由多跳组成, 数据通过多个主机的转发才能到达目的地, 也被称为多跳无线网 (Multihop Wireless Network) 、无固定设施的网络 (Infrastructureless Network) , 具有无中心、自组织、多跳路由、动态拓扑等特点。

Ad Hoc网络通过移动节点间的相互协作来进行网络互联, 可以看作是移动通信和计算机网络的交叉, 而不依赖于任何固定的网络基础设施, 每个移动节点都具有报文转发能力, 并且使用计算机网络的分组交换机制, 而不是电路交换机制。当一个节点需要和另一个节点通信时, 它或使用直接的无线链路, 或通过到目的节点的多个中间节点的转发, 即经过多跳路由, 从而实现网络的自动组织和运行。Ad Hoc网络路由协议通常被分为两类:先验式 (Proactive) 和反应式 (Reactive) 。先验式协议通过周期性路由控制信息的交换, 每个节点始终维护到网络中所有节点的路由, 如DSDV和OLSR;反应式协议在节点需要时才发现路由, 并且仅维护活动路由, 如AODV和DSR。在网络中通信的主机一般是便携式计算机、个人数字助理 (PDA) 等移动终端设备。Ad Hoc网络不同于目前因特网环境中的移动IP网络。在移动IP网络中, 移动主机可以通过固定有线网络、无线链路和拨号线路等方式接入网络, 而在Ad Hoc网络中只存在无线链路一种连接方式。在移动IP网络中, 移动主机通过相邻的基站等有线设施的支持才能通信, 在基站和基站 (代理和代理) 之间均为有线网络, 仍然使用因特网的传统路由协议。而Ad Hoc网络没有这些设施的支持。此外, 在移动IP网络中移动主机不具备路由功能, 只是一个普通的通信终端。当移动主机从一个区移动到另一个区时并不改变网络拓扑结构, 而Ad Hoc网络中移动主机的移动将会导致拓扑结构的改变。

1.2 移动IP概述

移动IP是用于移动主机移动性管理的一组网络层协议, 其目的是使移动中的主机在保持原IP地址不变的条件下能保持通信, 类似于移动电话系统中的漫游, 可适用于各种不同类型的移动通信系统。它定义了四个功能实体:移动主机 (Mobile Host) 、通信主机 (Corresponding Host) 、家乡代理 (Home Agent) 和外地代理 (Foreign Agent) 。移动主机是一个能在子网间移动的主机, 当Internet上的通信主机向移动主机发送IP数据包时, 数据包将交付到移动主机的家乡网络, 若移动主机离开了家乡网络, 数据包将通过隧道 (Tunnel) 机制交付到外地网络, 外地代理负责拆封数据包并转发到移动主机。

1.3 Ad Hoc网络的特点

在Ad Hoc网络中, 移动主机可以在网中随意移动。主机的移动会导致主机之间的链路增加或消失, 主机之间的关系不断发生变化。在自组网中, 主机可能同时还是路由器, 因此, 移动会使网络拓扑结构不断发生变化, 而且变化的方式和速度都是不可预测的。对于常规网络而言, 网络拓扑结构则相对较为稳定。

1.3.1 网络的独立性

Ad Hoc网络相对常规通信网络而言, 最大的区别就是可以在任何时刻、任何地点不需要硬件基础网络设施的支持, 快速构建起一个移动通信网络。它的建立不依赖于现有的网络通信设施, 具有一定的独立性。Ad Hoc网络的这种特点很适合灾难救助、偏远地区通信等应用。

1.3.2 动态变化的网络拓扑结构

1.3.3 有限的无线通信带宽

在Ad Hoc网络中没有有线基础设施的支持, 因此, 主机之间的通信均通过无线传输来完成。由于无线信道本身的物理特性, 它提供的网络带宽相对有线信道要低得多。除此以外, 考虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰等多种因素, 移动终端可得到的实际带宽远远小于理论中的最大带宽值。

1.3.4 有限的主机能源

在Ad Hoc网络中, 主机均是一些移动设备, 如PDA、便携计算机或掌上电脑。由于主机可能处在不停的移动状态下, 主机的能源主要由电池提供, 因此Ad Hoc网络有能源有限的特点。

1.3.5 网络的分布式特性

在Ad Hoc网络中没有中心控制节点, 主机通过分布式协议互联。一旦网络的某个或某些节点发生故障, 其余的节点仍然能够正常工作。

1.3.6 生存周期短

Ad Hoc网络主要用于临时的通信需求, 相对与有线网络, 它的生存时间一般比较短。

1.3.7 有限的物理安全

移动网络通常比固定网络更容易受到物理安全攻击, 易于遭受窃听、欺骗和拒绝服务等攻击。现有的链路安全技术有些已应用于无线网络中来减小安全攻击。不过Ad Hoc网络的分布式特性相对于集中式的网络具有一定的抗毁性。

1.4 Ad Hoc网络的应用需求

Ad Hoc网络的应用范围很广, 总体上来说, 它可以用于以下场合:a) 没有有线通信设施的地方, 如没有建立硬件通信设施或有线通信设施遭受破坏;b) 需要分布式特性的网络通信环境;c) 现有有线通信设施不足, 需要临时快速建立一个通信网络的环境;d) 作为生存性较强的后备网络。

2. Ad Hoc和移动IP集成原因

Ad Hoc网络有很强的独立性, 但它所使用的路由算法大多数只适用于单个Ad Hoc网络, 很少涉及如何实现Ad Hoc网络与Internet的互联, 这些因素使它难以大范围与互联网通信。

移动IP使节点在不同的子网间切换时仍可保持正在进行的通信, 它提供了一种IP路由机制, 使移动节点能够以一个永久的IP地址连接到任何子网中, 它的扩展性使其能在整个Internet上应用。

为了达到Ad Hoc网络中的移动主机可以在不同的Ad Hoc网络间移动和随时接入互联网, 我们利用移动IP的可扩展及可在不同网络中漫游的特性, 从而实现Ad Hoc网络与Internet的互联。

3. Ad Hoc和移动IP结合的体系结构及工作过程

近几年, 许多国内外学者从事Ad Hoc网络和移动IP集成方面的研究, 并且提出了不同的解决方案。在此我们以图1所示的简单结构模型为例来探讨Ad Hoc和移动IP的结合思想及工作过程。

3.1 体系结构

在图1所描述的体系结构中, 无线移动网络由多个Ad Hoc网组成, 每个Ad Hoc网相当于一个子网, 它们都通过相应的网关 (即基站) 接入Internet, 每个网关需配置两块网卡:一块连接有线网络, 另一块连接无线网络, 其职责是在Ad Hoc网和Internet之间转发/中继数据包;为支持移动IP, 每一个网关还同时扮演外地代理的角色, 周期性地广播代理公告消息, 同时运行Ad Hoc路由协议、移动IP协议和Internet路由协议, 保证Ad Hoc网内的节点利用自组网路由协议来创建和维持路由, 并通过移动IP实现移动节点的移动管理。由于移动节点与网关之间可以进行多跳通信, 在不添加任何固定设施的情况下, 只要有一个支持移动IP的网关节点能够访问Internet, 网络就能有效地访问Internet。

3.2 工作过程

在上述无线移动网络中, 通过移动IP实现Ad Hoc接入Internet有几个主要过程。

(1) 网关发现。网关发现是Ad Hoc与Internet连接的一个关键技术, 通过合适的网关发现方法可以同时解决地址分配及路由等问题。当Ad Hoc网的移动节点要向其它节点发送数据包时, 首先要判断目的节点是否在本网内, 这时节点根据路由协议发起路由查找, 如果找到就判定目的节点在网内, 并使用Ad Hoc网络路由协议进行通信, 如果找不到就判断目的节点在Internet中, 就需要通过网关进行外部访问。通常, 网关节点通过网关通告算法周期性地在本Ad Hoc网内发布网关信息通告, 以表明它是当前可用的Internet接入网关, 当Ad Hoc网中的节点想要发送数据到Internet节点时, 它首先必须将数据发送到网关。对于Ad Hoc网节点, 每当它收到 (以直接或间接方式) 一个网关通告消息之后, 就会立即记录下该网关的信息 (包括其IP地址、路由信息以及该信息的有效期 (TTL) 等) , 当需要同本Ad Hoc之外的节点通信时, 便向选择的网关发送接入请求消息, 网关决定是否接受该请求, 并发送Accept/Reject消息通知该节点。为了避免因多个Ad Hoc网重叠而造成网关的服务范围变得不清晰, 可设置一个参数N来限定网关的服务范围, 任何在网关N跳范围内的移动主机可获得网关的服务, 如图1中网关G1的服务范围 (椭圆范围内区域) N=3, 主机A虽然和自组网1相连, 但它不在网关G1的服务范围内;若一台主机处在多个网关的服务范围内, 它可以选择距离自己最近 (跳数最小) 的网关, 图1中B、C同时位于自组网2和自组网3中, 而B选择网关G2, C选择网关G3。

(2) 协议转换。网关同时运行Ad Hoc路由协议、移动IP协议和Internet路由协议, 为了确保采用不同的协议Ad Hoc与Internet进行通信, 网关实现了Ad Hoc协议和Internet中的TCP/IP协议的转换。

(3) 地址转换。移动节点将数据包发送到网关节点后, 网关对发往目的节点的数据包进行封装, 通过网络地址转换 (NAT) 将数据包的源地址改为自己的地址, 并将外层报头的目的IP地址设为外地代理的IP地址, 从而将数据包转换为由本地网关发往外地代理 (即目标节点的家乡代理) , 在网关节点上, 维持一个网络地址转换 (NAT) 表用来记录通过本网关访问Internet的节点, 以及它们各自的网络地址的映射关系。

(4) 路由选择。在此体系结构中, 路由选择分自组网内路由选择和网间路由选择。自组网内节点之间通信时 (图1中D到E的传输) , 路由选择采用自组网路由协议, 如1.1节中AODV路由协议。如果通信的节点中有一个在Internet中, 通信节点就通过Ad Hoc路由协议获得网关的路由, 将数据发往网关。一旦数据包经过网关进入Internet, 则依据标准IP路由协议进行网间路由, 将数据包发送到外地代理, 外地代理查询移动节点注册表, 将数据转发往目标移动节点 (如图1中F到E的传输, 即数据包在转发过程中, 从F到G2使用AODV, 从G2通过Internet到G3使用标准IP路由, 从G3到E再次使用AODV) , 若外地代理在移动节点注册表中没有直接查询到目标移动节点, 则要进行外地代理切换或网关切换。

(5) 切换。当目标主机从一个自组网移动进入了另一个自组网, 数据包转发到其代理后, 由移动IP负责在自组网间转发数据包, 实现原代理到新代理的切换, 原代理对数据进行封装, 采用移动IP路由协议, 利用隧道机制将数据包转发至新代理, 最后新代理将数据包直接发送到目的移动节点。

3.3 性能分析

总结起来该体系结构具有几个特点。

(1) Ad Hoc网内部的通讯可以直接进行。设想在一个校园内部, 如果用户的手机之间可以直接或以多跳的方式通信, 而不经过公用的基站, 就可以省去通过公用基站的费用。

(2) 增强了无线接入网的可靠性和扩展性。移动节点可能移动到基站覆盖范围以外, 也可能因某些无线传输现象 (如衰减、多路径干扰等) 或是障碍物等因素而无法直接访问基站, 这时节点仍可通过多跳路由的方式间接地访问基站。

(3) 微观移动对家乡代理来说是透明的。当移动节点在Ad Hoc网内移动时, 从网关到移动节点的路由是自动改变的, 家乡代理无须更新位置信息。

4. Ad Hoc网络的应用

Ad Hoc网络技术的研究最初是为了满足军事应用的需要, 军队通信系统需要具有抗毁性、自组性和机动性。在战争中, 通信系统很容易受到敌方的攻击, 因此, 需要通信系统能够抵御一定程度的攻击。若采用集中式的通信系统, 一旦通信中心受到破坏, 将导致整个系统的瘫痪。分布式的系统可以保证部分通信节点或链路断开时, 其余部分还能继续工作。在战争中, 战场很难保证有可靠的有线通信设施, 因此, 通过通信节点自己组合, 组成一个通信系统是非常有必要的。此外, 机动性是部队战斗力的重要部分, 这要求通信系统能够根据战事需求快速组建和拆除。

Ad Hoc网络满足了军事通信系统的这些需求。Ad Hoc网络采用分布式技术, 没有中心控制节点的管理。当网络中某些节点或链路发生故障, 其他节点还可以通过相关技术继续通信。Ad Hoc网络由移动节点自己自由组合, 不依赖于有线设备, 因此, 具有较强的自组性, 很适合战场的恶劣通信环境。Ad Hoc网络建立简单、具有很高的机动性。目前, 一些发达国家为作战人员配备了尖端的个人通信系统, 在恶劣的战场环境中, 很难通过有线通信机制或移动IP机制来完成通信任务, 但可以通过Ad Hoc网络来实现。因此, 研究Ad Hoc网络对军队通信系统的发展具有重要的应用价值和长远意义。

近年来, Ad Hoc网络的研究在民用和商业领域也受到了重视。在民用领域, Ad Hoc网络可以用于灾难救助。在发生洪水、地震后, 有线通信设施很可能因遭受破坏而无法正常通信, 通过Ad Hoc网络可以快速地建立应急通信网络, 保证救援工作的顺利进行, 完成紧急通信需求任务。Ad Hoc网络可以用于偏远或不发达地区通信。在这些地区, 由于造价、地理环境等原因往往没有有线通信设施, Ad Hoc网络可以解决这些环境中的通信问题。Ad Hoc网络还可以用于临时的通信需求, 如商务会议中需要参会人员之间互相通信交流, 在现有的有线通信系统不能满足通信需求的情况下, 可以通过Ad Hoc网络来完成通信任务。

5. 与其他移动通信系统的比较

5.1 蜂窝系统

蜂窝系统是覆盖范围最广的陆地公用移动通信系统。在蜂窝系统中, 覆盖区域一般被划分为类似蜂窝的多个小区。每个小区内设置固定的基站, 为用户提供接入和信息转发服务。移动用户之间以及移动用户和非移动用户之间的通信均需通过基站进行。基站则一般通过有线线路连接到主要由交换机构成的骨干交换网络。蜂窝系统是一种有连接网络, 一旦一个信道被分配给某个用户, 通常此信道可一直被此用户使用。蜂窝系统一般用于语音通信。

5.2 集群系统

集群系统与蜂窝系统类似, 也是一种有连接的网络, 一般属于专用网络, 规模不大, 主要为移动用户提供语音通信。

5.3 卫星通信系统

卫星通信系统的通信范围最广, 可以为全球每个角落的用户提供通信服务。在此系统中, 卫星起着与基站类似的功能。卫星通信系统按卫星所处位置可分为静止轨道、中轨道和低轨道3种。卫星通信系统存在成本高、传输延时大、传输带宽有限等不足。

上述移动通信系统都需要有线网络通信基础设施的支持, 如基站、交换机、卫星等。这些设施的建立和运转需要大量的人力和物力, 因此成本比较高, 同时建设的周期也长。Ad Hoc网络不需要基站的支持, 由主机自己组网, 因此, 网络建立的成本低, 同时时间短, 一般只要几秒钟或几分钟。上述通信系统中, 移动终端之间并不直接通信, 并且移动终端只具备收发功能, 不具备转发功能。而Ad Hoc网络由移动主机构成, 移动主机之间可以直接通信, 而移动主机不仅收发数据, 同时还转发数据。此外目前的移动通信系统主要为用户提供语音通信功能, 通常采用电路交换, 拓扑结构比较稳定。而Ad Hoc网络使用分组转发技术, 主要为用户提供数据通信服务, 拓扑结构易于变化。

6. 结束语

目前, 随着移动通信技术逐渐普及, 各种便携式终端大量涌现, 底层通信技术层出不穷, 越来越多的移动应用正逐渐被人们所发现和熟悉, 这都极大地推进了无线移动网络的应用和推广。通过移动IP和Ad Hoc网络的结合, 在不添加任何固定设施的情况下, 传统的接入点可以直接利用Ad Hoc网的灵活性并扩展它们的覆盖范围, 从而提高了无线移动网络的工作效率和服务质量, 在家庭、办公、工业、商业、医疗、军事等多种领域应用前景广阔。

无线Adhoc 第6篇

关键词：Ad Hoc,传输容量,最优半径,保护区域

无线Ad Hoc网络的网络容量是一个没有办法解决的长期存在的问题,人们在相当长的一段时间中甚至无法给出一种可以用来衡量无线Ad Hoc网络容量的方法。文献[1]把传输距离引入了无线Ad Hoc网络容量的定义中,定义了传送容量( Transport capacity) 这一参量,为了进行更加细致的研究,研究者们开始使用随机几何理论［2］进行网络建模,并在新的网络模型基础上提出了用来衡量无线Ad Hoc网络容量的一种新参量,这就是空间进度密度［3］( Spatial Density of Progress,SDP) ,SDP被定义为无线Ad Hoc网络中单位面积上的成功通信数量与单跳传输距离的乘积。文献[3]定义了一个指向目标接收机( Receiver,RX) 的半圆形中继RX选择区域,在此基础上研究了SDP与功率控制策略之间的关系。文献[4]对中继RX选择区域做了进一步的定义,定义中继RX选择区域为指向密度RX的扇形区域,并推导了最优传输半径。

无线Ad Hoc网络中,有多个发送机( Transmitter,TX) 使用同一频率在同一时隙发送数据,这些TX之间会产生对彼此的干扰［5］。无线Ad Hoc网络的网络容量由网络中干扰信号的强弱水平决定,要想提高SDP,关键就是如何抑制网络中的干扰信号强度。研究无线Ad Hoc网络容量的现有文献主要集中于功率控制策略［6 － 7］、多天线［8］、重叠网络［9］和波束成形［10］等,而对如何抑制网络中的干扰功率［11 － 12］的研究则极少。

本文在无线Ad Hoc网络中任意RX周围设置一个保护区域,在此保护区域内不允许存在任何发送干扰信号的TX,如果在保护区域内有干扰TX,则此干扰TX会停止发送数据。

1 系统模型及参数定义

系统模型如图1 所示。

无线Ad Hoc网络分布在二维平面中,网络规模没有限制,同一时隙使用相同频率发送数据的TX的位置构成参数为 λ0的泊松点过程［2］( Poisson Point Process,PPP) ( Π0) ,在以a为半径的圆形区域内存在k个TX的概率为

定义任意RX的保护区域为以b为半径以该RX为圆心的圆形区域,位于此区域内的所有干扰TX都需要停止发送数据。出于简化分析的目的,定义网络中任意一个RX的保护区域不会与另一个RX的保护区域相交,保护区域的存在会使部分TX停止发送数据,则最终发送数据的TX密度为

这部分的TX可以重新构成一个参数为λ的PPP(Π)。

定义无线Ad Hoc网络中的每一个TX都有一个与之相对应的RX,使用编号i来标记由RXi和TX i构成的通信对。在坐标原点处放置一个参考RX,由参考RX和对应的TX构成的通信对的编号记为0( 0  Π ) 。由PPP的平稳性可知,对RX 0 的中断概率进行统计特性研究得到的结果与无线Ad Hoc网络中任意RXi ( i ≠ 0 ) 处都是一样的。RX 0 处接收到的任意TXi ( i ≠ 0 ) 发送的信号都是被干扰信号,且噪声功率为 η 。

定义目的RX距离源TX足够远,源TX需要经过多次中继后才能把数据传输到目的RX处,为了保证每一次中继后数据能够更加靠近目的RX,中继选择区域的定义如下: 如图1 所示,在任意一次中继过程中,传输数据的TX位于图1 中A点,目的RX位于B点,中继RX选择区域是一个由最大传输距离Rm和角度 θ ( 0 < θ < π/2 ) 确定的指向目的RX的扇形区域,如图1 所示,∠HAB = θ ,AH = Rm,AB为扇形区域的中心线。

使用文章[5]的经典无线Ad Hoc网络模型,本文的传输模型定义如下: TX i的发送功率记为Pi,TX i与RX 0 之间的功率衰落系数记为Hi0,路径衰减系数记为 α( α > 2) ,TX i与RX 0 之间的距离记为Xi,可以把在RX 0 处的总干扰信号功率表示为。出于简化分析难度的目的,定义TX i和RX i之间的距离是一个固定值R,并且所有TX都使用相同的发送功率Pt来发送数据。定义信道衰落是瑞利衰落,则功率衰落系数Hi0将服从指数分布,概率密度公式(Probability of Density Function,PDF)可以表示为

式中:τ为指数分布的参数。虽然一次中继的距离为R,但是信号在中继后靠近目的RX的距离并不是R,而是比R要小。本文定义有效传输距离为信号经过一次中继后靠近目的RX的距离。如图1所示,点C为中继RX,∠CAB=α,因此可以用Rcosø(-θ<ø<θ)来表示有效传输距离的大小。

如果RX 0处的信噪比(Signal-to-Interference Ratio,SIR)不低于预设的门限值β,那么就可以认为RX 0成功地接收了信号,即网络的中断概率[5]可以表示为

无线Ad Hoc网络的SDP无法用传统的方式去定义,本文使用文献[4]中广泛为研究者们所认可的SDP定义,即SDP等于网络中单位面积上的成功通信数量与单跳有效传输距离的乘积。定义无线Ad Hoc网络的最大中断概率为ε,则对q(λ)=ε进行求解可以得到对应于最大中断概率ε时的TX最大密度λε,此时无线Ad Hoc网络的通信成功概率可以表示为1-ε,则SDP可以表示为[5]

式中:E(*)表示对随机变量求期望值。

2无线Ad Hoc网络SDP的表达式

网络的中断概率即式(4)可被重写为

使用功率衰减因子Hij的PDF式( 3) 、式( 6) 可以变为

式中:是干扰信号IΠ的PDF的拉普拉斯变换。

下面部分将首先对进行推导。由于使用了保护区域,则以RX 0 为圆心以b为半径的圆形区域内不存在任何发送干扰信号的TX。当只有以RX 0 为圆心以b为内半径且以a ( a > b ) 为外半径的环形区域内存在TX时,用表示此时RX 0 处IΠ的PDF的拉普拉斯变换,如果只有K个干扰TX存在环形区域内,则

由于干扰节点随机分布在环形区域内,RX 0 与干扰节点TX i之间距离Xi的PDF可以表示为

使用式(10) ,式( 9) 可以变为

使用式( 1) 和式( 11) 可以得到

当a → ∞ 时,以RX 0 为圆心以b为内半径且以a ( a > b )为外半径的环形区域将覆盖整个网络范围,此时可以得到。把a → ∞ 代入式( 12) 中可以得到

使用公式(3) ,可以得到

把公式( 14) 代入公式( 13) 可以得到

最后,把式( 15) 代入式( 8) ,可以得到无线Ad Hoc网络中断概率的表达式为

其中,

其中,Ψ( * ) 表示超几何函数Hypergeometric2F1。一般情况下,式( 17) 中的积分无法得到闭合表达式,但是当路径衰减系数 α = 4 时,式( 17) 变为

把式( 18) 代入式( 16) 可以得到

令q( λ) = ε ,并求解可以得到

由于任意TX在它的中继RX选择区域随机选择中继RX,图1 中继RX角度ø的PDF可以表示为

使用公式( 21) 可以得到

把式( 22) 和( 20) 代入SDP的定义式( 5) 可以得到

式( 23) 是路径衰减系数 α = 4 时的SDP表达式,下面对一般情况下的SDP表达式进行推导。当路径衰减系数 α ≠ 4时,可以对式( 17) 求近似解。对式( 17) 进行变化可以得到

把式( 24) 代入( 16) 并求解可以得到

最后,把式( 25) 和( 22) 代入SDP的定义式( 5) 可以得到

3 无线Ad Hoc网络SDP的上下界

在一般情况下,由于式( 17) 无法求得闭合表达式,因此也就无法得到中断概率和SDP的闭合表达式,下面将对中断概率和SDP的上下界进行研究。

首先求导中断概率的上界和SDP的下界。利用式( 17)可以很容易地得到

把式( 27) 代入式( 16) ,可以得到中断概率的上界为

令q(λ)=ε,由于,则利用式(28)可以得到

最后把式( 29) 和( 22) 代入式( 5) 可以得到SDP下界为

下面部分开始求导中断概率的下界和SDP的上界。首先对主要干扰区域进行定义,主要干扰区域被定义为只要有一个发送干扰信号的TX存在于此区域就会导致RX 0 处接收到的信噪比低于门限值,即会使RX 0 接收信号失败。定义主要干扰区域中的TX集合为 Πdom,则可以得到

使用式( 31) 并结合中断概率的定义,中断概率可以表示为

式( 32) 说明任意一个TX存在主要干扰区域的概率是中断概率的下界。根据文献[5]对于传输容量上下界的推导结果,中断概率的下界可以表示为

式中: Sdom是主要干扰区域的面积。令Hi0/ H00= Y ,使用功率衰减因子Hi0的PDF公式( 3) ,Y的PDF函数可以表示为

且从公式( 32) 可以得到

则使用式( 31) 和( 35) 可以得到

当 βRαb－ α+ βRαηPt－1< 1 时,式( 36) 可以变为

当 βRαb－ α+ βRαηPt－1≥ 1 时,式( 36) 可以变为

对于式( 38) 的第1 个积分部分,可以使用与式( 37) 相同的证明方法得到

对于式( 38) 中的第2 个积分进行求解可以得到

把式( 39) 和式( 40) 代入式( 38) 可以得到

Sdom的下界公式较为复杂,为了节省篇幅,下面只求βRαb－ α+ βRαηPt－1< 1 时的中断概率上界表达式和SDP下界表达式。把式( 37) 代入式( 33) 可以得到中断概率下界为

利用式( 42) 可以得到

最后,把式( 43) 和式( 22) 代入式( 5) 可以得到SDP上界为

4 数值仿真结果分析

为了尽可能地降低噪声对研究结果的影响,定义Pt/ η =60 d B ,如果没有额外的说明,本文的其他仿真参数设置如下

图2 给出了不同保护区域半径时的中断概率与TX密度的曲线图。如图2 所示,中断概率随着TX密度 λ 的增加而增大,这是由于TX密度的增大意味着网络中的干扰信号强度增大,导致RX处的接收SIR降低; 当TX密度 λ 相同时,有保护区域时的中断概率比没有保护区域时的中断概率小,说明保护区域的存在能够抑制网络中的干扰信号强度,降低中断概率; 并且可以看到,当TX密度 λ 不变时,保护区域半径越大时的中断概率越小,说明保护区域越大,对干扰信号的抑制作用越强。

图3 给出了SDP的近似值和仿真值与最大中断概率 ε 关系的曲线图。从图中可以看到,随着最大中断概率 ε 的增大,SDP先是不断增大,当到达某一临界值后,SDP开始不断变小。这是因为,最大中断概率 ε 增大时会使网络的最大TX密度迅速增大; 当最大中断概率 ε 很小时,由定义式( 5) 可知,SDP主要由最大TX密度决定,所以此时SDP随着最大中断概率 ε 的增大而增大; 但是当最大中断概率 ε 趋近于1 时,成功通信概率( 1 - ε ) 趋近于0,SDP主要由成功通信概率决定,所以此时SDP随着最大中断概率 ε 的增大而减小。另外,由图3 可以看到,仿真值略比近似值小,且近似值与仿真值的变化趋势基本一致,说明在一般情况下可以通过研究近似值表达式( 26) 来研究此时网络中的SDP变换情况,特别是最大中断概率 ε 趋近于0 时,此时的仿真值与近似值几乎没有什么区别。

图4 给出了中断概率的上下界和仿真值与TX密度 λ 的曲线图。从图中可以看到,中断概率的仿真值介于其上下界之间,且仿真值更加靠近下界,说明本文推导的中断概率上下界的公式是合理的。另外可以看到,当TX密度 λ 趋于0( 较小) 或较大时,中断概率仿真值基本与上下界重合,上下界的误差较小。

5 结束语

无线Adhoc 第7篇

关键词：节能,异步,自适应,Quorum

1 Ad hoc网络及其传统节能模式

Ad hoc网络是一种没有基础设施,仅凭任意个终端就可以随时随地组建的新型网络,网络中各个节点均可任意移动,并可作为路由为其他节点转发信息,目前已被广泛的用于各种军事,抢险,应急等场合,这样一种网络同时也意味着对于每一个节点来说,哪怕是其中一两个节点的能量耗尽也势必影响整个网络的性能(如路由选择),且能量已不能从外界进行补充,都只能是依靠最初的能量储备来维持,所以节能便成了唯一的出路。

现在在移动无线Ad hoc网络(MANET)中比较流行的是IEEE 802.11的节能模式。这是一种同步的模式,在这种方式下,对于每一个节点都定义了两种能量状态:活跃和节能(PS)。把每一个节点的时间轴(Time Axis)划分为若干个相等部分,每一个部分我们称之为一个信标间隔(Beacon Interval,BI),在所有的节点都是被假设是完全连接和同步的情况下,又进一步把每一个BI分成若干个部分(如图1所示),包括广播传输指示ATIM(Ad hoc Tracffic Indication Map)窗,数据传输窗(Data Window,DW)和一个信标窗(Beacon Window,BW),它们的作用及具体关系如下:

BW:当一个节点处于PS模式的时候,这个节点唯一所要做的便是监听或者竞争发出周期性的beacon信号,从而来保持对外界的联系,而BW就是用于节点对于发送类似信号的时间段。

ATIM:对于有数据想要发出的节点来说,首先必须要通过竞争给正处于节能模式的目的端发出一个通知来让他恢复活跃模式,ATIM就是用于实现此项功能的时间段。

DW:正式进行数据传送的时间段。

具体流程为:

所有节点都周期性地在ATIM窗内保持活跃状态。ATIM窗通常占BI的20%。在ATIM开始的BW内,每个节点通过竞争发送信标(Beacon)。为了减少碰撞,每个节点在尝试发送Beacon前有0~2(CWmin-1)个时隙的随机规避时间。发送完Beacon后,如果缓冲区有数据要发送,则通过竞争发送A-TIM帧,收到ATIM帧的节点必须回复ATIM应答帧完成握手,并在ATIM窗结束后仍保持活跃,进行数据帧的发送和接收。如果在ATIM窗没有完成握手,则进入休眠模式,等待下一个BI的到来,如图2所示。

以上便是IEEE 802.11现有的节能机制,这种传统的基于同步周期休眠/唤醒的节能机制在MANET环境下遇到了很多困难,大规模、高密度、多跳、移动性都是MANET网络标志环境下,时钟同步的开销很大,完全依靠时钟来同步是很不现实的,势必引发人们对异步方式的思考,文献[1]的作者首次应用分布式系统中的Quorum概念,开启了异步节能的新领域,经过几年的发展,基于Quorum机制的节能算法在MANET下取得了良好的效果。

2 基于Quorum系统的异步节能机制

在一个多跳的网络环境下,在考虑节能策略的时候,有两个问题是不能忽略的,即唤醒预测和邻居发现,Quorum系统的运用主要是解决后者,即两个有着任意时间差的节点,如果保证能被互相发现。

2.1 异步节能算法回顾

到目前为止,已经存在的大概有三种异步的节能算法,包括DAI(Dominating Awake Internval)、PFAI(Periodically Fully Awake Interval)以及QB(Quorum Based)。其中DAI的核心思想是让节点保持足够长的活跃时间,不难发现,只要这个时间大于整个BI长度的一半,不管两个节点的时钟相差多少,都能保证邻居之间可以互相发现。缺点在于对能量的利用率仍然不高。PFAI的核心思想在于把BI分别定义成两种不同的时隙,分别为“低能耗”和“完全能耗”,被定义为“完全能耗”的BI只是周期性的出现,剩下都为“低能耗”的BI。这种算法可以保证在一个周期T里,不管两个节点的时间差如何,其中一个节点的BW可以和邻居节点的“完全能耗”BI有交叠的部分,从而保证可以发现对方。而这种方式的问题在于对于一个新出现的节点的发现时间会根据所定义的周期长度T来确定,如果T值偏大就大大影响了新节点的响应时间,所以一般来说这样的方式适合移动性不强的环境。关于这两种算法更详细的信息,请参见文献[1]。

2.2 基于Quorum系统的异步节能

Quorum是一种分布式的系统,直观的讲,该系统就是一系列数字的集合中按照一定的规则选出的一部分所构成的一个团体。举一个列子来说,在一个44的方格当中,从左到右,从上到下,依次填充0到15这16个整数,从这个四行四列的方格中任意取出一行和一列组成一个整体,那么这样的一个整体就称为一个“Quorum”,如图3、图4所示。

从图3中我们可以看出,粗体元素所表的一个集合就可以构成一个“Quorum”,这样的一个集合和异步的节能方式是怎样联系起来的呢?我们不妨假设有两个这样的方格,每个方格中都有从0到15共16个整数,并且按照相同的方式排列,然后按上面提到的方法分别提取一个“Quorum”,即将图3中的粗体元素在和图4中的粗体元素分别提取出来。这么便构成了两个集合,不妨令U1={0,1,2,3,4,6,10,14}U2={3,7,8,9,10,11,15},不难发现,这两个集合中有着相同的元素,那么我们现在可以考虑将一个节点的BI等分为16份,从左到右依次标记0到15,其中集合U1中的元素为粗体,另一个节点类似处理,如图5所示。

那么在对应节点的时间轴上,粗斜体的部分我们称之为“Quorum间隔”,对应方格中剩下的元素称之为“Non quorum间隔”,如图6所示。

至此,我们稍加分析就能看出,不管两个节点之间的时间差如何变化,在这个16连续的时隙中,其中一个PS节点总是会有两个或更多的BW被另一个PS节点的活跃期所覆盖,从而解决了邻居发现的问题,更为一般的情况,即在一个nn方格中顺序的排列整数,构成一个n连续的时隙同样是可以满足的。

该算法的优势是很明显的,一个PS节点在整个的BI中,仅仅要发送1/n的信标,根据文献[2]提出的节点能量消耗分配来看,发送信号所耗能量是最大的,这个算法无疑能减少很多不必要的信标发送,从而节省能量。

2.3 满足QP S问题的Quorum系统

上一节提到的Quorum系统仅是很多Quorum系统的其中一种,我们可以给它一个更为详细的名字:“Grid Quorum”。一个值得关注的问题是:是不是所有的“Quorum”集合都能够解决异步机制中的节能问题,文献[]给出了证明,答案是否定的,并且进一步给出了“Quorum”集合能够成为符合节能机制的条件,我们把这个问题称为“QPS”(Quorum-based PS),并给出数学定义。

定义一:给定一个无限集合U={0,1,2,,n-1},集合“Quorum System Q”为其非空子集的集合,且满足这样的交集特征:AG,H∈Q:G∩H≠空集

定义二:给出一个非负整数i和一个Quorum H(其中H为Q的部分集),定义rotate(H,i)={(j+i)mod n/j∈H}。

定义三:如果一个Qquorum System Q,具有如下特征,我们称之为其具有旋转闭合性。AG,H∈Q,i∈{0,1,,n-1}:G∩rotate(H,i)≠空集

任何满足旋转闭合特性的集合Q都可以用于解决QPS问题,文献[2]给出了详细的证明过程。上节中提到的Grid Quorum是满足这样的定义的,因此它可以作为节能算法的基本模型,此外也存在其他符合旋转闭合特性的Quorum系统,如Torus Quorum系统,Cyclic Qquorum系统,以及Finite Project平台。

3 自适应Quorum系统

3.1 非自适应Quorum系统问题陈述

在以上提到的Quorum系统中,每一个Quorum的大小都是固定的,即在一个BI中处于活跃期的间隔的个数始终是相同的,我们分析它在能量方面的不足之处,第一个方面是整个网络电量的平衡问题,也就是网络的存活时间。每个节点耗电的情况不尽相同,我们所应该避免的情况应该是某一个或某几个节点的电量彻底耗尽,而失去工作能力的可能性,从而保证整个网络的工作时间,这就需要我们根据每个节点的耗电情况进行相应的调节;第二个方面是固定大小的Quorum系统不能综合考虑节点移动性和对邻居节点的发现能力,在一个BI中,如果“Quorum间隔”所占比例较大,则保证了对邻居节点的敏感性,而降低了对能量的利用率,相反,如果“Non-quorum间隔”所占比例较大,则是在用牺牲敏感性的代价获得了较长的续航能力。

3.2 现有的自适应Quorum系统

在节能机制的研究过程中,如果说同步的节能机制是第一阶段,异步的节能机制为第二阶段,那么建立在异步节能机制上的自适应Quorum系统就是第三个阶段了,而且正在成为研究的热点,文献[2]提出的基于Torus Quorum系统的e-torus系统,文献[3]提出的基于Cyclic Quorum系统的AAPM系统都可以归类为自适应系统,虽然考虑的角度不尽相同,但都在一定程度上体现了自适应的基本特征,详细信息请参考给出的文献资料。

4 本文工作

本文的主要贡献在于提出一种叫做“Dgrid”的自适应节能策略,从这个名字不难看出,该系统是基于“Grid Quorum”系统,“D”代表了两个方面的含义:“Double”和“Difference”。概括的说,该系统是在“Grid Quorum”的基础上,将任意两个不同大小的“Grid Quorum”看作一个整体进行定义。下面将具体阐述。

前面已经仔细分析过“Grid Quorum”,我们知道“Grid Quorum”是符合旋转闭合特性的,因此它可以成为节能机制的模式,也就是说,在一个BI中,无论两个节点的时间差是多少,总能发现对方,且每个节点“Quorum”的大小是固定的。对于不同大小的“Grid Quorum”,也是符合旋转闭合特性的,因此,两个不同大小的“Grid Quorum”至少也能有两个相同的时隙来实现相互发现,也就是说,一个PS节点总是会有两个或者更多的BW被另一个PS节点的活跃期所覆盖。

不妨假设,每个节点都能够从PHY获得电量的信息,现在考虑的是如何利用已获得的电量信息来进行相应调节,从而起到尽可能提高每个节点的能量利用率和平衡整个网络电量的作用。

定义一个有限整数集合n={2,3,4,5,6,7},n表示一个Quorum的大小,这个集合实际定义了一张由不同大小的Quorum系统组成的一张表,不难看出,当n取集合中的不同值的时候,“Quorum间隔”和“Non-quorum间隔”所占比例是不一样的,下面给出一张能够清楚说明这个问题的表:

显而易见,随着Quorum大小的增加,Quorum间隔在一个BI中所占的比例是越来越小的,也就是对于一个节点来说,是越省电的,同时对邻居节点的感知能力也是在下降的。现在我们考虑在每个节点中维护一张映射表,将节点从PHY中获知的能量和相应合适的Quorum大小映射起来,使得每个节点可以在根据自己电量来调节Quorum的大小。

首先假设,在一个Ad hoc网络中,每个节点的初始电量为E=200J,根据文献中提出的关于节点各功能用电情况的说明,在下一步仿真实验中,我们将假设用1.4W,0.95W,0.805W,0.06W分别表示传送,接收,监听,睡眠所消耗的电量,且在活跃模式和睡眠模式之间的转换也要消耗0.575m J。

在一个BI中,仍然将时隙分为Quorum间隔和Non-quorum间隔两种模式,如图6所示。

可见,在Quorum中,我们仍然设计了用于传递周期性信号的BW和用于唤醒的ATIM。所不同的是,节点会根据自身节点的电量选择自己的默认状态,也就是说,根据电量来调节每一个Quorum的大小,前面我们已经说明,Quorum size越大越省电。我们把电量的剩余值分为四个等级,分别用A,B,C,D表示,对应关系如下:

这里必须要说明的一点是,本文仅仅从能量方面来考虑该表的对应关系,事实上,对n值的选取同样需要考虑其他因素,如对突发流量的应对,路由的选取等,我们将在论文的下一步工作中进行进一步详细的讨论。

每个节点都维护这样的一张对应表,便于在电量逐渐消耗的同时及时调整Quorum的大小,用牺牲单个节点的敏感性来换取网络中节点能量的平衡从而延长整个网络的生存时间。

5 仿真结果

5.1 仿真环境设置

我们采用NS2作为仿真平台,并作相应设置,对网络中节点的存活率做仿真,从而反应出整个网络的生存时间。

范围:1000m1000m

节点移动速度:2Mbit/s

节点初始电量:100J

节点数量:100

节点感应半径:250

仿真时间:350s

5.2 仿真结果及分析

BI=100ms,BW=4ms,ATIM=15ms,100个节点,且移动速率为25m/s。

从仿真结果(见图7)中可以看出,本文对“Grid Quorum”的改进基本达到了预期的效果,使得网络中节点的存活率在较长的时间里达到了100%,可以看到改进后的系统在仿真时间的后期有一个和原有系统相比较大的斜率,恰好体现了各节点电量在整个网络中的平衡。

6 结论

在这篇文章中,我们首先介绍了IEEE 802.11中采用的同步的节能方式,在分析它的不足的基础上,介绍了和总结了异步节能机制的发展现状,最后在基于Grid Quorum系统的基础上提出了一种叫做“Dgrid”的自适应节能策略,从本质上来说,这是一种以逐渐弱化单个节点的敏感性来换取能量平衡从而延长整个网络生存时间的策略,仿真结果也说明,该策略达到了我们预期的目的,在下一步的工作中,我们将综合考虑各个因素对网络电量平衡的影响,期待寻求更佳的方案。

参考文献

[1]TSENGYC,HSU C S,HSIEH T Y.Power-saving protocols for IEEE802.11-based multi-hop ad hoc networks.Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02).2002,1(6):23～27,NewYork,NY,USA.Piscataway,NJ,USA:IEEE,2002:200～209

[2]JIANGJR,TSENG Y C,HSU C S,et al.Quorum-based asynchronous power-saving protocols for IEEE802.11ad hoc networks.Mobile Networks and Applications,2005,10(1):169～181

[3]CHOUZT.Optimal adaptive power management protocols for asynchronous wireless ad hoc networks.Proceedings of Wireless Communications and Networking Conference(WCNC'07),Mar11-15,2007,Kowloon,China.NewYork,NY,USA:IEEE,2007:61～65

无线Adhoc 第8篇

1 基于多信道的NM协议功能需求

传统的无线自组网吞吐量不高,尤其随着网络规模的增大,节点吞吐量下降。近年来通过在MAC层使用多个信道,无线自组网的吞吐量得到显著提高[4]。本文研究的无线Ad Hoc网络,针对某特定应用环境的需要,采用TDMA的信道接入机制,节点分为物理层、链路层、网络层。由于网络规模比较小(节点数不超过12),采用固定信道分配方式,每个节点分配固定的控制信道和业务信道,使控制报文和数据报文相分离,这使得在TDMA模式下,帧的发送具有无冲突、周期性、固定帧长等特点。虽然链路层并不关心邻居信息,但是由于链路层可以比网络层更有效地侦测到邻居信息,能减少网络层的路由开销,提高信道利用率。基于上述特点,使得在链路层完成NM功能极具优势。本文针对无线Ad Hoc网络的功能需求,在VxWorks嵌入式系统下设计并实现了一种基于多信道的邻居管理NM (Neighbor Management)协议。该协议针对网络初始化的邻居发现和全网的链路维护两个场景。在邻居发现阶段,采用时间驱动方式,定时与邻居节点交换HELLO消息,查询邻居链路的双向连通,检测邻居链路的变化;在全网链路维护阶段,采用事件驱动方式,泛洪邻居变化信息,建立和维护全网活动节点的拓扑分布(连通表)。

2 NM协议的设计与实现

2.1 邻居管理操作

基于多信道的NM机制,采用TDMA的方式,将信道划分为M个控制信道和多个业务信道,每个节点分配固定的控制信道,节点在控制信道公告NM信息分组,同时监听邻居节点的公告信息。

为了不影响节点的正常信道接入,每个节点建立一个帧号,帧号取16位(0～65 535),在达到最大值时从0开始循环取值。控制信道每发送一个时帧,帧号就增1,并把该帧号添加到链路分组中,刚入网的节点收到邻居节点的链路分组,修改本地帧号使之与邻居节点一致,从而达到全网节点在同一时间帧号一致。对于HELLO信息的公告,全网节点在帧号范围(1 024n～1024n+10)发送,避免了在控制信道的HELLO信息与其他控制报文的冲突,并使节点在统一时间段内进行HELLO消息广播,缩短了邻居发现时间。另外,公告邻居变化表时,如果节点有控制报文等待发送,节点将其缓冲,等待公告发送结束后,再继续发送。由于只有邻居发现和删除时才广播邻居变化表,占用控制信道时间比较少,所以造成的控制报文延迟很小。

HELLO消息的格式为ID号、邻居数、邻居列表。邻居列表是一个动态的一维数组,列出了它最近检测到的与它单向连通的邻居节点的ID号。邻居变化表的格式为源节点ID号、节点ID号、链路状态和序列号SEQ。链路状态1’表示连通,0’表示不连通。为了重复分组检测,每个节点维护一个序列号SEQ,节点每次发送一个邻居变化分组其维护的SEQ单调增1,其他节点收到一个信息分组依靠序列号和源节点ID号来判断自己是否转发过该分组。

每个节点维护一个连通表,表示全网节点链路的双向连通性,用矩阵A[i][j]表示。

其中,i、j表示节点的ID号,构成矩阵的行和列,行数和列数等于网内活动节点数,对应的元素表示双向连通状态。

基于多信道的邻居管理的操作主要分为以下三步:

(1)初始连通表的建立

连通表的初始值为全零,当节点入网成功后,以请求的方式从邻居节点得到全网最新的连通表,建立初始连通表。当节点第一个开始组网时,连通表为初始值全零。

(2)邻居发现和删除

节点通过帧号的范围,周期性地广播HELLO消息,同时监听邻居节点的HELLO信息,图1是一个邻居发现的例子。假设两个节点A与B分别处于不同的控制信道Ta和Tb。首先节点A在Ta上公告的HELLO消息被B接收,B将A的ID号添加到其维护的邻居列表NLb中,同时在信道Tb上公告HELLO消息(NLb),A收到公告后,将B的ID号添加到NLa中,同时查看NLb,发现B已经接收到之前A所发出的公告,A认定两者是邻居关系。在下一次公告时,B收到A的公告信息,同样也可以判断与A为邻居关系。通过这种握手机制完成了相互发现过程。容易推导,节点在前两次公告后即可实现相互发现过程。

实现邻居发现后,节点通过链路监测机制,当在一连续时间段内没有收到邻居节点的HELLO消息时,表示链路断开,则从邻居列表中将邻居节点ID号删除。

(3)泛洪邻居变化信息

节点通过邻居的发现与删除机制,修改连通表,并全网广播邻居变化信息,使全网节点的连通表达到同步。节点收到邻居变化信息分组后,查看分组中的源节点ID号和SEQ,判断是否有该ID和SEQ的记录,如果没有则更新连通表,转发该分组,否则丢弃。

2.2 实现方案

在本系统中,链路层设计采用“底层驱动软件+嵌入式实时多任务操作系统+协议栈”的设计结构,主要完成TDMA信道接入协议与NM协议的设计,本文主要实现NM协议。链路层总体软件结构如图2所示。硬件平台采用S3C2510的32位网络处理器和相应的外设构成硬件平台,RTOS采用VxWorks,使用I/O口进行NM数据分组的收发,使用串口将连通表发送给网络层。

VxWorks操作系统是一种嵌入式实时操作系统(RTOS),是嵌入式开发环境的主要组成部分,具有可靠性高、实时性强、可裁减等特点。VxWorks为程序员提供了高效的实时任务调度、中断管理、实时的系统资源以及任务间通信。

基于NM的功能需求和VxWorks操作系统的实时性,遵循H.Gomma原则[5],将系统划分为六个任务,如图3所示。

图3中,每一个虚线框图对应一个独立的任务,并建立邻居列表和连通表两个全局变量。其设计思想如下:

(1)首先从接收任务I/O口中检测到链路数据,取出其中的NM消息包,通过消息队列Msg发送到数据处理任务。

(2)数据处理任务对不同的NM信息进行不同的处理。首先通过邻居连通表的接收,建立初始的连通表。通过HELLO消息包实现邻居的发现,维护邻居列表和连通表;通过邻居变化信息包来判断两跳范围外的节点链路变化情况,若第一次收到,则修改连通表,转发邻居变化信息。

(3)链路检测任务通过taskdelay (int ticks)函数,每30s查看邻居HELLO消息的接收情况,监测邻居链路的变化,若在连续30s内没有收到邻居节点的HELLO消息,则在邻居列表中删除邻居ID号,修改连通表,泛洪邻居变化信息。

(4)数据处理任务产生二进制信号量Sem1和Sem2,分别触发I/O口发送任务和串口发送任务,完成任务的同步,泛洪邻居变化信息和发送连通表到网络层。

(5)通过硬件定时器,设定时帧的帧号,在帧号为(1 024n～1 024n+10)范围内广播HELLO消息。

3 功能测试

NM协议模块位于无线Ad Hoc网络系统体系结构框架内,现有的网络节点已研制成功,本文在真实的网络节点上对NM模块功能进行设计开发和测试,如图4所示为测试环境。

在该测试场景中,节点1(ID号为1)开始组网,节点2(ID号为2)通过节点1接入网络中,节点3(ID号为3)通过节点2接入网络中,节点1与节点2互为邻居,节点2与节点3互为邻居。测试的目的是检验NM的功能,PC机与链路控制器中的VxWorks平台通过控制台串口相连,用于观测节点NM数据包的收发和处理,通过超级终端从节点1抓包如图5:节点1周期性地发送HELLO数据(-1-0-0-0),当第一次检测到节点2的HELLO消息包(-2-1-0-0)时,在邻居列表中添邻居ID号(-1-2-0-0),并更新连通表,泛洪邻居变化信息(-1-2-1-1)。节点1第一次收到节点2发送的邻居变化信息(-2-3-1-1)后,发现节点2和节点3为邻居,修改连通表,并转发该邻居变化信息包(-2-3-1-1)时,对于再次收到同样的邻居变化信息包(判断SEQ,仍为1)时,不作处理。

根据NM的功能测试结果可以看出:此方案能提供实时、充分的邻居节点信息,建立全网统一的连通表,有助于提高上层应用的性能。

本文针对某工作于特定环境的无线Ad Hoc网络的需要,在链路层设计了一种基于多信道的邻居管理协议,该协议不仅能准确地掌握邻居节点信息,还能维护全网节点统一的连通表,有效地服务于网络层,并在VxWorks操作系统下对该协议进行了设计,功能测试结果表明,该协议稳定、可靠、准确。本文提出的邻居管理协议适用于网络规模较小的无线Ad Hoc网络。

摘要：针对无线 Ad Hoc 网络系统的需求,基于 VxWorks 操作系统,设计并实现了一种基于多信道的邻居管理协议,用于实现邻居的发现、删除以及全网节点的连通性维护。测试结果表明,该协议能确保网络节点之间高效可靠地完成邻居管理功能。

关键词：无线 Ad Hoc,多信道,邻居管理,连通表

参考文献

[1] 郑少仁,王海涛,赵志峰,等.Ad Hoc 网络技术.北京: 人民邮电出版社,2005．

[2] PERKINS C E,BHAGWAT P.Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers.In:Proceedings of SIGCOMM 4． NEW York:ACM Press,1994:234-244．

[3] MOSKO M,GARCIA-LUNA-ACEVES.A self-correcting neighbor protocol for mobile Ad Hoe wireless networks.Proc.IEEE ICCCN'02,2002:556-560．

[4] KYASANUR P,VAIDYA N H.Capacity of multi-channel wireless networks:impact of number of channels and interfaces.ACM MOBICOM'O5,Cologne,Germanv:43-57．

无线Adhoc

无线Adhoc 第1篇

无线Adhoc 第2篇

无线Adhoc 第3篇

无线Adhoc 第4篇

无线Adhoc 第5篇

无线Adhoc 第6篇

无线Adhoc 第7篇

无线Adhoc 第8篇

无线Adhoc

猜你喜欢

栏目

最近更新

热门标签