基于图着色的无线自组网极小连通支配集算法

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。     

基于计时器的最小连通支配集生成算法

在分簇的MANET中,基于计时器思想提出最小连通支配集生成算法,实现动态拓扑下骨干网构建与重构,证明了算法正确性。仿真结果表明,该算法能以少量消息开销,生成较小连通支配集,快速调整骨干网适应拓扑变化。     

定向自组网中基于连通支配集优化的信息共享算法

无线自组织网络中的信息共享是指,每个节点都将自己所拥有的信息传播到其他节点的行为.然而,在时延敏感型的网络中,需要努力减小共享过程的时延.针对定向自组织网络信息共享中的冗余控制和空分复用问题,提出了一种基于连通支配集优化的调度方案.该方案首先设计了适合定向传输的连通支配集构造方法,其次根据节点负载和链路耗费对连通支配集...     

移动自组网QoS保证技术的探讨

如何为用户提供相应的Qos保证是移动自组网发展的技术瓶颈之一。文章分别从QoS信令、QoS路由和QoS MAC方面比较全面地探讨了如何实现Qos保证;详细阐述了每个方面的关键技术,并结合主流协议介绍了具体操作过程,剖析了实现过程中的难点。     

构造自组网的容错骨干集

为简化网络结构和提高网络性能所使用的骨干网技术若未考虑容错易造成自组网无法面对节点和无线信道失效.本文研究了如何利用容错骨干来提高网络可靠性,设计了一种分布式容错骨干集构造算法LKFB,满足网络内任意两点之间仅通过容错骨干集保持最大限度K连通容错能力.仿真结果表明,LKFB能够通过改变K值来调整网络的容错能力,通过增加较少的骨干节点换得较高的容错性能.最后通过修改权值函数能够保证按照全网能耗均衡的方式选择容错骨干.     

移动自组网中的QoS保障及解决思路

介绍了移动自组网中OoS保障的难点，对目前的几种解决思路进行了分析，选取AODV路由协议作为具体的例子，对其QoS路由进行了分析并提出了今后的研究方向。     

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.     

移动自组网QoS路由协议研究

移动自组网是由一组带有无线收发装置的移动节点组成的一个多跳的临时性的自治系统。随着无线通信中多媒体业务的增加,在移动自组网中提供QoS(Quality of Sevice服务质量)保障具有越来越重要的意义,而QoS路由技术则是其中的核心技术和热点问题。文章指出移动自组网QoS路由的困难,对移动自组网典型QoS路由协议进行了详细的分析与比较,并对几种较新的移动自组网QoS路由协议进行了介绍,末了对移动自组网QoS路由协议的发展进行了展望。     

基于定向扩散的最小连通支配集构造算法

针对区域覆盖算法未考虑节点的通信梯度问题,利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列,提出了一种基于定向扩散的最小连通支配集构造算法.在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集,然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来,最终得到一个近似的最小连通支配集.理论及仿真实验结果表明,该算法构造的连通支配集最小且计算耗时少,能多重有效覆盖热点区域,从而延长无线传感器网络的寿命.     

基于定向天线的移动自组网路由协议研究

同等功耗下,定向天线能够产生更高的增益,提供更大的传输范围,提高网络的空间复用度和吞吐量,天线选择的方向性又降低了邻近结点之间的相互干扰,采用定向天线能够给移动自组网带来潜在性能的提高。对基于定向天线的移动自组网路由协议进行研究,简单介绍了定向天线,总结了引入定向天线产生的路由问题,对现有的一些典型定向路由协议进行了分类、介绍和比较,最后对引入定向天线带来的好处进行了分析。     

RPSF: A Routing Protocol with Selective Forwarding for Mobile Ad-Hoc Networks

Many existing reactive routing algorithms for mobile ad-hoc networks use a simple broadcasting mechanism for route discovery which can lead to a high redundancy of route-request messages, contention, and collision. Position-based routing algorithms address this problem but require every node to know the position and velocity of every other node at some point in time so that route requests can be propagated towards the destination without flooding the entire network. In a general ad-hoc network, each node maintaining the position information of every other node is expensive or impossible. In this paper, we propose a routing algorithm that addresses these drawbacks. Our algorithm, based on one-hop neighborhood information, allows each node to select a subset of its neighbors to forward route requests. This algorithm greatly reduces the number of route-request packets transmitted in the route-discovery process. We compare the performance of our algorithm with the well known Ad-hoc On-demand Distance Vector (AODV) routing algorithm. On average, our algorithm needs less than 12.6% of the routing-control packets needed by AODV. Simulation results also show that our algorithm has a higher packet-delivery ratio and lower average end-to-end delay than AODV.     

无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.     

Associativity-Based Routing for Ad Hoc Mobile Networks

This paper presents a new, simple and bandwidth-efficient distributed routing protocol to support mobile computing in a conference size ad-hoc mobile network environment. Unlike the conventional approaches such as link-state and distance-vector distributed routing algorithms, our protocol does not attempt to consistently maintain routing information in every node. In an ad-hoc mobile network where mobile hosts (MHs) are acting as routers and where routes are made inconsistent by MHs' movement, we employ an associativity-based routing scheme where a route is selected based on nodes having associativity states that imply periods of stability. In this manner, the routes selected are likely to be long-lived and hence there is no need to restart frequently, resulting in higher attainable throughput. Route requests are broadcast on a per need basis. The association property also allows the integration of ad-hoc routing into a BS-oriented Wireless LAN (WLAN) environment, providing the fault tolerance in times of base stations (BSs) failures. To discover shorter routes and to shorten the route recovery time when the association property is violated, the localised-query and quick-abort mechanisms are respectively incorporated into the protocol. To further increase cell capacity and lower transmission power requirements, a dynamic cell size adjustment scheme is introduced. The protocol is free from loops, deadlock and packet duplicates and has scalable memory requirements. Simulation results obtained reveal that shorter and better routes can be discovered during route re-constructions.     

