Applications of k-local MST for topology control and broadcasting in wireless ad hoc networks

We propose a family of structures, namely, k-localized minimum spanning tree (LMST/sub k/) for topology control and broadcasting in wireless ad hoc networks. We give an efficient localized method to construct LMST/sub k/ using only O(n) messages under the local-broadcast communication model, i.e., the signal sent by each node would be received by all nodes within the node's transmission range. We also analytically prove that the node degree of the structure LMST/sub k/ is at most 6, LMST/sub k/ is connected and planar and, more importantly, the total edge length of the LMST/sub k/ is within a constant factor of that of the minimum spanning tree when k/spl ges/2 (called low weighted hereafter). We then propose another low weighted structure, called Incident MST and RNG Graph (IMRG), that can be locally constructed using at most 13n messages under the local broadcast communication model. Test results are corroborated in the simulation study. We study the performance of our structures in terms of the total power consumption for broadcasting, the maximum node power needed to maintain the network connectivity. We theoretically prove that our structures are asymptotically the best possible for broadcasting among all locally constructed structures. Our simulations show that our new structures outperform previous locally constructed structures in terms of broadcasting and power assignment for connectivity.     

无线 Ad hoc 网络和传感网络中基于位置的、可靠的无信标传输路由方法

Existing position-based routing algorithms, where packets are forwarded in the geographic direction of the destination, normally require that the forwarding node should know the positions of all neighbors in its transmission range. This information on direct neighbors is gained by observing beacon messages that each node sends out periodically. Several beaconless greedy routing schemes have been proposed recently. However, none of the existing beaconless schemes guarantee the delivery of packets. Moreover, they incur communication overhead by sending excessive control messages or by broadcasting data packets. In this paper, we describe how existing localized position based routing schemes that guarantee delivery can be made beaconless, while preserving the same routes. In our guaranteed delivery beaconless routing scheme, the next hop is selected through the use of control RTS/CTS messages and biased timeouts. In greedy mode, the neighbor closest to destination responds first. In recovery mode, nodes closer to the source will select shorter timeouts, so that other neighbors, overhearing CTS packets, can eliminate their own CTS packets if they realize that their link to the source is not part of Gabriel graph. Nodes also cancel their packets after receiving data message sent by source to the selected neighbor. We analyze the behavior of our scheme on our simulation environment assuming ideal MAC, following GOAFR+ and GFG routing schemes. Our results demonstrate low communication overhead in addition to guaranteed delivery.     

Optimal transmission radius for energy efficient broadcasting protocols in ad hoc and sensor networks

We investigate the problem of minimum energy broadcasting in ad hoc networks where nodes have capability to adjust their transmission range. The minimal transmission energy needed for correct reception by neighbor at distance r is proportional to r/sup /spl alpha//+c/sub e/, /spl alpha/ and c/sub e/ being two environment-dependent constants. We demonstrate the existence of an optimal transmission radius, computed with a hexagonal tiling of the network area, that minimizes the total power consumption for a broadcasting task. This theoretically computed value is experimentally confirmed. The existing localized protocols are inferior to existing centralized protocols for dense networks. We present two localized broadcasting protocols, based on derived "target" radius, that remain competitive for all network densities. The first one, TR-LBOP, computes the minimal radius needed for connectivity and increases it up to the target one after having applied a neighbor elimination scheme on a reduced subset of direct neighbors. In the second one, TRDS, each node first considers only neighbors whose distance is no greater than the target radius (which depends on the power consumption model used), and neighbors in a localized connected topological structure such as RNG or LMST. Then, a connected dominating set is constructed using this subgraph. Nodes not selected for the set may be sent to sleep mode. Nodes in selected dominating set apply TR-LBOP. This protocol is the first one to consider both activity scheduling and minimum energy consumption as one combined problem. Finally, some experimental results for both protocols are given, as well as comparisons with other existing protocols. Our analysis and protocols remain valid if energy needed for packet receptions is charged.     

A probabilistic and opportunistic flooding algorithm in wireless sensor networks

In wireless sensor networks, many communication protocols and applications rely on flooding for various networking purposes. Prior efforts focus on how to design efficient flooding algorithms; that is, they seek to achieve full reliability while reducing the number of redundant broadcasting across the network. To achieve efficient flooding, most of the existing protocols try to reduce the number of transmissions, which is decided without considering any online transmission result. In this paper, we propose a probabilistic and opportunistic flooding algorithm that controls rebroadcasts and retransmissions opportunistically. It seeks to achieve a target reliability required by an application. For this purpose, it makes a given node select only the subset of its one-hop neighbors to rebroadcast the same message. It considers node relations such as link error rates among nodes in selecting eligible neighbors to rebroadcast. The sender controls the number of retransmissions opportunistically by tracking the current status of message reception at its neighbors. Simulation is carried out to reveal that our proposed scheme achieves the given target reliability with less overhead than other flooding algorithms in most cases, thus prolonging the network lifetime.     

