Multihop lightwave networks: a comparison of store-and-forward andhot-potato routing

The achievable aggregate capacity for a variant of the basic multihop approach in which minimum distance store-and-forward routing is replaced by a hot-potato routing algorithm is determined. With hot-potato routing, all packets simultaneously arriving at a given node and not intended for reception at that node are immediately placed onto the outbound links leaving that node; if two or more packets contend for the same outgoing link to achieve a minimum distance routing, then all but one will be misrouted to links which produce longer paths to the eventual destination. Attention is confined to the development of an analytical methodology for finding the probability distribution of the number of hops with hot potato routing for symmetric networks under uniform traffic load. Results show that the maximum throughput achievable with hot-potato routing can be as low as 25% of that for store-and-forward routing, and that the relative degradation increases as the number of nodes grows larger. This implies that the link speed up needed to produce a significant overall capacity advantage with hot potato should be at least a factor of 10     

Connectivity analysis of one-dimensional ad-hoc networks

Application and communication protocols in dynamic ad-hoc networks are exposed to physical limitations imposed by the connectivity relations that result from mobility. Motivated by vehicular freeway scenarios, this paper analyzes a number of important connectivity metrics for instantaneous snapshots of stochastic geographic movement patterns: (1) The single-hop connectivity number, corresponding to the number of single-hop neighbors of a mobile node; (2) the multi-hop connectivity number, expressing the number of nodes reachable via multi-hop paths of arbitrary hop-count; (3) the connectivity distance, expressing the geographic distance that a message can be propagated in the network on multi-hop paths; (4) the connectivity hops, which corresponds to the number of hops that are necessary to reach all nodes in the connected network. The paper develops analytic expressions for the distributions and moments of these random variables for general stationary MAP processes on a one dimensional space. The numerical results compare bursty vehicular traffic with independent movement scenarios described by a Poisson process, illustrate in examples the impact of a random communication range, and demonstrate the usefulness of MAP processes via comparison with vehicular simulation traces.     

Performance analysis of relative location estimation for multihop wireless sensor networks

In this paper, we present new analytical, simulated, and experimental results on the performance of relative location estimation in multihop wireless sensor networks. With relative location, node locations are estimated based on the collection of peer-to-peer ranges between nodes and their neighbors using a priori knowledge of the location of a small subset of nodes, called reference nodes. This paper establishes that when applying relative location to multihop networks the resulting location accuracy has a fundamental upper bound that is determined by such system parameters as the number of hops and the number of links to the reference nodes. This is in contrast to the case of single-hop or fully connected systems where increasing the node density results in continuously increasing location accuracy. More specifically, in multihop networks for a fixed number of hops, as sensor nodes are added to the network the overall location accuracy improves converging toward a fixed asymptotic value that is determined by the total number of links to the reference nodes, whereas for a fixed number of links to the reference nodes, the location accuracy of a node decreases the greater the number of hops from the reference nodes. Analytical expressions are derived from one-dimensional networks for these fundamental relationships that are also validated in two-dimensional and three-dimensional networks with simulation and UWB measurement results.     

Weakly versus strongly multihop space-division optical networks

Transparent multihop optical networks suffer from the accumulation from node to node of crosstalk and amplified spontaneous emission noise, which may severely degrade the quality of received signals. It is thus important to keep the number of intermediate hops as low as possible. This paper compares two single-wavelength cell-switching space-division optical networks that employ deflection routing. The first has a well-known Manhattan street (MS) distributed topology. The mean internodal distance of this network is approximately the square root of the number of nodes. We term this network as strongly multihop. The second has a centralized star topology: the star is a multistage space-division photonic switch with limited buffers. Deflected cells delivered to the wrong user are transparently rerouted to the star. This network is intrinsically single-hop and gradually becomes multihop because of deflections. We term this network as weakly multihop. As the carried traffic increases, the link load increases much more rapidly in the strongly multihop topology, and so do both the crosstalk level per hop and the number of hops caused by deflections. For the same carried traffic, the accumulated crosstalk and spontaneous emission levels in a well-designed star-based network are much lower than in a strongly multihop network. Hence, lower packet error rates and lower delay jitter are expected for the centralized network. Moreover, for both networks, a simple frequency sweeping technique is shown to substantially reduce the dominant signal-crosstalk beat, thus allowing network operation with switch crosstalk factors as low as -20 dB     

Multiconfiguration multihop protocols: a new class of protocols forpacket-switched WDM optical networks

