Multi-constraint multi-objective QoS aware routing heuristics for query driven sensor networks using fuzzy soft sets

In this paper, a fuzzy based distributed power aware routing scheme considering both energy and bandwidth constraints, especially for query driven applications in the asynchronous duty-cycled wireless sensor networks are devised. The proposed multi-constraint, multi-objective routing optimization approach under strict resource constraints guarantees reliability and fast data delivery along with efficient power management in spite of unreliable wireless links and limited power supply. In query driven applications, the request from the sink to the individual sensor node will be a broadcast message, whereas the individual sensor nodes replies back to sink as unicast messages. In the proposed work, the fuzzy approach and “A Star” algorithm are utilized for satisfying energy and bandwidth constraints to route the broadcast messages of the sink while querying all the sensor nodes in the network. Every node will be provided with a guidance list, which is used to decide the next best neighbor node with good route quality for forwarding the received multi-hop broadcast messages. The route quality of the every node is estimated with fuzzy rules based on the network parameters such as maximum remaining energy, minimum traffic load and better link quality to increase the network lifetime. The provision of overhearing the broadcast messages and acknowledgements within the transmission range minimizes the effort to search for the active time of nodes while routing the broadcast messages with asynchronous scheduling. Further, in the proposed work only the time slot of its nearest neighbor relay node (to which packets are to be forwarded) is learnt to reduce the number of message transmissions in the network. For the unicast message replies, the fuzzy membership function is modified and devised based on the routing metrics such as higher residual energy, minimum traffic loads and minimum hop count under energy and bandwidth constraints. Also, the multi-hop heuristic routing algorithm called Nearest Neighbor Tree is effectively used to reduce the number of neighbors in the guidance list that are elected for forwarding. This helps to increase the individual sensor node’s lifetime, thereby maximizes the network lifetime and guarantees increased network throughput. The simulation results show that the proposed technique reduces repeated transmissions, decreases the number of transmissions, shortens the active time of the sensor nodes and increases the network lifetime for query driven sensor network applications invariant to total the number of sensor nodes and sinks in the network. The proposed algorithm is tested in a small test bed of sensor network with ten nodes that monitors the room temperature.     

Centralized asynchronous broadcast in radio networks

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.     

Efficient Directional Network Backbone Construction in Mobile Ad Hoc Networks

In this paper, we consider the issue of constructing an energy-efficient virtual network backbone in mobile ad hoc networks (MANETs) for broadcasting applications using directional antennas. In directional antenna models, the transmission/reception range is divided into several sectors and one or more sectors can be switched on for transmission. Therefore, data forwarding can be restricted to certain directions (sectors), and both energy consumption and interference can be reduced. We develop the notation of directional network backbone using the directional antenna model, and form the problem of the directional connected dominating set (DCDS) which is an extreme case of the directional network backbone using an unlimited number of directional antennas. The minimum DCDS problem is proved to be NP-complete. A localized heuristic algorithm for constructing a small DCDS and two extensions of the algorithm are proposed. Performance analysis includes an analytical study in terms of an approximation ratio and a simulation study on the proposed algorithms using both a custom simulator and ns2.     

基于网络编码的航空自组网安全路由算法

针对航空自组网路由可靠性低及安全性差的特点,提出了基于网络编码的安全路由算法NC-SRP。该算法基于地理位置信息确定协作编码簇进而构建多路径传输网络,保证了源节点和目的节点的匿名性;将消息编码后连同编码向量进行分割转发;协同簇内节点对消息重编码并多播,对累积编码向量重编码后分散转发,从而可以在不需要密钥的情况下保证消息的安全性。理论分析与仿真实验表明,NC-SRP提高了消息的安全性的同时依靠网络编码的优势提高了路由的性能。     

Efficient broadcasting in ad hoc wireless networks using directional antennas