一种产生小流量区域的Ad Hoc网可达阶段协议

MANET中的障碍区域阻碍着消息的中继。一些协议通过产生大量的冗余报文的办法避开障碍区将消息传输到目标区域。本文在分析了OFSDP的基础上，针对定位传输问题提出了一种新改进的单目标区域的可达阶段协议。与现存的可达阶段协议相比，该协议不仅能够保证消息避开未知障碍区到达目标区域，同时，它产生更小的报文流量，对减少MANET拥塞起到很大的作用。     

基于大功率消息广播的DTMSN路由机制

提出一种基于基站大功率信号广播的延迟容忍移动传感器网络消息路由机制(High-power Broadcasting based Routing scheme,HBR)。该机制使用两个通信频率f₁ 和f₂,基站以恒定大功率在频率f₁上广播已经接收到的消息,网络中传感器节点根据基站广播信息计算自身转发概率并清理冗余消息副本,节点间利用频率f₂进行通信。为进一步提升网络性能,HBR优先传输转发阈值(M)小且生存时间短的消息,并合理进行消息队列管理。仿真结果表明,与几种经典的路由机制相比,HBR在消息传输成功率、传输延迟方面有着一定的优势。     

Impact of noise and interference on probabilistic broadcast schemes in mobile ad-hoc networks

Broadcasting is a vital part of on-demand routing protocols to discover new routes in mobile ad-hoc networks (MANET). Pure flooding is the earliest and still widely used mechanism of broadcasting for route discovery in on-demand routing protocol. In pure flooding, a source node broadcasts a route request to its neighbors. These neighbors then rebroadcast the received route request to their neighbors until the route request arrives at the destination node. Pure flooding may generate excessive redundant traffic leading to increased contention and collisions deteriorating the performance. To limit the redundant traffic, a number of probabilistic broadcast schemes have been proposed in the literature. However, the performance of those probabilistic broadcasting schemes is questionable under real life MANETs which are noisy in nature. Environmental factors like thermal noise and co-channel interference may have adverse effects on the system performance. This paper investigates the effects of thermal noise and co-channel interference on the performance of probabilistic schemes employed in the route discovery mechanism in MANETs. Based on extensive ns-2 simulations, this paper discovers that, contrary to the findings of previous studies, these schemes do not outperform pure flooding scheme when thermal noise and co-channel interference are taken into account.     

基于密度和距离的多跳广播转发节点选择方案

多数车联网VANET(Vehicular Ad Hoc Network)的安全应用均采用多跳广播方式分发安全消息。现已提出了许多的多跳广播转发节点选择方案,但它们以减少转发节点数为目的。为此,提出基于密度和距离的多跳广播转发节点选择方案DDBFS(Density-Distance based multi-hop Broadcast Forwarder Selection scheme),记为DDBFS。DDBFS方案主要解决两个问题：密集区域的冗余广播和稀疏区域的高的传输时延。在提出的DDBFS方案中,节点在决策是否转播接收的消息前,依据距离和网络密度设置定时器,一旦定时完毕,且在定时期间,没有其他节点转发该消息,该节点就成为下一跳转发节点。仿真结果表明,与现有的方案相比,提出的DDBFS协议在重播次数和传输时延性能得到显著提高。在密集区域,消息重播次数下降了约57%,在稀疏区域,传输时延缩短了约82%。     

Dynamic Prediction based Multi Queue (DPMQ) drop policy for probabilistic routing protocols of delay tolerant network

Two most important issues should be considered to achieve data delivery in DTN networking: routing protocols for the network and intelligent buffer management policy for everyone node in the network. The routing scheme decides which messages should be forwarded when nodes meet, and the buffer management policy determines which message is purged when the buffer overflows in a node. This study proposes a buffer management policy named as Dynamic Prediction based Multi Queue (DPMQ) for probabilistic routing protocols. It works by classification of local buffer into three queues of messages, which are DCTL, HPTL and LPTL. The simulation results have proven that the DPMQ performs well as compared to DLA, DOA, MOFO, LIFO, LEPR and LIFO in terms of reducing the message relay, message drop, hop counts average and overhead while rising in the delivery probability.     