Wavelength-division multiplexing (WDM) local-area networks based on the optical passive-star coupler have traditionally been classified as being either single-hop or multihop. A single-hop network provides a direct connection between the source and the destination of a packet during the packet transfer duration, but may require some amount of coordination between the nodes which may involve tuning of the transmitters or receivers at each node. Since the time required to tune a tunable optical transmitter or receiver may be high, a single-hop network may incur significant overhead. On the other hand, a typical multihop network requires little or no tuning, but a packet may traverse a number of intermediate nodes between the source and destination nodes. Each hop incurs additional queueing delays at each node and also increases the overall load on each link and on the network. In this paper, we propose a new class of multiconfiguration multihop protocols (MMPs) which use tunable transmitters and receivers to cycle through a number of configurations which together make up a multihop logical topology. This class of protocols offers a trade-off between the tuning required in a single-hop network and the number of hops required in a multihop network. We present a generalized framework for comparing the proposed protocols with existing single-hop and multihop protocols, and we show that these protocols may offer significant performance gains for systems with high tuning delays and a limited number of transmitters and receivers at each node     

An improvement of DV-Hop localization algorithm for wireless sensor networks

An improved DV-HOP localization algorithm is proposed based on the traditional DV-HOP localization algorithm in the paper. There will be a big error that using the nearest anchor node’s average hop distance instead of the average hop distance of all the anchor nodes that involved in the localizing in the traditional DV-HOP localization algorithm. Therefore, the improved algorithm introduces threshold M, it uses the weighted average hop distances of anchor nodes within M hops to calculate the average hop distance of unknown nodes. In addition, the positioning results are corrected in the improved algorithm. The simulation results show that the new localization algorithm effectively improves the positioning accuracy compared with the traditional DV-HOP localization algorithm, it is an effective localization algorithm in the wireless sensor networks.     

Vehicle density based multihop broadcast protocol in VANET

In vehicular ad hoc networks (VANET), the medium access control (MAC) protocol was of crucial importance to provide time-critical multihop broadcast. Contemporary multihop broadcast protocols in VANET usually choose the farthest node in broadcast range as the forwarder to reduce the number of forwarding hops. However, it was demonstrated that the farthest forwarder may experience long contention delay in case of high vehicle density. An IEEE 802.11p-based multihop broadcast protocol vehicle density based forwarding (VDF) was proposed, which adaptively chose the forwarder according to the vehicle density. The evaluation results in safety warning and online game applications show that, VDF could shorten broadcast delay by achieving the proper trade-off between the contention delay and coverage speed.     

Exploiting Contact Spatial Dependency for Opportunistic Message Forwarding

The movement of real users often follows patterns that can be characterized by certain statistical metrics of the contacts. Such metrics are useful for routing decisions, especially in sparse mobile ad hoc networks where node connectivity is opportunistic and messages are delivered using store-carry-forward routing. Past analysis on real-world data traces indicates that human behaviors affect the node contact pattern and spatial dependency exists among mobile nodes. A new metric called the expected dependent delay that characterizes the expected delay of a contact dependent on the previous hop is proposed. It characterizes the spatial dependency between neighboring contact pairs and reflects the regularity in node movement. In sparse opportunistic mobile ad hoc networks, a good approximation of the expected delay of a multihop path can be derived as the sum of the expected delay of the first hop and the expected dependent delays of later hops. We apply the proposed path-delay estimation to end-to-end routing. Simulation results show that compared with routing schemes that consider only the delivery probability or the expected delay, the proposed scheme can reduce the message delay significantly, when the network is sufficiently sparse and the spatial dependency is quantitatively constant over time. Moreover, the proposed method is tractable and can be easily implemented in combination with other routing techniques such as multipath routing and per-contact routing.     

定位算法在传感器网络中的改进策略

研究节点定位技术是传感器网络中的一个重要课题。针对DV-Hop定位算法适应节点均匀分布的网络这一特性,为了减小DV-Hop定位算法的定位误差,提出了节点的部署策略;针对平均每跳距离在求不同跳数的节点之间的距离时有着不同程度的影响,为了提高待定位节点的定位精度,提出了距离修正值策略。经过以上处理之后,得到了更加准确的平均每跳距离的估计值。实验表明,改进后的算法不仅提高了定位精度,同时也改善了定位的稳定性。     

Energy‐efficient multihop routing in WSN using the hybrid optimization algorithm

