Method to establish and organize an ad-hoc wireless peer to peer network

• US 20060176847A1
• Filed: 01/11/2006
• Published: 08/10/2006
• Est. Priority Date: 01/11/2005
• Status: Active Grant

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Infotechnology Center Co., Ltd. (Toyota Motor Corporation)
• Original Assignee: Toyota Infotechnology Center Co., Ltd. (Toyota Motor Corporation)
• Inventors: Chennikara-Varghese, Jasmine, Lee, John, Pang, Marcus, Chen, Wai, Hikita, Toshiro, Cai, Shengwei
• Granted Patent: US 7,720,026 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• CPC Class Codes: G08G 1/161 Decentralised systems, e.g. inter-vehicle communication
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

A method for organizing and maintaining an ad-hoc network for communication between a plurality of moving devices is disclosed. The method comprises the steps of grouping the plurality of moving devices into at least one local peer group (LPG), ordering the plurality of devices within each LPG based upon a relative position of each of the plurality of devices within each LPG and assigning a unique identifier for each of the plurality of moving devices, where the unique identifier is based, in part on the LPG that the corresponding moving device is located.

Claims

1. A method for organizing and maintaining an ad-hoc network for communication between a plurality of moving devices comprising the steps of:

(a) grouping said plurality of moving devices into at least one local peer group (LPG);

(b) ordering said plurality of moving devices within each LPG based upon a relative position of each of said plurality of devices within each LPG; and

(c) assigning a unique identifier for each of said plurality of moving devices, where said unique identifier is based, in part on the LPG in which the corresponding moving device is located.

2. The method of claim 1, wherein step b includes reordering said plurality of moving devices based upon a change in the relative position of the plurality of moving devices which is caused by motion of said plurality of moving devices.

3. The method of claim 1, wherein step c includes modifying said unique identifier for a moving device when said moving device changes LPGs.

4. The method of claim 1, wherein a message is routed within an LPG based upon the ordering of the plurality of moving devices and further based upon a type of communication message.

5. The method of claim 1, wherein said unique identifier is an IP address.

6. The method of claim 5, wherein step c includes assigning two IP addresses when a moving device is located near a border of two adjacent LPGs or within an overlapping area of said adjacent LPGs to allow for communication between the adjacent LPGs.

7. The method of claim 1, wherein at least one LPG is a stationary LPG, said at least one stationary LPG has a fixed location that is predefined.

8. The method of claim 1, wherein said LPG is at least one dynamic LPG, said dynamic LPG is formed based upon a clustering of one or more of said plurality of moving devices.

9. The method of claim 1, wherein said LPGs are divided into equivalent cells (EC) defined by a group of moving devices that are within a one hop of each other such that only one transmission of a message is needed to reach any of the group of moving devices within the EC, said EC is controlled by an equivalent cell header (ECH).

10. The method of claim 1, wherein step b comprises the step of:

creating a position vector representing the relative position of each moving device within each LPG.

11. The method of claim 5, wherein said IP address is assigned based upon a predefined network prefix concatenated with a unique LPG identification and a unique moving device identification.

12. The method of claim 11, wherein said unique LPG identification and said unique moving device identification are calculated from a hash function.

13. The method of claim 11, wherein said unique LPG identification and said unique moving device identification are provided from an external wireless device in communication with the plurality of moving devices.

14. The method of claim 1, wherein the step b comprises the steps of:

broadcasting a message including a first moving device'"'"'s position, an indication of an intended message direction, and a time of the broadcast;

receiving said broadcast message by a second moving device;

estimating a displacement of said first moving device based upon said received broadcast message;

calculating a current position for said first moving device based upon said estimated displacement and said first moving device'"'"'s position; and

comparing said calculated current position with a position of said second moving device.

15. The method of claim 10, wherein the step of creating a position vector comprises the steps of:

initializing the position vector;

broadcasting said initialized position vector to another moving device that is joining the LPG;

comparing, by said another moving device, its position with position information that is included in said broadcast;

inserting a position value of said another moving device into said position vector based upon the comparison; and

broadcasting an updated position vector to all other moving devices within the LPG.

16. The method of claim 15, wherein upon receipt of said updated position vector at least one of said other moving devices modify its position in the updated position vector based upon its change in relative position.

17. The method of claim 14, wherein said second moving device will relay the message when the second moving device is determined to be along the intended message direction.

18. The method of claim 1, wherein each of said plurality of moving devices are classified according to a type of moving device and said unique identifier is assigned based upon said classification.