数据链中面向可靠传输的泛洪算法及应用分析

数据链多点中继(MultiPoint Relay,MPR)泛洪是一个多目标、多约束的网络规划问题.现有的泛洪算法未考虑在多种QoS(Quality of Service)约束下,尽量实现MPR集节点数最小和传输可靠性最大这两个目标.针对优先考虑目标的不同提出了两种面向可靠传输的启发式优化泛洪算法:RA-MPR-N和RA-MPR-R,前者选择尽量少的一跳邻节点以覆盖二跳范围内所有的节点,后者能最高程度保证传输可靠性.理论分析和试验结果表明,两种算法分别在其优先考虑的目标上得到了比较满意的结果.     

一种面向可靠传输的数据链中继策略研究

数据链采用泛洪中继(Flood Relay)策略实现信息在全网的广播,该策略通过冗余发送提高传输的可靠性,但是在网络节点密集的情况下,将引起过量的泛洪开销,因此被认为是低效的。分析了数据链的双时隙中继泛洪模式,并在此基础上提出了一种面向可靠传输的MPR(RA-MPR)策略,该策略保证在满足可靠性约束和传输时延约束等条件下,根据节点的主控关系、节点的可靠度以及节点间的邻接关系进行优选中继节点,构成具有中继功能的临时性的核心网络,该网络随着拓扑结构的变化、电磁环境的变化、节点的毁伤以及主控关系的变化而动态变化。通过算法分析和仿真,比较了该策略在不同网络规模和传输半径条件下的性能,分析结果显示该策略不仅降低了泛洪开销,而且保证了报文传输的可靠性。     

车联网中多跳广播转发节点选择研究

在车载自组织网络中(VANET),大部分应用采用多跳广播来交换道路交通信息,其中最典型的为泛洪广播,但是随着车辆和节点的增多泛洪广播会引起广播风暴,导致信道阻塞。结合模糊逻辑,提出一种基于接收节点的多跳广播方案,依靠接收节点的覆盖范围、信道忙闲比和移动因素,由模糊逻辑系统决定当前节点是否具备转发资格。通过于其它方案的仿真对比验证,所提出的方案在投递率与时延方面具有更好的性能,可有效提高信道利用率,降低广播风暴风险。     

VANET中一种基于概率转发的AODV路由协议

泛洪被作为实现广播通信的最简单的技术,广泛应用于车联网VANET(vehicular Ad Hoc network)路由.然而,由于VANET中节点的快速移动以及网络拓扑动态变化,简单的泛洪容易导致大量的冗余数据包,并引发广播风暴.为此,以典型的按需式距离矢量路由协议AODV (Ad Hoc on-demand distance vector)为基础,提出基于概率转发的AODV路由协议,记为AODV_P.AODV_P协议利用概率转发机制替代AODV中的泛洪.节点利用距离、密度信息计算转发概率,并依据转发概率设置计时器.计时器时间越短,成为下一跳转发节点的可能性越大.仿真结果表明,提出的AODV_P能够有效降低冗余数据包,缓解广播风暴问题.与AODV协议相比,AODV_P在传输时延、数据包传输率方面得到了有效提高.     

一种基于移动Agent的Ad Hoc可信网络架构

ad hoc网络是一组具有路由和转发功能的移动节点组成的一个多跳的临时性自治系统,是一种无中心的无线网络,现有的安全策略都是从某一方面提出改进方法;基于系统论思想方法,提出了一种基于移动Agent 的ad hoc可信网络架构,并进行了初步分析.     

PVPS：P2P点播中的分布式搜索算法

PVPS系统针对P2P点播服务实现中的源节点搜索问题给出了一种实用高效的解决策略.PVPS在节点结构组织上采用了基于节目内容分簇的网状结构,每个分簇中由代理节点进行管理.在簇间搜索过程中,PVPS采用改进的启发式MPR算法、基于邻居优先级的自裁减策略和基于消息冗余度的剪枝策略对非结构化搜索进行多次优化,提高了搜索的效率.理论分析和实验结果表明,PVPS服务体系采用的搜索策略在性能上优于现有策略,在大型网络中具有良好的稳定性和扩展性.     

基于传输范围覆盖的无线传感器网络广播算法

广播在无线传感器网络中具有广泛的应用.泛洪广播虽然简单,但极为耗能.基于概率、基于计数以及基于位置等广播算法不使用任何邻节点信息,简单但性能改善有限.MPR以及多数基于连通支配集的广播算法利用2-hop邻节点信息计算转发节点集,虽然获得了较好的性能,但需更多的通信开销以获取和维护2-hop邻节点信息.为减少转发节点并节约通信开销,较好的实现无线传感器网络广播,本文利用1-hop邻节点信息提出了一种基于传输范围覆盖的广播算法TRCB.算法的主要思想是如果发送节点U的1-hop邻节点V被U和不包括节点V的其余1-hop邻节点集S覆盖,则节点V将不参与转发.分析与仿真表明,TRCB有效减少了冗余转发节点,从而节约了无线传感器网络能耗;并且利用1-hop邻节点信息,具有通信开销小、适应网络拓扑变化的特点;且其性能优于同样利用1-hop邻节点信息的边缘转发算法EFB.     