The technical growth in the field of the wireless sensor networks (WSNs) has resulted in the process of collecting and forwarding the massive data between the nodes, which was a major challenge to the WSNs as it is associated with greater energy loss and delay. This resulted in the establishment of a routing protocol for the optimal selection of the multipath to progress the routing in WSNs. This paper proposes an energy‐efficient routing in WSNs using the hybrid optimization algorithm, cat–salp swarm algorithm (C‐SSA), which chooses the optimal hops in progressing the routing. Initially, the cluster heads (CHs) are selected using the low‐energy adaptive clustering hierarchy (LEACH) protocol that minimizes the traffic in the network. The CHs are engaged in the multihop routing, and the selection of the optimal paths is based on the proposed hybrid optimization, which chooses the optimal hops based on the energy constraints, such as energy, delay, intercluster distance, intracluster distance, link lifetime, delay, and distance. The simulation results prove that the proposed routing protocol acquired minimal delay of 0.3165 with 50 nodes and two hops, maximal energy of 0.1521 with 50 nodes and three hops, maximal number of the alive nodes as 39 with 100 nodes and two hops, and average throughput of 0.9379 with 100 nodes and three hops.     

MDPF: Minimum Distance Packet Forwarding for Search Applications in Mobile Ad Hoc Networks

This paper introduces a message forwarding algorithm for search applications within mobile ad hoc networks that is based on the concept of selecting the nearest node from a set of designated nodes. The algorithm, which is called Minimum Distance Packet Forwarding (MDPF), uses routing information to select the node with the minimum distance. The goal of the proposed algorithm is to minimize the average number of hops taken to reach the node that holds the desired data. Numerical analysis and experimental evaluations using the network simulation software ns2 were performed to derive the lower and upper bounds of the confidence interval for the mean hop count between the source node of the data request, on one hand, and the node that holds the desired data and the last node in the set of search nodes, on the other hand. In the experimental evaluation, the performance of MDPF was compared to that of Random Packet Forwarding (RPF) and Minimal Spanning Tree Forwarding (MSTF). The results agreed with the numerical analysis results and demonstrated that MDPF offers significant hop count savings and smaller delays when compared to RPF and MSTF.     

Simple star multihop optical network

A new multihop wavelength division multiplexed (WDM) optical network with two wavelengths per node that can give the maximum throughput and minimum delay is proposed. It is called a “simple star” multihop network. This network has good characteristics in traffic balance and minimum average number of hops. Furthermore, unlike most existing networks, it does not impose an upper limit to the number of nodes     

An all-optical network architecture

A novel photonic network, MATRIX (for multi-wavelength all-optical transparent information exchange), is proposed in this paper. The all-optical multihop network supports wavelength continuity and provides a very high network capacity. Spatial reuse of wavelengths as well as the multiplicity of fibers in optical fiber cables are exploited and enable the interconnection of N² network nodes with merely N wavelengths. The node structure is simple since neither tunable devices nor wavelength converters are required. Packets are routed through the network by photonic fast packet switching as well as by wavelength and experience a maximum hop number of two. Multiple optical paths between any pair of nodes provide a good network survivability     

Vehicular node positioning based on Doppler-shifted frequency measurement on highway

Vehicular node positioning needs to be quick and precise on highway for safety consideration. In this paper, we present a novel and practical vehicular node positioning method which can achieve a higher accuracy and more reliability than the existing global-positioning-system-based positioning solutions by making use of Doppler-shifted frequency measurements taken by vehicular node itself. This positioning method uses infrastructure nodes which are placed on the roadside every several kilometers as radiation sources to estimate the relative distances of vehicle to the infrastructure node. Through coordinate conversion, we get the absolute coordinates of vehicular node based on known absolute coordinates of infrastructure node. We also analyze the optimal distance of neighbor infrastructure nodes in order to ensure a high accuracy. In addition, simulation results demonstrate that the accuracy of our method with Extended Kalman Filtering (EKF) is superior to the method without EKF.     

改进人工免疫算法优化的DV-Hop节点定位算法

