Virtual-Force-Based Geometric Routing Protocol in MANETs

Routing is the foremost issue in mobile ad hoc networks (MANETs). To guarantee delivery and improve performance, most position-based routing protocols, e.g., greedy-face-greedy (GFG), forward a message in greedy routing mode until the message is forwarded to a local minimum where greedy forwarding is impossible. They then switch to a less efficient mode known as face routing. Face routing requires the underlying network to be a planar graph which makes geometric routing only theoretically feasible. To remove this constraint, this paper tackles the local minimum problem with two new methods. First, we construct a virtual small-world network by adding virtual long links to the network to reduce the number of local minima. Second, we use the virtual force method to recover from local minima without relying on face routing. Combining these two methods, we propose a purely greedy routing protocol, the small-world iterative navigation greedy (SWING+) routing protocol. Simulations are conducted to evaluate SWING+ against existing geometric routing protocols. Simulation results show that SWING+ guarantees delivery, and that its performance is comparable to that of the state-of-the-art greedy other adaptive face routing (GOAFR+) routing protocol.     

Shortest-path routing in randomized DHT-based Peer-to-Peer systems

Randomized DHT-based Peer-to-Peer (P2P) systems grant nodes certain flexibility in selecting their overlay neighbors, leading to irregular overlay structures but to better overall performance in terms of path latency, static resilience and local convergence. However, routing in the presence of overlay irregularity is challenging. In this paper, we propose a novel routing protocol, RASTER, that approximates shortest overlay routes between nodes in randomized DHTs. Unlike previously proposed routing protocols, RASTER encodes and aggregates routing information. Its simple bitmap-encoding scheme together with the proposed RASTER routing algorithm enable a performance edge over current overlay routing protocols. RASTER provides a forwarding overhead of merely a small constant number of bitwise operations, a routing performance close to optimal, and a better resilience to churn. RASTER also provides nodes with the flexibility to adjust the size of the maintained routing information based on their storage/processing capabilities. The cost of storing and exchanging encoded routing information is manageable and grows logarithmically with the number of nodes in the system.     

A learning automata-based fault-tolerant routing algorithm for mobile ad hoc networks

Reliable routing of packets in a Mobile Ad Hoc Network (MANET) has always been a major concern. The open medium and the susceptibility of the nodes of being fault-prone make the design of protocols for these networks a challenging task. The faults in these networks, which occur either due to the failure of nodes or due to reorganization, can eventuate to packet loss. Such losses degrade the performance of the routing protocols running on them. In this paper, we propose a routing algorithm, named as learning automata based fault-tolerant routing algorithm (LAFTRA), which is capable of routing in the presence of faulty nodes in MANETs using multipath routing. We have used the theory of Learning Automata (LA) for optimizing the selection of paths, reducing the overhead in the network, and for learning about the faulty nodes present in the network. The proposed algorithm can be juxtaposed to any existing routing protocol in a MANET. The results of simulation of our protocol using network simulator 2 (ns-2) shows the increase in packet delivery ratio and decrease in overhead compared to the existing protocols. The proposed protocol gains an edge over FTAR, E2FT by nearly 2% and by more than 10% when compared with AODV in terms of packet delivery ratio with nearly 30% faulty nodes in the network. The overhead generated by our protocol is lesser by 1% as compared to FTAR and by nearly 17% as compared to E2FT when there are nearly 30% faulty nodes.     

移动自组织网络下的基本蚁群路由算法

针对移动自组织网络资源受限的特点和目前已有的蚁群路由算法比较复杂的问题,提出一种基本蚁群路由算法。通过对蚁群路由流程的分析,只维持基本的蚁群路由机制,不增加额外开销。详细讨论算法中信息素更新和信息素使用两项关键机制,并且通过模拟实验分析它们对性能的影响。实验结果表明,该算法能够以很低的开销取得与其他路由协议相近的性能。     

基于扩展环的Ad Hoc网络路由发现算法

针对传统的AODV路由协议采用全网络广播进行路由发现带来的路由开销较大问题,提出一种自适应的L跳扩展环路由搜索算法,并推导出L值的计算公式,节点在路由请求过程中能够根据以前搜索中获得的“先验”知识动态地调整搜索参数,进而计算下一步路由过程的最优跳数L,使搜索总是向着路由开销最小的方向进行。仿真结果表明,改进后的AODV协议能够降低路由开销,缩短路由发现过程的延时。     

On the Design of Link-State Routing Protocol for Connection-Oriented Networks

Link-state routing protocols are being increasingly used in modern communications networks. A salient feature of this class of routing protocols is that network connectivity and state information of all links are available to nodes for making routing decision. Two main components of a link-state routing protocol are an update mechanism and a routing algorithm. These components must be properly designed for efficient routing. Various alternatives are possible for each of these components leading to different scenarios for routing protocol. In this paper, we quantitatively examine the impact of these alternatives on network performance using call-by-call simulations. Our design objective is to reduce call blocking ratio without significantly increasing routing overhead. We also present a new signaling scheme that can be used in conjunction with link-state protocols. We show that, if properly designed, this scheme can enhance the network performance.     