基于中继节点的多跳CR Ad Hoc网络广播算法

针对避免广播冲突的CR Ad Hoc网络的分布式广播协议广播成功率低和基于选择性广播信道集的低延迟广播算法广播冲突率高的问题，提出基于中继节点选择的多跳CR Ad Hoc网络广播算法。根据节点可用信道集的大小和基于邻居度的转发概率选取中继节点，并对相应中继节点的可用信道集随机左移，在保证一定广播成功率、广播时延和广播冲突率的前提下，降低节点转发率，减少网络中的冗余信息；建立综合评价函数对广播算法的综合性能进行了定量分析；给出广播冲突概率推导。仿真结果表明，该算法与分布式广播协议相比，提高了广播成功率，降低了广播时延；与低延迟广播算法相比，降低了节点转发率和广播冲突概率。根据综合评价函数，该广播算法的综合性能更好。     

基于混合策略的动态多跳无线网络路由算法

针对动态多跳无线网络中节点的动态变化和数据包的转发冗余问题,提出了一种基于MPR (multipoint relays)和评价函数的混合动态路由策略.确定节点的MPR集,并基于评价函数对MPR集中的节点排序.无线通信时,节点根据本地存储的MPR集将数据包转发给传递成功率高的节点,若MPR中没有可成功转发节点的信息,则随机选择MPR集外的节点,定向转发与随机转发相补充使数据包能在较短的时间内准确的到达目的节点.仿真结果表明,该路由策略能有效的降低平均时延和丢包率,提高了传输率.     

高密度且信号涵盖范围不规则的WSN广播算法研究

广播在无线传感器(WSN)协议中有着广泛的应用,但简单泛洪广播将带来广播风暴问题,在节点稠密的网络中尤为严重.借鉴DCB(double-covered broadcast)算法的节点双重覆盖思想,提出适合在节点高密度且信号涵盖范围不规则无线传感器网络的改进广播算法,简称为SDCB(sensor double-covered broadcast)算法.算法考虑在节点间不对称链路存在情况下,有效利用局部邻居节点信息减轻广播风暴,使广播有效进行,同时考虑低能量节点的处理来平衡网络耗能.最后在NS2平台上对SDCB算法进行仿真,并与DCB算法进行分析、比较.仿真结果表明,SDCB算法有较高的广播送达率、较低的节点转发率以及较低的广播时延.     

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.     

A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks

Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm     

Loop-free hybrid single-path/flooding routing algorithms withguaranteed delivery for wireless networks

In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer     

Performance analysis of broadcast protocols in ad hoc networks based on self-pruning

Self-pruning is an effective scheme for efficient broadcasting in ad hoc wireless networks. In a self-pruning broadcast protocol, a node may not forward a broadcast packet if a certain self-pruning condition is satisfied based on the neighborhood information. In a static network with an ideal MAC layer, only a subset of nodes forward the broadcast packet and still guarantee the complete network delivery. Various protocols have been proposed with different self-pruning conditions. Recently, a generic self-pruning protocol was proposed by Wu and Dai (2003), which combines the strength of previous conditions and is more effective. In this paper, we first propose an enhanced version of the generic protocol, which is more elegant in interpreting existing protocols and has a simpler correctness proof. Then, we evaluate the performance of the family of self-pruning protocols under various network situations with ns2. The objective is to observe the efficiency and reliability of these protocols as a function of network density, congestion, and mobility, and provide a guideline of implementation in the "real world". Our performance analysis reveals that the protocol reliability is barely affected by packet collision. However, most self-pruning protocols suffer from low delivery ratio in highly mobile networks. We further explore various techniques that improve the delivery ratio and show that both high efficiency and reliability can be achieved in highly mobile networks.     

高效的MPR选择算法

OLSR(optimized link state routing)协议中最重要的功能之一是多点中继(multi point relays, MPR)节点的选择,该协议中路由的计算就要依靠MPR选择相关表项。传统的MPR算法只是减少了同一区域内相同消息的泛洪,并没有考虑网络中新加入节点获取全网拓扑信息的时间问题。针对该问题进行了研究并提出一种高效的MPR选择算法,该算法有三个步骤:首先减少了部分拓扑控制(topology control, TC)消息冗余问题;然后选择MPR时考虑有效覆盖面积让新加入的节点获取全网拓扑信息所需的时间缩短;最后考虑到移动性对网络拓扑的影响,基于历史信息预估下一时刻节点的位置,增强了链路的稳定性。通过仿真,将改进的MPR算法与传统算法比较,端到端时延降低,数据包的传递成功率也有所提升。     