由于无线传感器网络连通性不合理,导致计算待测节点与已知节点间距离时存在误差。为此,提出一种改进的人工免疫算法(AIA)优化DV-Hop未知节点坐标。首先对原平均跳距加权,其次利用网络中信标节点间距离产生的偏差构造跳距校正值得到最终的全网平均跳距。最后在计算待测节点坐标时引入AIA,针对AIA易陷入局部最优以及收敛速度过慢的问题,在局部搜索过程中采用高斯变异方法对AIA进行改进,扩大搜索范围,得到优化的待测节点坐标。经Matlab仿真证明,与原DV-Hop算法相比,改进后的算法在节点总数、信标节点比例以及通信半径三方面平均定位误差降低了近15%左右,具有较高的定位精度和较好的定位稳定性,同时也改善了算法的收敛性。     

A Connectivity-Based Multi-Lane Routing Optimization Algorithm in Vehicular Communication

This paper proposed a connectivity-based multi-lane geographic routing protocol (CGRP) for vehicular ad hoc networks. The proposed CGRP is based on an effective selection of road intersections through which a package must pass from source to destination. The cooperative connectivity probability and delay are taken into consideration when choosing the most suitable path for delay-sensitive safety traffic. Analytical expressions for cooperative connectivity probability is derived based on a three-lanes path model. Geographical forwarding is used to transfer packets between any two intersections on the path, reducing the path sensitivity to individual node movements. Furthermore, forwarding packets between two adjacent intersections also depend on geographic location information. Neighbor nodes’ priority are assigned according to position, speed, direction and other factors. Node with the highest priority will be selected as the next hop. Numerical and simulation results show that the proposed algorithm outperforms the exsiting routing protocols in terms of the end-to-end delay and the number of hops with a little cost of routing overhead in city environments.     

Anchor‐free distance estimation: A new approach to distance estimation for multihop ad hoc wireless networks

In ad hoc wireless networks, devices that normally cannot directly communicate route their messages through intermediate nodes. The number of those nodes is called hop count, a useful metric in estimating the distance between 2 nodes. Current methods usually depend on special nodes, called anchors, that need accurate localization information, in order to calculate an estimate for the average distance traversed per hop. The drawback of this approach is that anchor nodes increase the overall cost and complexity of the system. To address this problem, this letter proposes a novel, anchor node–free algorithm that can achieve a useful estimate for actual distance between 2 nodes, by analytically finding an estimate for the average maximum distance traveled per hop and multiplying with the hop count. The only requirement is the a priori knowledge of the networks' node density and the node range. The performance of our method is compared with a recent anchor node–based method and is shown to yield similar location estimation accuracy, despite the fact that it does not use anchor nodes.     

一种新的无线传感器网络定位算法研究

针对传统无线传感器网络定位算法平均误差大、节点能耗过高、定位精度不够理想等缺陷,提出了一种新的无线传感器网络定位算法IMDV-Hop.该算法引进了局部跳数Si和修正因子δ-i,用修正因子-δi对局部跳数进行修正,使待定位节点到锚节点的平均跳数更加符合实际情况;通过权衡定位精度和能耗,分三种情况计算了平均每跳间距,使得平均每跳间距更接近于真实值.仿真实验结果表明IMDV-Hop算法平均定位误差低,具有较小的通信开销,在非规则网络中可达到较好的定位精度.     

基于改进的Floyd算法求节点间所有最短路径

网络节点间的最短路径可能不止一条.首先运用加速的Floyd算法得到最短路径长度矩阵;然后根据最短路径长度矩阵构造各个节点的到达距离矩阵,用来与最短路径长度矩阵进行对比;最后得到每个节点的后继节点,进而得到所有最短路径.计算机仿真验证了该算法的高效性.     

Autonomic self‐organization architecture for wireless sensor communications

Wireless sensor nodes may be spread over large areas and long distances, and require multi‐hop communications between nodes, making direct management numerous wireless sensor nodes inefficient. Hierarchical management can be adopted to control several nodes. Effectively controlling the top‐level nodes can decrease the costs of managing nodes and of the communication among them. The lower‐level nodes are controlled and organized with the higher‐level nodes. This study presents an algorithm for self‐organization mechanism of higher‐level nodes, contesting member nodes by multi‐hop to form hierarchical clusters, and applying the ‘20/80 rule’ to determine the ratio of headers to member nodes. Furthermore, the broadcast tree is constructed with the minimum number of hops. Simulation results indicate that the mechanism has a 6–22% lower cover loss than other approaches. The average delay of the minimum hop count approach is 0.22–1.57ms less than that of free hop count approach. The simulation also reveals the influence of 20/80 rule on cluster formation between sensor nodes. Copyright © 2006 John Wiley & Sons, Ltd.