Using directional antennas to conserve bandwidth and energy consumption in ad hoc wireless networks (or simply ad hoc networks) is becoming popular. However, applications of directional antennas for broadcasting have been limited. We propose a novel broadcast protocol called directional self-pruning (DSP) for ad hoc wireless networks using directional antennas. DSP is a nontrivial generalization of an existing localized deterministic broadcast protocol using omnidirectional antennas. Compared with its omnidirectional predecessor, DSP uses about the same number of forward nodes to relay the broadcast packet, while the number of forward directions that each forward node uses in transmission is significantly reduced. With the lower broadcast redundancy, DSP is more bandwidth and energy-efficient. DSP is based on 2-hop neighborhood information and does not rely on location or angle-of-arrival (AoA) information. Two special cases of DSP are discussed: the first one preserves shortest paths in reactive routing discoveries; the second one uses the directional reception mode to minimize broadcast redundancy. DSP is a localized protocol. Its expected number of forward nodes is O(1) times the optimal value. An extensive simulation study using both custom and ns2 simulators show that DSP significantly outperforms both omnidirectional broadcast protocols and existing directional broadcast protocols.     

无线多跳通信网络中基于贝叶斯概率模型的消息转发机制研究

无线多跳通信网络依赖多节点中继实现信息传输,因不需要依赖预先架设的基础设施而成为军用及民用领域等特殊应用场景下的重要通信方式。为了能在复杂及恶劣环境下组网,信源节点往往采用全网广播路由请求分组RREQ的泛洪方法,以提高多跳转发路径构建成功率。然而,全网泛洪广播产生消息的冗余转发和重叠效应引起节点能耗的上升和信道利用率的下降,导致分组碰撞与网络拥塞概率的上升,严重时可能造成网络瘫痪而失去效用。本文基于贝叶斯概率论设计了无线多跳通信网络的消息转发模型,通过计算节点密度和后验概率在保证网络连通性的条件下减少不必要的消息转发。基于NS2的仿真结果表明,本文所提出的基于贝叶斯概率模型的消息转发机制能够有效减小广播分组的重播次数。相比于同类算法,在基本保证网络吞吐量的前提下,可以有效降低能量消耗、路由开销,并提高分组成功交付率,从而为未来广域大规模动态多跳网络部署提供技术支撑。     

基于网络编码的异构无线传感器网络数据广播协议

本文提出一种适应异构无线传感器网络的能量感知的网络编码数据广播协议(ENCBP)。传感器节点根据邻居能量信息列表实时地计算节点剩余能量的线性映射值。在此基础上,采用能量感知的网络编码转发概率机制,使具有较高剩余能量的节点比低能量节点拥有更高的数据转发优先级,以实现能量均衡的数据传输。另外,采用伪广播机制对协议进行优化,以提高数据包投递率。仿真结果表明,ENCBP不仅可以有效实现网络的能耗均衡,以延长网络的生命周期,还能在一定程度上降低数据包传输时延,从而提高数据通信性能。     

An Optimal Algorithm for Broadcasting Multiple Messages in Trees

We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting scheme prescribes in which time unit a given node should send a message to which child. It is k-optimal if it achieves the smallest possible time for broadcasting k messages from the source to all nodes. We give an algorithm to construct a k-optimal broadcasting scheme for an arbitrary n-node tree. The time complexity of our algorithm is O(nk), i.e., the best possible.     

Optimizing responses to broadcast messages in radio networks

Algorithms to optimize the performance of response traffic for broadcast messages in a packet-switched radio network are studied. The situation considered here involves a source node sending a broadcast message to all destinations and collecting positive response packets from these destinations in a fully connected packet radio network. The exact value of the number of destination nodes is unknown. A contention-based two-level protocol is described. Based on the protocol, an optimization problem is formulated in order to minimize the time for the source node to receive all the responses. Several algorithms are presented and numerical results of the corresponding optimization problems are obtained. These optimization problems are treated by the methods of dynamic programming. An extension of the basic scheme—multicast instead of full broadcast message—is also studied.     

节点转发消息能力动态估计的缓存替换策略

机会网络中的节点以“存储-携带-转发”的方式完成消息转发,消息需要在中继节点缓存较长时间以等待通信机会,高效的缓存替换策略能够提高有限缓存空间的利用率。提出一种基于节点转发消息能力的自适应缓存替换策略。通过动态地感知当前的消息传输状态,并根据其在此节点中的停留时间和消息转发状态,估计节点对该消息的转发能力,进而调整消息的转发以及删除优先级。结果表明所提出的缓存替换策略能够有效提高消息的成功投递率,并大幅度地降低网络负载率。     

基于节点社会性的无线网络编码传输策略研究

