Process for generating and updating a hierarchical tree in a MANET multicast routing protocol ad hoc network

• US 20050259595A1
• Filed: 05/11/2005
• Published: 11/24/2005
• Est. Priority Date: 05/18/2004
• Status: Active Grant

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Preguica, Christophe
• Granted Patent: US 7,602,738 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A MANET multicast proactive routing protocol ad hoc network is designed to implement a process dedicated to the generating and updating of a “child/parent” hierarchical tree. This process consists, if a “child” router (RR1) belonging to the network wishes to join a hierarchical tree associated with a source router (SR), of associating this child router (RR1) with a neighboring “parent” router (R1_NA) through the transmitting of a join message designating the source router (SR), in unicast mode, to the neighboring parent router (R1_NA)

Claims

1. A process for generating a “

child/parent”

hierarchical tree in a MANET point-to-multipoint proactive routing protocol ad hoc network, characterized by the fact that it comprises, each time that a “

child”

router (RR, R) of said network wishes to join a hierarchical tree associated with a source router (SR), associating it with a neighboring “

parent”

router (R) of said network through the transmitting of a join message designating said source router (SR) to said neighboring parent router (R) in point-to-point mode.

2. A process according to claim 1, characterized by the fact that:

a) If said neighboring parent router is already associated with another child router of said network, said requesting child router is associated with said neighboring parent router, in order to join it to said tree, and the value of the state information representative of the number of child routers associated with said neighboring parent router is incremented by one unit,

b) If said neighboring parent router is not already associated with another child router of said network, said requesting child router is associated with said neighboring parent router and said state information of said neighboring parent router is given the value “

one”

. A join message designating said source router (SR) is then transmitted in point-to-point mode, by said neighboring parent router, to another neighboring router of said network, which in its turn constitutes a parent for said neighboring parent router,

c) Operation a) or operation b) is then repeated with said neighboring parent router receiving a join message according to whether or not it is already associated with another child router of said network.

3. A process according to claim 1, characterized by the fact that if a router (RR, R) no longer wishes to belong to said tree, as it is no long associated with a child router, said router transmits a prune message to its neighboring parent router in point-to-point mode.

4. A process according to claim 3, characterized by the fact that:

i. If said neighboring parent router is associated with at least two child routers of said network, said requesting router is disassociated from said neighboring parent router, so that it no longer belongs to said tree, and the value of said neighboring parent router'"'"'s state information representative of the number of child routers associated with it is decremented by one unit,

ii. If said neighboring parent router is only associated with said requesting child router, said requesting child router is disassociated from said neighboring parent router and said state information of said neighboring parent router is given the value zero, and a request for pruning from said tree is then transmitted by said neighboring parent router, to its own neighboring parent router, in point-to-point mode,

iii. Operation i) or operation ii) is then repeated with said neighboring parent router receiving a prune message according to whether it is associated with at least two child routers or with a single child router.

5. A process according to claim 1, characterized by the fact that if a link embodying an association between a parent router and a child router is interrupted, said child router transmits a join message designating said source router (RS), in unicast mode, to another neighboring router of said network, in order to be associated with it, and this neighboring router then becomes a new neighboring parent router for said child router.

6. A process according to claim 5, characterized by the fact that:

I) If said neighboring parent router is already associated with another child router of said network, said requesting child router is associated with its new neighboring parent router, in order to join it to said tree, and the value of said new neighboring parent router'"'"'s state information representative of the number of child routers associated with it is incremented by one unit,

II) If said new neighboring parent router is not already associated with another child router of said network, said requesting child router is associated with said new neighboring parent router and said state information of said new neighboring parent router is given the value “

one”

, and a join message designating said source router (SR) is then transmitted, in point-to-point mode, by said new neighboring parent router, to another neighboring router of said network, which in its turn becomes a parent for said new neighboring parent router,

III) Operation I) or operation II) is then repeated with said neighboring parent router receiving a join message according to whether or not it is already associated with another child router of said network.

7. A process according to claim 5, characterized by the fact that if said link embodying an association between a parent router and a child router is interrupted, said parent router transmits a request for pruning from said tree to its neighboring parent router, in point-to-point mode.

8. A process according to claim 7, characterized by the fact that the time elapsed since the start of said link interruption is counted at the level of said parent router, so that said prune demand is only transmitted once a first chosen duration has elapsed.

9. A process according to claim 1, characterized by the fact that at the level of each router of said tree the intensity of the signals originating from its parent router is analyzed, then said intensities are compared with a chosen threshold, so that if an intensity below said threshold is detected by a child router on a link with its neighboring parent router, said child router transmits a request to join said tree to a neighboring router other than its neighboring parent router.

10. A process according to claim 9, characterized by the fact that the time elapsed since a signal intensity first fell below the threshold is counted by said child router, so that said join demand is only transmitted once a second chosen duration has elapsed.

11. A process according to claim 2, characterized by the fact that said join message and/or said prune message includes a “

unicast”

address designating said source router and a “

multicast”

group address.

12. A process according to claim 1, characterized by the fact that said MANET point-to-multipoint proactive routing protocol is chosen from a group containing at least the TBRPF and OLSR protocols.