Search

For noncooperative networks in which each node is a selfish agent, certain incentives must be given to intermediate nodes to let them forward the data for others. What makes the scenario worse is that, in a multihop noncooperative network, the end points can only observe whether or not the end-to-end transaction was successful or not, but not the individual actions of intermediate nodes. Thus, in the absence of properly designed incentive schemes, rational and selfish intermediate nodes may choose to forward data packets at a very low priority or simply drop the packets, and they could put the blame on the unreliable channel. In this paper, assuming the receiver is a trusted authority, we propose several methods that discourage the hidden actions under hidden information in multihop noncooperative networks with high probability. We design several algorithmic mechanisms for a number of routing scenarios such that each selfish agent will maximize its expected utility (i.e., profit) when it truthfully declares its type (i.e., cost and its actions) and it truthfully follows its declared actions. Our simulations show that the payments by our mechanisms are only slightly larger than the actual cost incurred by all intermediate nodes. [ABSTRACT FROM AUTHOR]

Unlike convectional omnidirectional sensors that always have an omniangle of sensing range, directional sensors may have a limited angle of sensing range due to the technical constraints or cost considerations. A directional sensor network consists of a number of directional sensors, which can switch to several directions to extend their sensing ability to cover all the targets in a given area. Power conservation is still an important issue in such directional sensor networks. In this paper, we address the multiple directional cover sets (MDCS) problem of organizing'the directions of sensors into a group of nondisjoint cover sets to extend the network lifetime. One cover set in which the directions cover all the targets is activated at one time. We prove the MDCS to be NP-complete and propose several algorithms for the MDCS. Simulation results are presented to demonstrate the performance of these algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of joint channel assignment, link scheduling, and routing for throughput optimization in wireless networks with multiradios and multichannels. We mathematically formulate this problem by taking into account the interference, the number of available radios the set of usable channels, and other resource constraints at nodes. We also consider the possible combining of several consecutive channels into one so that a network interface card (NIC) can use the channel with larger range of frequencies and thus improve the channel capacity. Furthermore, we consider several interference models and assume a general yet practical network model in which two nodes may still not communicate directly even if one is within the transmission range of the other. We designed efficient algorithm for throughput (or fairness) optimization by finding flow routing, scheduling of transmissions, and dynamic channel assignment and combining. We show that the performance, fairness and throughput, achieved by our method is within a constant factor of the optimum. Our model also can deal with the situation when each node will charge a certain amount for relaying data to a neighboring node and each flow has a budget constraint. Our extensive evaluation shows that our algorithm can effectively exploit the number of channels and radios. In addition, it shows that combining multiple channels and assigning them to a single user at some time slots indeed increases the maximum throughput of the system compared to assigning a single channel. [ABSTRACT FROM AUTHOR]

Assume that n wireless nodes are uniformly randomly deployed in a square region with side-length a and all nodes have the uniform transmission range r and uniform interference range R > r. We further assume that each wireless node can transmit (or receive) at W bits/second over a common wireless channel. For each node vi, we randomly and independently pick k - 1 points pi,j (1 ≤ j ≤ k - 1) from the square, and then multicast data to the nearest node for each Pi,j. We derive matching asymptotic upper bounds and lower bounds on multicast capacity of random wireless networks. Under protocol interference model, when a²/r² = O(n/log(n)), we show that the total multicast capacity is Θ (√n/log n · (W/√k)) when k = O(n/log n); the total multicast capacity is Θ; (W) when k = Ω(n/ log n). We also study the capacity of group-multicast for wireless networks where for each source node, we randomly select k - 1 groups of nodes as receivers and the nodes in each group are within a constant hops from the group leader. The same asymptotic upper bounds and lower bounds still hold. We also extend our capacity bounds to d-dimensional networks. [ABSTRACT FROM AUTHOR]

Differentiated service (DiffServ) is a mechanism to provide the quality-of-service (QoS) with a certain performance guarantee. In this paper, we study how to design DiffServ multicast when every relay link is an independent selfish agent. We assume that each link ei is associated with a (privately known) cost coefficient ci such that the cost of el to provide a transmission service with bandwidth demand χ is ci ⋅ χ. Further, we assume that there is a fixed source node s and a set R of receivers, each of which requires from s data with a minimum bandwidth demand. The DiffServ multicast problem is to compute a link-weighted tree rooted at s and spanning R such that the receivers' demands are met. This generalizes the traditional link-weighted Steiner tree problem. We first show that a previous approximation algorithm does not directly induce a strategyproof mechanism. We then give a new polynomial time algorithm to construct a DiffServ multicast tree whose total cost is no more than eight times the optimal total cost when the cost coefficient of each link is known. Based on this tree, we design a truthful mechanism for DiffServ multicast, i.e., we give a polynomial-time computable payment scheme to compensate all chosen relay links such that each link maximizes its profit when it declares its cost coefficient truthfully. [ABSTRACT FROM AUTHOR]

We propose a novel localized topology-control algorithm for each wireless node to locally select communication neighbors and adjust its transmission power accordingly such that all nodes together self-form a topology that is energy efficient simultaneously for both unicast and broadcast communications. We theoretically prove that the proposed topology is planar, which meets the requirement of certain localized routing methods to guarantee packet delivery; it is power-efficient for unicast—the energy needed to connect any pair of nodes is within a small constant factor of the minimum; it is also asymptotically optimum for broadcast—the energy consumption for broadcasting data on top of it is asymptotically the best among all structures constructed using only local information; it has a constant bounded logical degree, which will potentially save the cost of updating routing tables if used. We further prove that the expected average physical degree of all nodes is a small constant. To the best of our knowledge, this is the first localized topology- control strategy for all nodes to maintain a structure with all these desirable properties. Previously, only a centralized algorithm was reported in [3]. Moreover, by assuming that the node ID and its position can be represented in O(Iog n) bits for a wireless network of n nodes, the total number of messages by our methods is in the range of [5n, 13n], where each message is O(Iog n) bits. Our theoretical results are corroborated in the simulations. [ABSTRACT FROM AUTHOR]

Proposes a geometric spanner for static wireless ad hoc networks that can be constructed efficiently in a localized manner. Connected dominating set; Delaunay triangulation; Localized algorithm.

We present an overview of the recent progress of applying computational geometry techniques to solve some questions, such as topology construction and broadcasting, in wireless ad hoc networks. Treating each wireless device as a node in a two-dimensional plane, we model the wireless networks by unit disk graphs in which two nodes are connected if their Euclidean distance is no more than one. We first summarize the current status of constructing sparse spanners for unit disk graphs with various combinations of the following properties: bounded stretch factor, bounded node degree, planar, and bounded total edges weight (compared with the minimum spanning tree). Instead of constructing subgraphs by removing links, we then review the algorithms for constructing a sparse backbone (connected dominating set), that is, subgraph from the subset of nodes. We then review some efficient methods for broadcasting and multicasting with theoretic guaranteed performance. Copyright © 2003 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

An introduction is presented in which editors discuss various papers within the issued focused on mobile sensing covering several topics including, multisensor architecture, routing algorithm, and data collection protocol meant for wireless sensor networks.