延迟容忍网络是一种缺乏持续连接的新型网络体系结构,选择合适的转发节点是实现延迟容忍网络高效的转发和投递消息的关键问题。由于节点移动性和网络拓扑动态变化等会对延迟容忍网络的传输效率产生影响,提出了一种基于节点社会性和利用随机线性网络编码的DTN网络模型NSNC-DTN。NSNC-DTN网络模型利用网络中的社团结构、社团紧密度以及节点活跃度,选择出最合适的转发节点。离线计算节点的社会性,对源节点和Center节点进行随机线性网络编码,在线完成转发,从而达到高效转发和投递的目的。仿真结果表明NSNC-DTN网络能够有效的提高信息投递成功率,减小端对端的网络延迟和网络开销。     

Dominating sets and neighbor elimination-based broadcastingalgorithms in wireless networks

In a multihop wireless network, each node has a transmission radius and is able to send a message to all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. In this paper, we propose to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets. Their maintenance does not require any communication overhead in addition to maintaining positions of neighboring nodes. Retransmissions by only internal nodes in a dominating set is sufficient for reliable broadcasting. Existing dominating sets are improved by using node degrees instead of their ids as primary keys. We also propose to eliminate neighbors that already received the message and rebroadcast only if the list of neighbors that might need the message is nonempty. A retransmission after negative acknowledgements scheme is also described. The important features of the proposed algorithms are their reliability (reaching all nodes in the absence of message collisions), significant rebroadcast savings, and their localized and parameterless behavior. The reduction in communication overhead for the broadcasting task is measured experimentally. Dominating set based broadcasting, enhanced by a neighbor elimination scheme and highest degree key, provides reliable broadcast with ⩽53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with <48 percent for ⩽3, ⩽40 percent for d⩾10, and ⩽20 percent for d⩾25. The proposed methods are better than existing ones in all considered aspects: reliability, rebroadcast savings, and maintenance communication overhead. In particular, the cluster structure is inefficient for broadcasting because of considerable communication overhead for maintaining the structure and is also inferior in terms of rebroadcast savings     

采用方向性天线的Ad Hoc网络邻居发现策略研究

为了有效支持MAC和路由协议,对采用方向性天线的邻居发现策略进行了研究,提出了基于Hello消息的邻居发现策略(HDND),尽量通过全向天线广播两跳Heno消息发现方向性邻居,只有当节点成为孤立节点或网络可能存在网络分区时,才利用方向性天线进行扫描发现,该策略既降低了方向性天线通过扫描进行邻居发现的高代价,又解决了网络中出现的孤立节点和网络分区问题.理论分析了方向性天线的高传输能力带给分组转发性能的提高,并利用仿真验证了分析结果.     

Efficient DSR route request flooding with directional antennas

In this paper, an efficient scheme for flooding the DSR route request in ad hoc networks using directional antennas is proposed. The scheme makes use of the local neighbor information provided by the neighbor discovery scheme. Route request packets are forwarded to selected representative neighbors using directional transmissions instead of being broadcast to all neighbors. Two strategies are proposed to efficiently select the representative neighbors: fixed branching and honeycomb strategies. The fixed branching strategy selects one representative neighbor in each predefined forwarding direction, while the honeycomb strategy selects representative neighbors to create a hexagonal tiling pattern. Simulation results show that the proposed strategies are able to achieve a high route discovery success rate while keeping the number of involved nodes and the number of transmissions low.     

节点度估计和静态博弈转发策略的Ad Hoc网络路由协议

针对Ad Hoc网络路由发现过程中广播路由请求分组导致的广播风暴问题，提出了一种基于节点度估计和静态博弈转发策略的Ad Hoc网络路由协议NGRP.NGRP考虑边界影响，采用分段函数的思想将网络场景分为中心、边和角区域，分别估算网络中节点在不同区域的节点度，避免了周期性广播Hello消息获取节点度导致的开销；NGRP路由请求分组的转发采用静态博弈转发策略，利用节点度估算参与转发路由请求分组的节点数量，将转发和不转发作为策略集合，设计效益函数，通过纳什均衡获得节点转发路由请求分组的转发概率，从而减少了路由请求分组广播过程中产生的大量的冗余、竞争和冲突，提高了路由发现过程中路由请求分组的广播效率.运用NS-2对协议的性能进行大量的仿真，结果表明：NGRP的分组投递率、路由开销、MAC层路由开销和吞吐率这4项指标明显优于AODV+FDG，AODV with Hello和AODV without Hello协议.     

