Group-header based method to organize local peer group of vehicles for inter-vehicle communication

• US 8,254,301 B2
• Filed: 11/22/2005
• Issued: 08/28/2012
• Est. Priority Date: 11/22/2005
• Status: Expired due to Fees

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Infotechnology Center Co., Ltd. (Toyota Motor Corporation)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Infotechnology Center USA, Inc.
• Inventors: Chennikara-Varghese, Jasmine, Pang, Marcus, Cai, Shengwei, Hikita, Toshiro, Chen, Wai
• Primary Examiner(s): Pérez Gutiérrez, Rafael
• Assistant Examiner(s): Miah, Liton
• Application Number:
  US11/285,593
• Publication Number:
  US 20070115868A1
• Time in Patent Office: 2,471 Days
• Field of Search: 370/338, 370/342, 370/328, 370/315, 455/522
• US Class Current: 370/315
• CPC Class Codes: G08G 1/163 involving continuous checking
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 48/10 using broadcasted information
• CPC Class Codes: H04W 8/186 Processing of subscriber group data
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method for establishing and maintaining the network and a corresponding ad-hoc moving-device to moving-device network having a plurality of moving-devices grouped into a Local Peer Group (LPG) is disclosed. A group header node (GH) is selected from the plurality of moving wireless devices in the LPG. The GH controls and manages the LPG by broadcasting a plurality of control messages, including a heartbeat message at a fixed interval. The LPG also includes at least one group node (GN). The at least one GN can communicate with the GH via a network link created between the at least one GN and the GH. The GNs join the LPG via the GH. If there is more then one GH in an LPG, header resolution occurs to select only one GH.

Claims

1. A method of establishing and maintaining an ad-hoc wireless network between a plurality of moving nodes, where said plurality of moving nodes are divided into a dynamically formed local peer group (LPG) without ordering said plurality of moving nodes, said method comprises the steps of:

selecting a group header node (GH) for said LPG from said plurality of moving nodes, said GH is assigned a unique group header identification, said GH controls and manages membership in said LPG;

broadcasting a plurality of control messages identifying said LPG and providing information regarding said LPG, including a heartbeat message signal from said selected GH, said heartbeat message is broadcast at a fixed interval;

determining if others of said plurality of moving nodes can join said LPG based upon a predetermined threshold value; and

creating a network link between said others of said plurality of moving nodes if it is determined that said other of said plurality of moving nodes can join the LPG as group nodes (GNs);

wherein if there is more than one GHs within the LPG, said selection step further comprises the steps of;

broadcasting a header resolution message from each of said more than one GH;

performing header resolution to select only one GH as the GH for the LPG, based upon a predetermined selection criterion; and

broadcasting a GH selected message by the new GH that was selected, and the others said more than one GHs join the LPG via the new GH.

2. The method of claim 1, wherein said predetermined selection criterion is based upon a first node of said more than one GH that broadcasts the heartbeat message.

3. The method of claim 1, wherein said heartbeat message includes a Local Peer Group Identification, GH identification number, a number of nodes within the LPG, a maximum number of nodes allowed in the LPG, a hop count, a maximum hop and a time of a next heartbeat message.

4. The method of claim 3, further comprising the steps of:

receiving said heartbeat message by said others of said plurality of moving nodes within a radio range; and

determining whether to broadcast a join Local Peer Group message to the GH, said determination is based upon a comparison of at least one parameter with said predetermined threshold value where said at least one parameter including the number of nodes within said LPG and said hop count and said predetermined threshold value is said maximum number of nodes allowed in the LPG and the maximum hop, said others of said plurality of moving nodes broadcast said join local peer group message if said at least one parameter does not exceed said predetermined threshold value and does not broadcast the join LPG message if the at least one parameter exceeds said predetermined threshold value.