Sparse structures for searching and broadcasting algorithms over internet graphs and peer-to-peer computing systems

In a broadcasting problem, a message is sent from a source to all the other nodes in the network. Blind flooding is a classical mechanism for broadcasting, where each node retransmits received message to all its neighbors. Despite its important advantages, an increase in the number of requests or the network size or density produces communication overheads that limit the scalability of blind flooding, especially in networks with dynamic topologies. Theoretically optimal solution is based on minimal spanning trees (MST), but its construction is expensive. We discuss here protocols based on local knowledge and newly proposed sparse structures. In weighted RNG (Relative Neighborhood Graph), messages are forwarded only on links which are not the ‘longest’ in any triangle. In weighted RNGQ, messages are forwarded to links which are not the longest in any triangle or quadrangle. Each node constructs weighted MST based on its 2-hop knowledge. Weighted LMST (Localized LMST) preserves only edges that are selected by both endpoints, and messages are forwarded on these links. Any available metric, such as delay, reliability, reputation etc. can be used as weight. Analysis and simulation show that weighted RNG performs better than existing Flooding and Rumor Mongering (or Gossip) schemes. The parameterless weighted LMST, MST, RNG and RNGQ (RNG over Quadrangle) based broadcasting schemes are compared, showing overall advantage for LMST. We also hint that a number of existing protocols can be simplified by applying concept from this article.     

Identifying influential nodes in weighted complex networks using an improved WVoteRank approach

Influence maximization is an important research problem in the field of network science because of its business value. It requires the strategic selection of seed nodes called “influential nodes,” such that information originating from these nodes can reach numerous nodes in the network. Many real-world networks, such as transportation, communication, and social networks, are weighted networks. Influence maximization in a weighted network is more challenging compared to that in an unweighted network. Many methods, such as weighted degree rank, weighted h-index, weighted betweenness, and weighted VoteRank techniques, have been used to order the nodes based on their spreading capabilities in weighted networks. The VoteRank method is a popular method for finding influential nodes in an unweighted network using the idea of a voting scheme. Recently, the WVoteRank method was proposed to find the seed nodes; it extends the idea of the VoteRank method by considering the edge weights. This method considers only 1-hop neighbors to calculate the voting score of every node. In this study, we propose an improved WVoteRank method based on an extended neighborhood concept, which takes the 1-hop neighbors as well as 2-hop neighbors into account for the voting process to decide influential nodes in a weighted network. We also extend our proposed approach to unweighted networks. We compare the performance of the proposed improved WVoteRank method against the popular centrality measures, weighted degree, weighted closeness, weighted betweenness, weighted h-index, and weighted VoteRank on several real-life and synthetic datasets of diverse sizes and properties. We utilize the widely used stochastic susceptible–infected–recovered information diffusion model to calculate the infection scale, the final infected scale as a function of time, and the average distance between spreaders. The simulation results reveal that the proposed method, improved WVoteRank, considerably outperforms the other methods described above, including the recent WVoteRank.

     

EF-MPR,a new energy eFficient multi-point relay selection algorithm for MANET

MultiPoint Relay (MPR) selection algorithm is a flooding technique for propagating a broadcast message inside an ad-hoc network which reduces the number of unnecessary broadcast messages in order to save more energy in the network, minimize the number of packet collisions, and speed up the propagation time. In this paper, we demonstrate that MPR selection is an application of Set Covering Problem (SCP). A few optimization methods are developed in this work to find the optimum solution including Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA), and a new greedy algorithm. Extensive simulations are set up to evaluate the developed methods. The new algorithm is named Energy eFficient MPR or EF-MPR in short. The simulation results show that EF-MPR can reduce the number of MPR nodes up to 19%. Moreover, EF-MPR algorithm reduces the power-consumption of network up to 12% and speed up the propagation time by 9%.     

基于信任机制的机会网络安全路由决策方法

提出一种基于信任机制的机会网络安全路由决策方法TOR,该方法在节点中引入信任向量的数据结构,记录节点携带消息能力的信任度.采用层状硬币模型和数字签名机制,在消息传递过程中将节点签名的转发证据动态捆绑到消息包上,依靠消息携带方式实现证据链的采集.周期性地将具有签名和时间戳的信任向量表通过洪泛方式反馈到网络中,在每个节点,迭代形成一个由多维行向量集组成的只读可信路由表TRT,作为选择下一跳节点和副本分割策略的决策依据.在节点相遇时,选择信任度比自身大的作为下一跳转发节点,消息沿着信任梯度递增的方向传递.实验结果表明：与现有路由算法相比,TOR算法能够有效抑制恶意节点和自私节点的破坏行为,且具有较高的消息传递成功率和较低的消息转发平均时延,对缓存空间和计算能力要求较低.