An energy-efficient permutation routing protocol for single-hop radio networks

A radio network (RN) is a distributed system where each station or node is a small hand-held commodity device called a station. Typically, each station has access to a few channels for transmitting and receiving messages. By RN(p, k), we denote a radio network with p stations, where each station has access to k channels. In a single-hop RN, every station is within the transmission range of every other station. Each station consumes power while transmitting or receiving a message, even when it receives a message that is not destined for it. It is extremely important that the stations consume power only when it is necessary since it is not possible to recharge batteries when the stations are on a mission. We are interested in designing an energy-efficient protocol for permutation routing, which is one of the most fundamental problems in any distributed system. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination address which is the identity of the destination station to which the item should be sent. The goal is to route all the items to their destinations while consuming as little energy as possible. We show that the permutation routing problem of n packets on an RN(p, k) can be solved in 2n/k+(p/k)/sup 2/+p+2k/sup 2/ slots and each station needs to be awake for at most 6n/p+2p/k+8k slots. When k/spl Lt/p/spl Lt/n, our protocol is more efficient, both in terms of total number of slots and the number of slots each station is awake compared to a previously published protocol by Nakano et al. (2001).     

Energy-efficient initialization protocols for single-hop radionetworks with no collision detection

A radio network (RN, for short) is a distributed system consisting of n radio stations. We assume that the stations are small, bulk-produced, hand-held devices running on batteries and cannot be distinguished by serial or manufacturing number. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy-efficient. The initialization problem is to assign each of the n stations in the RN a unique ID. The initialization problem is nontrivial since the stations are assumed to be indistinguishable. The problem is fundamental, since practically all communication protocols for RNs proceed under the assumption that the RN has been initialized in advance. The main contribution of this work is to propose energy-efficient randomized initialization protocols for single-hop RNs lacking collision detection capabilities. First, we show that if the number n of stations is known beforehand, the single-channel RN can be initialized by a protocol that terminates, with probability exceeding 1-¹/_n in O(n) time slots, with no station being awake for more than O(log log n) time slots. We then go on to address the multichannel case and show that if k, (k⩾1), channels are available, an n-station RN can be initialized, with probability exceeding 1-¹/_n, in O(ⁿ/_k+log n) time slots, with no station being awake for more than O(log log n) time slots     

Broadcast-efficient protocols for mobile radio networks

The main contribution of this work is to present elegant broadcast-efficient protocols for permutation routing, ranking, and sorting on single-hop Mobile Radio Networks with p stations and k radio channels, denoted by MRN(p,k). Clearly, any protocol performing these tasks on n items must perform ⁿ/_k broadcast rounds because each item must be broadcast at least once. We begin by presenting an optimal off-line permutation routing protocol using ⁿ /_k broadcast rounds for arbitrary k, p, and n. Further, we show that optimal on-line routing can be performed in ⁿ/ _k broadcast rounds, provided that either k=1 or p=n. We then go on to develop an online routing protocol that takes 2ⁿ/ _k+k-1 broadcast rounds on the MRN(p,k), whenever k⩽√^p/₂. Using these routing protocols as basic building blocks, we develop a ranking protocol that takes 2ⁿ /_k+o(ⁿ/_k) broadcast rounds as well as a sorting protocol that takes 3ⁿ/_k+o(ⁿ/_k) broadcast rounds, provided that k ϵ o(√n) and p=n. Finally, we develop a ranking protocol that takes 3ⁿ/_k+o(ⁿ/ _k) broadcast rounds, as well as a sorting protocol that takes 4ⁿ/_k+o(ⁿ/_k) broadcast rounds on the MRN(p,k), provided that k⩽√^p/₂ and p ϵ o(n). Featuring very low proportionality constants, our protocols offer a vast improvement over the state of the art     

Hypercube computations on partitioned optical passive stars networks

This paper shows that an n=2/sup k/ processor partitioned optical passive stars (POPS) network with g groups and d processors per group can simulate every bidirectional move of an n processor hypercube using one slot when dg. Moreover, the same POPS network can simulate every monodirectional move of a processor hypercube using one slot when d=g. All these results are shown to be optimal. Our simulations improve on the literature whenever d/spl ne/g and directly yield several important consequences. For example, as a direct consequence of our simulations, a POPS network, n=dg and d相似文献   

An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks

In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in broadcast rounds if k p and if each station has a -memory locations. And if k and if each station has a -memory locations, the permutations of these n pretitled items can be done also in broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of stations. Finally we show that the permutation routing problem can be solved on it in broadcast rounds in the worst case. It can be solved in broadcast rounds in the better case. Note that our approach does not impose any restriction on k.     