5. The method of claim 1, wherein upon receipt of the heartbeat message said others of said plurality of moving nodes broadcast a join Local Peer Group signal to the GH, and the step of determining if said others of said plurality of moving nodes can join is performed by the GH, said determination is based upon a comparison of at least one parameter with said predetermined threshold value, said at least one parameter including a number of nodes within the LPG and a hop count and said predetermined threshold value is a maximum number of nodes and a maximum hops, said GH allows said other of said plurality of moving nodes to join said LPG as GNs if said at least one parameter does not exceed said predetermined threshold value and does not allow said other of said plurality of nodes to join said LPG if the at least one parameter exceeds the predetermined threshold value.

6. The method of claim 1, where said plurality of control messages further includes a group membership message that includes an identification of all GNs within the LPG, a Local peer group Identification, a GH identification and a timestamp, said identification of GNs within the LPG is periodically updated via a status message broadcast from said GNs.

7. The method of claim 6, wherein the identification of the GN is removed from said group membership message if said status message is not received from said GN after predetermined time interval or if an affirmative leaving message has been received by the GH from the GN.

8. The method of claim 6, wherein said group membership message is included in said heartbeat message and is broadcast at said fixed interval.

9. The method of claim 1, further comprising the steps of:

receiving said heartbeat message from the GH at the GNs;

randomly setting a timer to a value greater than the heartbeat period at each GN within the LPG and waiting for the next heartbeat message; and

decreasing the timer when no heartbeat message is received, wherein if said timer expires prior to receiving said next heartbeat message, said GN having the first timer to expire broadcasts its own heartbeat message and acts as a new GH, where the first GN that broadcasts the heartbeat message becomes the new GH for the LPG.

10. The method of claim 1, further comprising the step of selecting at least one gateway node for said LPG, said at least one gateway node functions to relay a plurality of messages from said GNs to said GH.

11. The method of claim 10, wherein said at least one gateway node collects a plurality of status messages received from said GNs, stores said plurality of status messages in memory and after a predetermined period of time has elapsed, broadcasts one message, containing an aggregate of said plurality of status messages, to said GH.

12. The method of claim 1, further comprising the step of selecting at least one secondary GH, the at least one secondary GH not broadcasting the plurality of control message while said GH is within the LPG, wherein when said GH leaves the LPG, said at least one secondary GH becomes a new GH for the LPG.

13. An ad-hoc wireless network system comprising;

at least one local peer group (LPG), said LPG being dynamically formed from a plurality of moving wireless devices, said plurality of moving wireless are not ordered, said LPG includes;

one group header node (GH) which is selected from said plurality of moving wireless devices and is assigned a unique group header identification, said GH controls and manages membership in said LPG by broadcasting a plurality of control messages identifying said LPG and providing information regarding said LPG, including a heartbeat message at a fixed interval, and

at least one group node (GN) which is created from the remaining moving wireless devices of said plurality of moving wireless devices within radio range of said GH when a predetermined threshold value has not been reached by said at least one LPG,

said at least one GN can communicate with said GH via a network link created between said at least one GN and said GH, said at least one GN broadcasts a status message containing information about the GN to the GH;

wherein if there is more than one GH within the LPG, said more than one GH broadcasts a header resolution message to each other GH and enters into header resolution mode to select one GH as the GH for the LPG based upon a predetermined selection criterion and after one GH is selected, the one GH broadcasts a GH selected message to all other GNs within the LPG and then broadcasts the heartbeat message, the others of said more than one GHs join the LPG via the new GH.

14. The ad-hoc wireless network according to claim 13, further comprising:

at least one gateway node selected from said remaining moving wireless devices of said plurality of moving wireless devices, said at least one gateway node functions to relay a plurality of messages from said at least one GN to said GH, said plurality of messages includes a status message from said at least one GN to said GH, said at least one gateway node collects said status message received from said at least one GN, stores said status message and after a predetermined period of time has elapsed, broadcasts one aggregate status message containing an aggregate of all of said status messages received by said at least one gateway node during said predetermined period of time to said GH.