Randomized dynamic route maintenance for adaptive routing in multihop mobile ad hoc networks

Several approaches have been proposed for designing multihop routing protocols in mobile ad hoc networks (MANET). Many of them adopt a method, called flooding, to discover a routing path. Due to the time-varying nature of the route in MANET, the discovered route needs to be dynamically maintained for optimality in terms of traffic load, hop-distance, and resource usage. It is easy to see that flooding incurs significant overhead and hence is inappropriate for the dynamic route maintenance. In this paper we propose a randomized, dynamic route maintenance scheme for adaptive routing in MANET. The scheme makes use of a nomadic control packet (NCP) which travels through the network based on a random walk, and collects its stopovers as a traversal record. The NCP uses the traversal record to probabilistically provide the nodes with clue for routing path updates. From the clue, the nodes can find the routing path update information that is up-to-date and optimal (less-loaded and shorter), thereby adapting to the dynamic network topology and traffic load conditions. We present an analytical model for measuring the effectiveness of NCP in terms of its frequency of visits and probability of finding the clue from the NCP traversal record. The proposed randomized scheme serves as a routing protocol supporting layer and can be easily applied with minimum modifications to the existing on-demand routing protocols such as AODV and DSR. In our experimental study, we modified the AODV protocol to maintain routing paths using NCPs’ traversal record. Simulation results show that NCPs help the routing protocol to notably reduce average end-to-end packet delay with increased route optimality and better control on traffic congestion.     

无线 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.     

一种支持任务合并的交换网络实时调度策略

通过分析现有网络通信和实时系统的调度算法,在实时调度算法LSF(Least Start First)的基础上,提出支持任务合并的交换式网络实时调度策略TC-LSF(Tasks Combining-Least Start First)来保证任务在网络通信中的实时性.该算法使用任务合并策略对多个通信任务进行合并,从而节省相...     

移动自组网络中基于启发式环索算法的Anycasting路由的研究

移动无线自组网络（Mobile Ad Hoc Networks）是一种新型的无线网络,网络中不需要固定通信设施的支持,具有很高的灵活性．任播路由（Anycasting Routing）在移动无线自组网络中有着十分重要的潜在应用．该文提出的基于启发式环索算法的Anycasting路由在路由请求过程中能够根据以前搜索中获得的“先验”知识动态地调整搜索的参数,使搜索总是向着“最可能”的方向进行．模拟实验表明,采用启发式环索算法的混合式Anycasting路由在不影响路由正确性的情况下能极大地减少网络中无用的路由请求消息,从而提高网络的整体性能．     

一种SRIO网络负载均衡最短路径路由算法

在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息,以路由跳数定义路由的成本,根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载,采用负载均衡算法从K最短路径中进行选路,建立SRIO网络最短路径约束的负载均衡路由。实验结果表明,与深度遍历路由算法、最小跳数算法相比,该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现,能够有效提升SRIO路由网络的稳定性。     

Bi-LCQ: A low-weight clustering-based Q-learning approach for NoCs

Network congestion has a negative impact on the performance of on-chip networks due to the increased packet latency. Many congestion-aware routing algorithms have been developed to alleviate traffic congestion over the network. In this paper, we propose a congestion-aware routing algorithm based on the Q-learning approach for avoiding congested areas in the network. By using the learning method, local and global congestion information of the network is provided for each switch. This information can be dynamically updated, when a switch receives a packet. However, Q-learning approach suffers from high area overhead in NoCs due to the need for a large routing table in each switch. In order to reduce the area overhead, we also present a clustering approach that decreases the number of routing tables by the factor of 4. Results show that the proposed approach achieves a significant performance improvement over the traditional Q-learning, C-routing, DBAR and Dynamic XY algorithms.     

Concurrent face traversal for efficient geometric routing

We present a concurrent face routing CFR algorithm. We formally prove that the worst case latency of our algorithm is asymptotically optimal. Our simulation results demonstrate that, on average, the path stretch, i.e., the speed of message delivery, achieved by CFR is significantly better than by other known geometric routing algorithms. In fact, it approaches the shortest possible path. CFR maintains its advantage over the other algorithms in pure form as well as in combination with greedy routing. CFR displays this performance superiority both on planar and non-planar graphs.     

一种自适应的基于流言机制的AODV路由算法

