Technique for establishing a virtual backbone in an ad hoc...

Details Technique for establishing a virtual backbone in an ad hoc... Technique for establishing a virtual backbone in an ad hoc...

2005-01-04

2005-01-04

Gesesse, Tilahun (Department: 2684)

Telecommunications

Transmitter and receiver at separate stations

Short range rf communication

C455S517000, C455S426200, C370S338000, C370S408000

Reexamination Certificate

active

06839541

ABSTRACT:
An algorithm on a computer readable medium for efficiently creating a message efficient virtual backbone in a wireless ad hoc network utilizes three phases to establish an efficient network among the independent transceivers of a wireless ad hoc network. Independent transceivers within the transmission range of each other are neighbors. A leader election and tree construction phase constructs a tree of neighboring transceivers with one transceiver being designated the root and with each transceiver establishing and recording its location in the tree structure and the identifiers of its neighbors; and reporting when the tree is established. A level calculation phase determines the level of each transceiver away from the root transceiver, with each transceiver recording the level of its neighbors. Precedence for each transceiver is established with consideration of each transceiver's tree level and identifier, with tree level being paramount in deciding precedence; and reporting when the levels of the tree are established. A backbone construction phase establishes all transceivers as a dominator or a dominatee, with the dominators forming the network backbone and the dominatees all being neighbors to a dominator. Within the network each transceiver only needs to know the information of its neighboring transceivers.

REFERENCES:
patent: 5412654 (1995-05-01), Perkins
patent: 5436905 (1995-07-01), Li et al.
patent: 5533025 (1996-07-01), Fleek et al.
patent: 5623495 (1997-04-01), Eng et al.
patent: 5654959 (1997-08-01), Baker et al.
patent: 5706428 (1998-01-01), Boer et al.
patent: 5717689 (1998-02-01), Ayanoglu
patent: 5875179 (1999-02-01), Tikalsky
patent: 5987011 (1999-11-01), Toh
patent: 6078568 (2000-06-01), Wright et al.
patent: 6104712 (2000-08-01), Robert et al.
patent: 6122759 (2000-09-01), Ayanoglu et al.
patent: 6130881 (2000-10-01), Stiller et al.
patent: 6195751 (2001-02-01), Caronni et al.
patent: 6198728 (2001-03-01), Hulyalkar et al.
patent: 6205128 (2001-03-01), Le
patent: 6304556 (2001-10-01), Haas
patent: 6456599 (2002-09-01), Elliott
patent: 20020018448 (2002-02-01), Amis et al.
I. Cidon and O. Mokryn:Propagation and Leader Election in Multihop Broadcast Environment, 12th International Symposium on DIStributed Computing (DISC98), 104-119, Greece, Sep. 1998.
P. Berman et al.:Applications of the Matroid Parity Problem to Approximating Steiner Trees, Tech. Rep. 980021, Computer Science Dept., UCLA, 1998.
H.B. Hunt et al.:NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs, Journal of Algorithms, 26(2):238-274, 1998.
B. Das et al.:Routing in Ad Hoc Networks Using a Spine, International Conference on Computers and Communications Networks '97, Las Vegas, Nevada, Sep. 1997.
U. Feige:A threshold of 1n n for approximating set cover, 28th ACM Symposium on Theory of Computing, 314-318, 1996.
S. Guha et al.:Approximation Algorithms for Connected Dominating Sets, Algorithmica, 20(4):374-387, Apr. 1998.
M.V. Marathe et al.:Simple Heuristics for Unit Disk Graphs, Networks, vol. 25, 59-68, 1995.
K. M. Alzoubi et al.:New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Hawaii International Conference on System Sciences—2002.
B. Das et al.:Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets, International Conference on Communications '97, Montreal, Canada, Jun. 1997.
K. M. Alzoubi et al.:Distributed Heuristics for Connected Dominating Sets in Wireless Ad Hoc Networks, Journal of Communications and Networks, vol. 4, No. 1, Mar. 2002.

Affiliated with

Also associated with

Rating

Technique for establishing a virtual backbone in an ad hoc... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Technique for establishing a virtual backbone in an ad hoc..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for establishing a virtual backbone in an ad hoc... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3377547