Academic
Publications
Distributed low-cost backbone formation for wireless ad hoc networks

Distributed low-cost backbone formation for wireless ad hoc networks,10.1145/1062689.1062692,Yu Wang,Weizhao Wang,Xiang-yang Li

Distributed low-cost backbone formation for wireless ad hoc networks   (Citations: 43)
BibTex | RIS | RefWorks Download
Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless networks. Previous methods are mostly designed to minimize the backbone size. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with a large cost. We then propose an efficient distributed method to construct a weighted sparse backbone with low cost. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth or the network maximum node degree is bounded. We also show that with a small modification the constructed backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than 3 (or 4) times of the least cost (or hop) path in the original communication graph. As a side product, we give an efficient overlay based multicast structure whose total cost is no more than 10 times of the minimum when the network is modeled by UDG. Our theoretical results are corroborated by our simulation studies.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Several schemes have been proposed for constructing a virtual communication backbone by turning off redundant sensor nodes [1], [2], [3], [4], [5], [6], [7], [8], [9]...

    Chih-Hsun Anthony Chouet al. A Dead-End Free Topology Maintenance Protocol for Geographic Forwardin...

    • ...They assumed that the wireless links are reliable and then tried to theoretically provide performance guarantees [7], [16], [17]...
    • ...There are some other protocols proposed recently to remedy the unreliability of the wireless channels such as using multipath routing [9], [10], building reliable backbone [17], [8], and using energy-efficient reliable routing structure [4], [23]...

    Xufei Maoet al. Energy-Efficient Opportunistic Routing in Wireless Sensor Networks

    • ...In the literature, clusters are applied to: Dynamic Spectrum Allocation [7][11][12], spectrum sensing [13], ad hoc and sensor networks organization [14][15][16], cooperative MIMO techniques [17] [18]...
    • ...For each of the topologies specific cluster hierarchy is applied, where cluster head role can be: predefined [13], rotated [12], location-bounded [11], strategy-bounded [7][17] or metric-based [14][16][21][22][23]...
    • ...However, association protocol may as well resemble CSMA/CA (“sense and associate”) [11][17][23] or impose that cluster head is responsible for discovery of cluster members and their association [14]...
    • ...Possible solutions vary from periodical status reporting [13][17][24], membership expiry [7][18][23] to cluster head request-based [14][25]...

    Jacek Kibildaet al. Novel Cluster Formation Framework for Energy Efficient Short-Range Coo...

    • ...Therefore it is meaningful to assign weights to the nodes (e.g., assign small weight to nodes with a large remaining battery life) and aim to determine a (connected) dominating set of minimum weight (Wang and Li 2005)...

    Yaochun Huanget al. A better constant-factor approximation for weighted dominating set in ...

    • ...Clustering can play a critical role in increasing the performance and lifetime of wireless networks and has been proposed as a way to improve MAC layer protocols (e.g., [1,2]), higher level routing protocols (e.g., [3,4,5]), and energy saving protocols (e.g., [6,7])...

    Saurav Panditet al. Finding Facilities Fast

Sort by: