NDLI: Adding Capacity Points to a Wireless Mesh Network Using Local Search

Content Provider	IEEE Xplore Digital Library
Author	Robinson, J. Uysal, M. Swaminathan, R. Knightly, E.
Copyright Year	2008
Description	Author affiliation: Rice Univ., Houston, TX (Robinson, J.; Knightly, E.)
Abstract	Wireless mesh network deployments are popular as a cost-effective means to provide broadband connectivity to large user populations. As the network usage grows, network planners need to evolve an existing mesh network to provide additional capacity. In this paper, we study the problem of adding new capacity points (e.g., gateway nodes) to an existing mesh network. We first present a new technique for calculating gateway-limited fair capacity as a function of the contention at each gateway. Then, we present two online gateway placement algorithms that use local search operations to maximize the capacity gain on an existing network. A key challenge is that each gateway's capacity depends on the locations of other gateways and cannot be known in advance of determining a gateway placement. We address this challenge with two placement algorithms with different approaches to estimating the unknown gateway capacities. Our first placement algorithm, MinHopCount, is adapted from a solution to the facility location problem. MinHopCount minimizes path lengths and iteratively estimates the wireless capacity of each gateway location. Our second algorithm, MinContention, is adapted from a solution to the uncapacitated k-median problem and minimizes average contention on mesh nodes, i.e. the number of links in contention range of a mesh node and the number of routes using each link. We show that our gateway placement algorithms outperform a greedy heuristic by up to 64% on realistic topologies. For an example topology, we study the set of all possible gateway placements and find that there is large capacity gain between near-optimal and optimal placements, but the near-optimal placements found by local search are similar in configuration to the optimal.
Starting Page	1247
Ending Page	1255
File Size	203608
Page Count	9
File Format	PDF
ISBN	9781424420254
ISSN	0743166X
DOI	10.1109/INFOCOM.2008.181
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-04-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Wireless mesh networks Iterative algorithms Peer to peer computing Network topology IP networks Mesh networks Telecommunication traffic Communications Society Cities and towns Throughput
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Deploying Mesh Nodes under Non-Uniform Propagation

Assessing the VANET's Local Information Storage Capability under Different Traffic Mobility

PPMN:A Resilient Public Peer-to-Peer Mesh Network of IEEE802.16 Users

Routing Primitives for Wireless Mesh Networks: Design, Analysis and Experiments

A Performance Study of Deployment Factors in Wireless Mesh Networks

Latency-Efficient Distributed M2M Multicasting in Wireless Mesh Networks under Physical Interference Model

The Multicast Capacity Region of Large Wireless Networks

Characterizing Link Importance in Multi-Channel, Multi-Radio, Multi-Rate Wireless Mesh Networks

Minimum-Latency Gossiping in Multi-Hop Wireless Mesh Networks

Adding Capacity Points to a Wireless Mesh Network Using Local Search

Similar Documents

Deploying Mesh Nodes under Non-Uniform Propagation

Assessing the VANET's Local Information Storage Capability under Different Traffic Mobility

PPMN:A Resilient Public Peer-to-Peer Mesh Network of IEEE802.16 Users

Routing Primitives for Wireless Mesh Networks: Design, Analysis and Experiments

A Performance Study of Deployment Factors in Wireless Mesh Networks

Latency-Efficient Distributed M2M Multicasting in Wireless Mesh Networks under Physical Interference Model

The Multicast Capacity Region of Large Wireless Networks

Characterizing Link Importance in Multi-Channel, Multi-Radio, Multi-Rate Wireless Mesh Networks

Minimum-Latency Gossiping in Multi-Hop Wireless Mesh Networks

Adding Capacity Points to a Wireless Mesh Network Using Local Search