无线中继网络中基于方向天线的MAC协议

无线中继网络是指网络中的节点互相通信成为中继节点之间,中继节点之间距离很近可以形成协作分集,该文对这种网络进行了研究,引入多天线技术(MIMO)中的波束成型技术来消除信道间干扰,实现并行传输数据,分析了协作传输策略,结合协作传输策略对中继节点的功率分配进行了优化,基于合协作传输策略设计了一种基于方向天线的MAC协议.经过分析和实验仿真,基于MIMO波束成型的协作传输方法在相同情况下比其它的方法增加15％以上的信道容量.     

机会网络自私节点的Bertrand博弈与激励机制研究

在真实的网络环境中,很多节点可能是自私的,它们不愿意牺牲自己的资源为其他节点转发消息。针对这种情况,提出一种基于博弈论的激励机制,可以激励节点与其他节点相互合作。该机制为二阶段激励,激励节点接收消息以协助其他节点转发,同时激励节点转发更多的消息。把源节点与中继节点之间的竞争与合作模型化为Bertrand（伯特兰德）博弈,定义了源节点和中继节点的效用函数。求解了源节点的最佳定价策略和中继节点最佳的转发计划,验证了源节点与中继节点之间存在唯一的纳什均衡。模拟仿真结果表明提出的激励机制能够鼓励自私节点参与合作,能提高路由算法的传递率,同时降低了消息传递延迟。与基于声誉的激励机制相比,所提激励机制能使消息传递成功率提高31.4%、平均时延降低9.7%。     

基于改进网络编码的匿名通信机制研究

针对现有基于网络编码的匿名系统,由于转发节点的不稳定性以及匿名消息的多路径转发,使得数据发送的成功率较低的问题,提出了一种基于网络编码与数据冗余方法的新匿名通信机制ACSNC（anonymous communication system based on network coding）。首先采用数据冗余机制对要发送的数据进行冗余分片,并沿多条路径发送;然后中间转发节点对信息进行随机编码后转发,使信息通过节点前后的统计特性发生变化;最后,目的节点根据收到的数据片与编码系数恢复匿名信息。仿真结果表明,该机制在显著提高数据发送成功率的基础上,能够有效地保障通信的匿名性与安全性。     

基于拓扑快速变化的OLSR改进路由协议研究

针对优化链路状态路由协议（OLSR）在网络拓扑结构快速变化时性能下降的问题,提出了一种新的结合鱼眼状态路由和能量感知的自适应改进路由协议,命名为AFE-OLSR。该改进协议通过监听节点链路集和多点中继选择集的变化情况,自动调整HELLO和拓扑控制消息的发送频率,实现移动感知。同时,它借鉴鱼眼状态路由的思想,节点自动调整拓扑控制消息的转发次数。通过这些机制,该协议能够记录接收消息的能量大小实现能量感知,以及根据能量感知和移动感知的结果来帮助节点选择更稳定和更可靠的路由。仿真结果表明,AFE-OLSR在网络拓扑变化时端到端时延减少8%,分组到达率提高11%,建立全网路由时间减少12%;在网络拓扑静止时HELLO发送量减少19%,TC转发量减少15%。     

Neighborhood tracking for mobile ad hoc networks

In mobile ad hoc networks (MANETs), node mobility causes network topologies to change dynamically over time, which complicates such important tasks as broadcasting and routing. In a typical efficient localized approach, each node makes forwarding decisions based on a neighborhood local view constructed simply by collecting received “Hello” messages. That kind of neighborhood local view can become outdated and inconsistent, which induces a low-coverage problem for efficient broadcasting tasks and a low-delivery ratio problem for efficient routing tasks. In this paper, we propose a neighborhood tracking scheme to guarantee the accuracy of forwarding decisions. Based on historical location information, nodes predict the positions of neighbors when making a forwarding decision, and then construct an updated and consistent neighborhood local view to help derive more precise forwarding decisions. The inaccuracy factors of our scheme are also discussed and an accessory method is provided for possible usage. Simulation results illustrate the accuracy of our proposed tracking scheme. To verify the effectiveness of our scheme, we apply it to existing efficient broadcast algorithms. Simulation results indicate that our neighborhood tracking scheme can improve the protocols coverage ratio greatly.