Uniform leader election protocols for radio networks

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. In this work, we focus on single-channel, single-hop radio networks. We assume that time is slotted and all transmissions occur at slot boundaries. In each time slot, the stations transmit on the channel with some probability until, eventually, one of the stations is declared leader. A leader election protocol is said to be uniform if, in each time slot, every station transmits with the same probability. In a seminal paper, Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open for more than 15 years whether Willard's protocol featured the same time performance with "high probability." One of our main contributions is to show that, unfortunately, this is not the case. Specifically, we prove that for every parameter f∈e^O(n), in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+Ω(√f) time slots. The highlight of this work is a novel uniform leader election protocol that terminates, with probability exceeding 1-1/f, in log log n+o(log log n)+O(log f) time slots. Finally, we provide simulation results that show that our leader election protocol outperforms Willard's protocol in practice     

A fast parallel algorithm for routing unicast assignments in Benesnetworks

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg ² k+lg n) time on a completely connected network of n processors and in O(lg⁴ k+lg² k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route α unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg² k+lg n+(α-1) lg k) time on a completely connected network and in O(lg⁴ k+lg² k lg n+(α-1)(lg ³ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg³ k+1g k lg n) in the second case, for all α⩾lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links     

Near-optimal broadcast in all-port wormhole-routed hypercubes usingerror-correcting codes

A new broadcasting method is presented for hypercubes with wormhole routing mechanism. The communication model assumed allows an n-dimensional hypercube to have at most n concurrent 110 communications along its ports. It further assumes a distance insensitivity of (n+1) with no intermediate reception capability for the nodes along the communication path. The approach is based on determination of the set of nodes (called stations) in the hypercube such that for any node in the network there is a station at distance of at most 1. Once stations are identified, parallel disjoint paths are formed from the source to all stations. The broadcasting is accomplished first by sending the message to all stations which will in turn inform the rest of the nodes of the message. To establish node-disjoint paths between the source node and all stations, we introduce a new routing strategy. We prove that multicasting can be done in one routing step as long as the number of destination nodes are at most n in an n-dimensional hypercube. The number of broadcasting steps using our routing is equal to or smaller than that obtained in an earlier work; this number is optimal for all hypercube dimensions n⩽12, except for n=10     

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-al     

快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

Fully dynamic algorithms for permutation graph coloring

We introduce a dynamic model for maintaining permutation graph coloring. Our motivation comes from the strait type river routing problem in VLSI. This paper presents fully dynamic algorithms for the permutation graph coloring problem. These algorithms are designed to handle Insert and Delete operations and answer some queries. The aim is to provide for running times that are asymptotically more efficient than recomputation (off-line algorithms that run in 0(n logw) time, are known [5,6,10,3]). First, the algorithm A^ that runs in 0(n) uniform running time per Insert/Delete operation is presented. Second, a more sophisticated data structure leads to the algorithm A2 that runs in (9(m logw) uniform running time per Insert I Delete, where m denotes the number of chains in the decomposition. It follows from [7,4] that the running time of A2 when the points from the dynamically changing set are drawn independently from a uniform distribution on the unit square is G(yfn logn) per Insert/Delete in probability. Third, we sketch a composite algorithm A3 that switches between A± and A2 guarantees an amortized running time of (min{n,m logw)) per Insert/Delete. Finally, we outline a number of applications     

Hot-potato algorithms for permutation routing

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n×n Mesh: 7n+o(n) steps; 2ⁿ hypercube: O(n²) steps; n×n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2ⁿ-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2ⁿ) steps     

Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

大规模无线传感网络的混合LEACH协议研究

能耗问题已经成为大规模无线传感器网络中的研究热点,因此如何设计高能效的路由协议是当前面临的技术挑战。为了降低传感器节点的能耗,提出一种适用大规模网络的基于LEACH算法的混合无线传感网络节能路由算法。首先,根据距离信息,设计一种簇成员向基站直接传输或者通过簇头转发数据的路由协议。然后,推导出满足该算法的能耗条件。最后,通过MATLAB工具仿真表明与已有的LEACH协议和M-LEACH协议相比,混合路由协议能够有效降低基站周围节点的能耗,从而延长整个网路的生存期。     

Efficient routing and sorting schemes for de Bruijn networks

We consider the problems of routing and sorting on a de Bruijn network. First, we show that any deterministic oblivious routing scheme for permutation routing on a d-ary de Bruijn network with N=dⁿ nodes, in the worst case, will take Ω(√N) steps under the single-port model. This improves the existing lower bounds provided d is not a constant. We also show that the lower bound is indeed a tight one. Second, we present a deterministic nonoblivious permutation routing algorithm which runs in O(d.n²) time on a d-ary de Bruijn network with N=dⁿ nodes. This algorithm is currently the fastest known nonoblivious deterministic routing algorithm for de Bruijn networks of arbitrary degree. Finally, we present an efficient general sorting algorithm for the de Bruijn networks of arbitrary degree. This algorithm is the best sorting algorithm known so far. It runs in O((log d).d.n²) time for directed de Bruijn network with dⁿ nodes, degree d, and diameter n. As a corollary, we show that on a binary de Bruijn network of Nnodes, our sorting scheme requires at most 2 log² Nsteps     

On computing the upper envelope of segments in parallel

Given a collection of segments in the plane, if we regard the segments as opaque barriers, their upper envelope consists of the portions of the segments visible from point (0, +∞). In this paper, we present deterministic parallel methods for constructing the upper envelope of segments on the weakest shared-memory model, the EREW PRAM. We show that we can find the upper envelope of n line segments optimally in 0(logn) time using 0(n) processors. Furthermore, if the segments are nonintersecting and their endpoints are sorted in x-coordinate, then we can reduce the number of processors to 0(n/ logn). Our method implies that we can find the upper envelope sequentially in 0(n log log n) time, which improves previous results. We also show that we can find the upper envelope of n k-intersecting segments (any pair of the segments intersects at most k times) with a slightly larger time and processor bound     

具有大量错误结点的超立方体网络中并行路由算法

本文讨论具有大量错误结点的超立方体网络中的并行路由算法。假定Hn是一个局部k-维子立方体连通用的n-维超立方体网络,本文提出的并行路由算法能够找出至少K=min（Dk(u),Dk(v）条并行路径,其中每一条路径的长度不超过（dH(Uk,Vk）＋3）2^k。该算法的时间复杂度为O（Kn2^k）。这里,Dk(u）和Dk(v）分别代表源结点u和目的结点v的正确的邻结点个数（不考虑u和v所在的k－维子立方体内部的邻结点）,dH(Uk,Vk）代表源结点u和目的结点v所在的两个k－维子立方体Uk和Vk之间的海明距离。本文还考察了了k=3的特殊情况,在k=3并且有分别不超过12．5％和25％的错误结点的情况下,该算法的时间复杂度为O（Kn）,并且每一条路径的路径长度分别在大约1．5和2倍源结点和目的结点之间的海明距离之内。该算法只要求结点知道其邻结点的状态,而无需知道整个网络信息,也就是说,该算法是基于局部信息的,因而该算法具有很强的实际意义。     

Summation and routing on a partitioned optical passive stars network with large group size

In a partitioned optical passive stars (POPS) network, n=dg processors are divided into g groups of d processors each, and such a POPS network is denoted by POPS(d,g). There is an optical passive star (OPS) coupler between every pair of groups. Hence, a POPS(d,g) requires g/sup 2/ couplers. It is likely that, in a practical system, the number of couplers will be less than the number of processors, i.e., d>/spl radic/n>g and the number of groups will be smaller than the number of processors in a group. Hence, it is important to design fast algorithms for basic operations on such POPS networks with large group size. We present fast algorithms for data sum, prefix sum, and permutation routing on a POPS(d,g) such that d>/spl radic/n>g. Our data sum and prefix sum algorithms improve upon the best known algorithms for these problems designed by Sahni (2000). Permutation routing can be solved on a POPS network by simulating a hypercube sorting algorithm. Our algorithm for permutation routing is more efficient compared to this simulated hypercube sorting algorithm.     

A wavelength division multiple access protocol for high-speed local area networks with a passive star topology

In this paper a multiple access protocol is proposed for a system consisting of many high-speed bursty traffic stations interconnected via an optical passive star coupler. Each station has access over a range of wavelengths. Time is divided intp fixed-sized slots. A station must reserve a wavelength first, then transmits the data on that wavelength. New stations can join the system anytime without any system reconfiguration. Broadcast and multicast traffic can also be easily supported. The performance of both the infinite and finite population cases has been modeled and analyzed. Numerical results show that low delay and high throughput (larger than the electronic speed of a single station) can be achieved. The analysis also shows that the best performance is obtained when the capacities of the reservation channels and the data channels are balanced.     

A subcarrier-slot partition scheme with first-last fit spectrum allocation for elastic optical networks

Bandwidth fragmentation refers to the existence of non-aligned and non-contiguous available subcarrier slots in elastic optical networks. Since spectrum for a connection must be allocated to contiguous slots and aligned along the routing path, non-contiguous and non-aligned available slots could cause call blocking. This paper proposes a subcarrier-slot partition scheme with first-last fit spectrum allocation for elastic optical networks in order to increase the number of contiguous aligned available slots, and hence the blocking probability in the network is suppressed. The partition approach creates more aligned available slots by separating the spectrum allocation of the non-disjoint connections. The first-last fit allocation policy creates more contiguous aligned available slots between two partitions. Simulation results show that the partition approach with first-last fit allocation policy provides lower blocking probability than that of the non-partition approach and the partition approach with other spectrum allocation policies. Furthermore, simulation results indicate that the blocking probability in the network using the proposed scheme improves as the number of partitions is reduced.