Evaluation of alternatives for the broadcast operation in Kademlia under churn

During recent years, considerable effort has been devoted to the enhancement of Distributed Hash Table (DHT) systems with broadcasting capabilities. Such systems typically provide individual node routing but a broadcast primitive is required for functionalities such as information dissemination or data aggregation. Broadcasting can also be used as the basis for partial keyword searches. Little work has however specifically addressed Kademlia, a well known DHT, used in real applications. Our work exposes the particularities of this system, notably its XOR-based distance metrics, and analytically studies what broadcasting techniques can be applied to it. A model that estimates node coverage as a function of the probability that individual messages reach their destination has been also developed. For validation, several broadcasting algorithms have been implemented and comprehensively evaluated, considering node coverage, messages to nodes ratio, latency and imbalance factor. Moreover, several techniques are proposed to enhance the bare protocols when adverse circumstances such as churn and failure rate conditions are present. These include redundancy, resubmissions or flooding, and also combinations of those. All have been implemented and fully tested. An analysis of the strengths and weaknesses of algorithms and additional techniques, and a discussion on the choices and compromises to make, depending on system characteristics or application priorities, is finally presented.     

A new dynamic counter-based broadcasting scheme for Mobile Ad hoc Networks

Broadcasting is an essential operation in Mobile Ad hoc Networks (MANETs) to transmit a message (data packet) from the sender to the rest of the network nodes. Although flooding is the simplest mechanism for broadcasting, where each node retransmits every uniquely received message exactly once, it is usually costly and results in serious redundancy, contention and collisions in the network. These problems are widely referred to as the broadcast storm problem. In the light of this, this study introduces a new counter-based broadcasting scheme to achieve efficient broadcasting in MANETs. This is achieved by using a counter-based scheme with a dynamic threshold to increase the successful delivery rate of packets and enhance the throughput of the network. Extensive simulation experiments have been conducted. Our results show that the new scheme outperforms the well known exiting schemes, namely the two counter-based broadcasting scheme and blind flooding.     

延迟容忍网络中自适应拥塞控制机制研究

由于延迟容忍网络（DTN）的不稳定连接和高延时特性,传统的拥塞控制方法并不适用于DTN。提出一种基于节点状态的自适应拥塞控制机制（ACC-NS）。为满足不同的服务质量需求,将网络中的消息分为普通消息和特殊消息,其中特殊消息要求更高的传输率。根据节点的拥塞程度将节点状态分为三个等级,每个节点根据自己所处的拥塞状态和当前缓存空间使用率自主决策消息的接收行为。将VACCINE和基于消息相遇计数方法进行结合,以清除冗余消息副本。将ACC-NS和另两种经典的路由协议进行对比,ACC-NS实现了更好的性能。     

Overload control for short message transfer in GPRS/UMTS networks

In the General Packet Radio Service (GPRS)/Universal Mobile Telecommunications System (UMTS) short message service (SMS) network, the serving GPRS support node (SGSN) stores the message in a queue until it is successfully transferred to the mobile device or its maximum waiting time expires. The queued message is forwarded to the new SGSN and is immediately removed from the waiting queue of the old SGSN, if the corresponding mobile device leaves the old SGSN area before the valid queueing time expires. Once the SGSN's buffer is full, all incoming messages must be discarded and retransmitted later. Under this situation, the messages, especially the forwarded messages, suffer from a longer delay before being successfully delivered. To prevent messages from being excessively delayed, this paper proposes an SGSN overload control scheme called the N-overload scheme. According to this scheme, a newly arriving message is discarded if the buffer is full upon its arrival. A forwarded message, however, is queued in an overload space of size N. Taking the forwarding and the expiration effects of queued messages into account, this paper also develops an analytical model to study the performance for the SGSN using the N-overload scheme. On the basis of the analysis, the optimal value of N is numerically determined so that the loss probability for the forwarded messages is minimized.     

An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks

Double-loop networks are widely used in computer networks. In this paper, we present an optimal message routing algorithm and an optimal fault-tolerant message routing algorithm for weighted bidirectional double-loop networks. The algorithms presented are novel, and they do not use routing tables. After a precalculation of O(log N) steps to determine network parameters, the algorithms can route messages using constant time at each node along the route. The algorithm presented can route messages in the presence of up to three faulty nodes or links. The fault-tolerant routing algorithm guarantees an optimal route in the presence of one node failure.     

DTN中基于二分散发和等待路由的自适应拥塞控制策略