Integrated Routing and Storage for Messaging Applications in Mobile Ad Hoc Networks

This paper is motivated by the observation that traditional ad hoc routing protocols are not an adequate solution for messaging applications (e.g., e-mail) in mobile ad hoc networks. Routing in ad hoc mobile networks is challenging mainly because of node mobility – the more rapid the rate of movement, the greater the fraction of bad routes and undelivered messages. For applications that can tolerate delays beyond conventional forwarding delays, we advocate a relay-based approach to be used in conjunction with traditional ad hoc routing protocols. This approach takes advantage of node mobility to disseminate messages to mobile nodes. The result is the Mobile Relay Protocol (MRP), which integrates message routing and storage in the network; the basic idea is that if a route to a destination is unavailable, a node performs a controlled local broadcast (a relay) to its immediate neighbors. In a network with sufficient mobility – precisely the situation when conventional routes are likely to be non-existent or broken – it is quite likely that one of the relay nodes to which the packet has been relayed will encounter a node that has a valid, short (conventional) route to the eventual destination, thereby increasing the likelihood that the message will be successfully delivered. Our simulation results under a variety of node movement models demonstrate that this idea can work well for applications that prefer reliability over latency.     

移动自组织网络预测分簇算法的路由协议

针对移动自组织网络中传统分簇算法存在稳定性低、网络开销大的问题,在WCA分簇算法的基础上,提出一种带有预测机制的EWCA-MP(Efficient on-demand Weighted Clustering Algorithm using Mobility Prediction)分簇算法,该算法在簇头选择时充分考虑节点间的链路保持时间,在簇维护阶段引入模糊逻辑的概念,对Hello消息包的广播周期进行优化。并将其应用于CBRP中,提出了一种ECBRP-MP(Efficient Cluster Based Routing Protocol using Mobility Prediction)移动预测的分簇路由协议。仿真结果表明,EWCA-MP算法在簇头数目、单位时间内节点转移次数和统治集更新次数明显减少,ECBRP-MP路由协议在路由开销、分组投递率的性能得到优化。     

Energy-Efficient Routing for Connection-Oriented Traffic in Wireless Ad-Hoc Networks

We address the problem of routing connection-oriented traffic in wireless ad-hoc networks with energy efficiency. We outline the trade-offs that arise by the flexibility of wireless nodes to transmit at different power levels and define a framework for formulating the problem of session routing from the perspective of energy expenditure. A set of heuristics are developed for determining end-to-end unicast paths with sufficient bandwidth and transceiver resources, in which nodes use local information in order to select their transmission power and bandwidth allocation. We propose a set of metrics that associate each link transmission with a cost and consider both the cases of plentiful and limited bandwidth resources, the latter jointly with a set of channel allocation algorithms. Performance is measured through call blocking probability and average energy consumption and our detailed simulation model is used to evaluate the algorithms for a variety of networks.     

A Distributed Virtual Backbone Development Scheme for Ad-Hoc Wireless Networks

The virtual backbone is an approach for solving routing problems in ad-hoc wireless networks. The virtual backbone approach features low latency, moderate routing overhead and is a hybrid scheme that uses the table-driven and on-demand routing protocols. This work presents a distributed virtual backbone development scheme for ad-hoc wireless networks. Using clustering, distributed labeling and heuristic Steiner tree techniques, our scheme outperforms other schemes in terms of the size and stability of the virtual backbone and the virtual backbone change rate. Experimental results demonstrate that our scheme has lower overhead than traditional table-driven and on-demand routing schemes. This revised version was published online in July 2006 with corrections to the Cover Date.     

On Increasing Service Accessibility and Efficiency in Wireless Ad-Hoc Networks with Group Mobility

Wireless ad-hoc networks consist of mobile nodes interconnected by multi-hopwireless paths. Unlike conventional wireless networks, ad-hoc networks haveno fixed network infrastructure or administrative support. Because of thedynamic nature of the network topology and limited bandwidth of wirelesschannels, Quality-of-Service (QoS) provisioning is an inherently complex anddifficult issue. In this paper, we propose a fully distributed and adaptivealgorithm to provide statistical QoS guarantees with respect toaccessibility of services in an ad-hoc network. In this algorithm,we focus on the optimization of a new QoS parameter of interest, serviceefficiency, while keeping protocol overheads to the minimum. To achievethis goal, we theoretically derive the lower and upper bounds of serviceefficiency based on a novel model for group mobility, followed by extensivesimulation results to verify the effectiveness of our algorithm.     

一种改进的基于连通支配集的P2P搜索算法

为了避免由洪泛搜索方法引起的大量网络流量问题．基于连通支配集的广播算法BCDS通过减少转发节点来减少查询消息数。文章对BCDS算法进行改进，选择转发节点时考虑节点间的距离．简化选择转发节点的操作，且不用维持局部两跳拓扑信息。实验结果表明当搜索结果相同时，改进的BCDS算法的消息数量平均仅为洪泛搜索方法的35％。