多跳的无线连接、动态的网络拓扑和有限的带宽是移动Adhoc网络的主要特点,这些特点对移动Adhoc网络的路由协议提出了诸多挑战。在Adhoc路由算法中使用流言(gossip)机制不仅可以减少路由开销,同时还能提高路由效率和可靠性。文章提出了一种自适应的基于流言机制的AODV路由算法,并将其与原来的基于流言机制的AODV路由算法进行了仿真性能比较。     

Ad Hoc移动网络多路径研究

在Ad Hoc移动网络中,由于结点的移动性,网络拓扑结构的易变性,路由成为研究的热点和难点。当前AdHoc路由协议一般都是单路径协议。然而由于多路径路由方式可以大大减少路由开销,提高数据传输率,减少网络拥塞,越来越多的研究表明,它将是未来Ad Hoc网络路由的主要方式。本文介绍了几种典型的多路径路由协议,并对这些多路径协议进行评价,对其性能进行比较,然后介绍多路径协议在QoS、能源和安全方面的应用,最后指出未来多路径研究的关键问题。     

Exploiting Voronoi diagram properties in face segmentation and feature extraction

Segmentation of human faces from still images is a research field of rapidly increasing interest. Although the field encounters several challenges, this paper seeks to present a novel face segmentation and facial feature extraction algorithm for gray intensity images (each containing a single face object). Face location and extraction must first be performed to obtain the approximate, if not exact, representation of a given face in an image. The proposed approach is based on the Voronoi diagram (VD), a well-known technique in computational geometry, which generates clusters of intensity values using information from the vertices of the external boundary of Delaunay triangulation (DT). In this way, it is possible to produce segmented image regions. A greedy search algorithm looks for a particular face candidate by focusing its action in elliptical-like regions. VD is presently employed in many fields, but researchers primarily focus on its use in skeletonization and for generating Euclidean distances; this work exploits the triangulations (i.e., Delaunay) generated by the VD for use in this field. A distance transformation is applied to segment face features. We used the BioID face database to test our algorithm. We obtained promising results: 95.14% of faces were correctly segmented; 90.2% of eyes were detected and a 98.03% detection rate was obtained for mouth and nose.     

CoCONet: A collision-free container-based core optical network

Electrical-to-optical domain conversions and vice versa (denoted by O/E/O conversions) for each hop in optical core transport networks impose considerable capital and financial overhead on the providers. In this paper, we propose a full-mesh topology driven core network with a central scheduler that handles the task of signaling and coordination among slot transmissions for every hop to eliminate such O/E/O conversions. We introduce the concept of a container as a macro data unit that forms a separate layer in the protocol stack above the optical layer. A FAST centralized scheduling algorithm is proposed based on a preemptive scheduling technique that can ensure that there are no collisions between the containers. We also analyze the complexity of this algorithm. Next we design the logical architecture for the core and edge switches following the de facto policy of moving the complexity to the edge. We also designed a hierarchical architecture for the edge switch and provide the respective block diagrams. To get a more concrete design prototype, we further proposed a generic (vendor independent) physical architecture for a single port of the switch considering SONET/SDH on the access side. Moreover, we develop a concise delay model for the containers to analyze the packet arrival process and derive the optimal container size, based on the link speed. Finally, we present some simulation results to study the performance of the algorithms and models proposed in our work.     

移动Ad hoc网络中路由协议的能耗-性能联合比较

移动Adhoc网络是一种完全由移动主机构成的网络,网络拓扑易变,带宽,能源有限是其的突出特点。因此,高效路由协议的设计是Adhoc网络的基本问题之一。目前提出的各种路由协议各有它们的特点和优点。但是对这些路由协议的评价仅仅局限于单纯的网络性能或者能量消耗。该文在引入一种性能—能耗联合度量的基础上,对常见的DSR、AODV、TORA和DSDV四种路由协议进行了比较和评价。     

一种稳定的按需QoS路由协议

一个ad hoc网络是一个多跳无线网络,网络中的节点互相通信而不依赖于预先架设的固定基础设施，选路协议中的频繁的路由失败和高控制开销致使系统性能降低.本文提出了一个稳定的分布式Ad hoc路由协议，该协议支持QoS选路用于多媒体应用．     

基于回归置信度的多尺度精确人脸检测

在大多数受限情况下人脸检测已经有了许多有效方案,但对于人脸尺度变化极大、小人脸,以及模糊、遮挡、光照等非受限环境的人脸检测问题,仍面临更多挑战。针对以上问题,提出一种多尺度卷积神经网络模型。在R-FCN网络的基础上进行改进,以多尺度特征替代单一特征,使网络对多尺度信息更加敏感,在预测阶段同时输出分类置信度与回归置信度,改进非极大值抑制(non-maximum suppression,NMS)算法,提出基于回归置信度的NMS算法。在WIDER FACE数据集上训练模型,在FDDB与WIDER FACE人脸评测库进行实验,实验结果表明,召回率、准确率等指标均优于其它人脸检测算法。