15. The ad-hoc wireless network according to claim 13, wherein the moving wireless device includes a memory section, a timer, a control means, a transmission and reception section and a heartbeat generating means, said heartbeat generating means generates the heartbeat message at the fixed interval, the heartbeat message includes LPG identification number, the GH identification, a number of nodes with the LPG, a maximum number of nodes allowed in the LPG, a hop count, a maximum hop and a time of the next heartbeat message, when said moving wireless devices is selected as the GH, said fixed interval is counted by said timer and when said timer expires, said heartbeat generating section broadcasts said heartbeat message based upon information stored in the memory section, said control section controls the GH including the determination of whether one of said remaining moving wireless devices of said plurality of moving devices can join said LPG by comparing the predetermined value with at least one parameter, if it is determined that said one of said remaining moving wireless devices of said plurality of moving devices can join the LPG, said control section instructs said transmission and reception section to broadcast a GN accept message, whereas if said control section determines that said one of said remaining of said plurality of moving devices cannot join the LPG, said control section instructs said transmission and reception section to broadcast a GN deny message.

16. The ad-hoc wireless network according to claim 13, wherein when the said remaining plurality of moving wireless devices is selected as a GN, the node includes a memory means, a timer, a control section, and a transmission and reception section said transmission and reception section broadcasts a status message, at a fixed interval to said GH, said fixed interval is by said timer, and when said timer expires, said transmission and reception section broadcasts the status message, based upon information stored in the memory means, said timer is also set to a random time period greater than the heartbeat period, upon reception of said heartbeat message by the transmission reception section, said timer is reset upon a reception of another heartbeat message, if no heartbeat message is received by the transmission/reception section before said timer expires, said control means instructs said transmission/reception section to broadcast its own heartbeat message including information relating to the LPG stored in the memory means and to act as new GH for said LPG.

17. The ad-hoc wireless network according to claim 13, wherein when said remaining plurality of moving wireless devices receiving said heartbeat message said remaining plurality moving wireless device determines whether to broadcast a join LPG message to the GH, said determination is based upon a comparison of at least one parameter with the predetermined threshold value, said remaining wireless devices plurality of moving wireless devices broadcasts the join LPG message if it is determined that said at least one parameter does not exceed said predetermined threshold value, and does not broadcast the join LPG message if the at least one parameter exceeds the predetermined threshold value.

18. The ad-hoc wireless network according to claim 13, wherein said plurality of wireless devices is at least one moving vehicle.

19. The ad-hoc wireless network according to claim 13, wherein said plurality of wireless devices is at least one wireless device coupled to or embedded in a moving vehicle.

20. An ad-hoc network for establishing and maintaining an ad-hoc wireless network between a plurality of moving nodes, where said plurality of moving nodes are divided into a dynamically formed local peer group (LPG) without ordering said plurality of moving nodes, the network comprising:

a processor for executing computer-readable program code provided on computer-readable storage medium, the computer-readable program code having instructions which causes said processor to execute the following steps;

selecting a group header node (GH) for said LPG from said plurality of moving nodes, said GH is assigned a unique group header identification, said GH controls and manages membership in said LPG;

broadcasting a plurality of control messages identifying said LPG and providing information regarding said LPG, including a heartbeat message from said selected GH, said heartbeat message is broadcast at a fixed interval;

determining if others of said plurality of moving nodes can join said LPG based upon a predetermined threshold value; and

creating a network link between said others of said plurality of moving nodes if it is determined that said other of said plurality of moving nodes can join the LPG as group nodes (GNs);

wherein if there is more than one GHs within the LPG, said selection step further comprises the steps of;

broadcasting a header resolution message from each of said more than one GH;

performing header resolution to select only one GH as the GH for the LPG, based upon a predetermined selection criterion; and

broadcasting a GH selected message by the new GH that was selected, and the others said more than one GHs join the LPG via the new GH.