针对二分散发和等待路由中报文被转发的特点,提出节点首先通过应答交换机制丢弃已被递交到信宿节点的报文,来减少网络中冗余报文的传输;当节点缓存完全占用又需存储新报文时,执行拥塞检测和拥塞避免操作,遍历缓存,找到缓存中拷贝数最小的报文将其丢弃（若此报文正在被传输则丢弃拷贝数次小的报文）直至有足够的缓存空间存储新接收到的报文。通过大量仿真实验及相关数据的分析与比较,说明该拥塞策略能显著提高递交率,减小开销,并对拥塞状况有更好的自适应能力。     

DTN中基于消息质量度和节点可信度的拥塞控制

DTN(Delay Tolerant Network)具有间歇性连接、资源有限以及拓扑结构随机动态变化等特点,因此会受到网络资源有限和网络拓扑不确定性的限制,极易产生网络拥塞。针对这一问题,提出了一种基于消息质量度和节点可信度的拥塞控制策略CCMQ(Congestion Control Based on Message Quality and Node Reliability in DTN)。该策略主要根据消息的质量度划分消息的优先级,在转发消息时,将优先级高的消息优先转发;在选择下一跳节点时,选择节点可信度高的节点进行消息的转发,并充分考虑中继节点自身的属性;在发生拥塞时,消息质量度小的消息被率先丢弃,同时增加了S-ACK消息确认删除机制,以释放节点的缓存空间,从而有效缓解节点拥塞。仿真结果表明,相比传统的拥塞控制算法,CCMQ在消息递交率、网络负载率和平均时延性能方面都有较大的提升。     

基于历史相遇间隔的机会网络路由协议

针对大多数机会网络路由协议在寻找端到端通信链路时不能很好地抓住节点社会性质的问题,提出一种基于历史相遇间隔(HICR) 协议的路由算法。HICR协议利用社会关系的特点,根据节点之间的历史相遇间隔判断它们的亲密程度,转发消息给离目的节点更亲近的节点,使得消息朝更靠近目的节点方向发送。仿真结果表明,该HICR协议在网络资源有限的的情况下,与Epidemic协议和Prophet协议相比,能获得更高的消息交付率。     

一种MANET环境下基于兴趣度的协同缓存策略

MANET网络中由于节点移动的随机性和无线链路的断连性,导致网络拓扑变化频繁,从而降低了数据可访问能力.提出一种基于兴趣度的协同缓存策略(IBCC).其主要思想是:针对节点转发的数据请求消息,引入ω-稳定节点集定义和兴趣度概念,定期挖掘ω-稳定节点集中具有相同兴趣度的数据形成预取集;针对回复的数据消息形成数据定位表,通过查找数据定位表将请求发送给同样拥有该数据但路由跳数较少的节点.该策略提高了在出现链路断接时节点对数据的访问能力.仿真实验结果证明该策略的有效性.     

An efficient network-wide broadcasting based on hop-limited shortest-path trees

We propose a technique for reducing the number of message duplicates during network-wide broadcasting in wired networks. The key feature of our proposal is that each node keeps the information on hop-limited shortest path trees whose roots are within a certain number of hops from each node. When receiving the message, each node generates its duplicates and forwards them to a subset of neighbors, which are on the hop-limited shortest path tree rooted at the message source. The information on hop-limited shortest path trees is stored in message forwarding table of each node. We show that the hop-limited shortest path tree can be constructed in a fully-distributed manner by simply using dummy message flooding or exchanging distance vectors with poisoned reverse. Our proposal can largely reduce the number of message duplicates compared with the flooding while it is more scalable than the global-shortest-path-tree-based delivery. We also note that it guarantees the full reachability in static conditions and the time to reach of the proposal is the same as that of the flooding or the global-shortest-path-tree-based delivery. Duplicate reduction effect of our proposal is theoretically evaluated and numerically examined by simulation experiments.     

受限网络中基于转发历史异步路由及中继数量研究

由于节点的移动性、稀疏链路和节点的不可靠,受限网络节点之间在大部分时间处于断开状态,现有的同步路由方法不能适用这种实际情况,所以必须从异步角度来考虑这类网络环境下的路由问题.文章完全从异步的角度思考无线自组织网中的路由问题,利用分组转发的历史信息智能做出路由决策,并研究中继节点数量对性能的影响,以减少由于复制大量分组而产生的网络流量.文章详细介绍了作者提出的方法,并通过仿真实验和一些相关算法进行比较,分析算法性能.