Communication method and wireless communication device having a frame which is exchanged between nodes

• US 8,000,315 B2
• Filed: 01/27/2006
• Issued: 08/16/2011
• Est. Priority Date: 01/31/2005
• Status: Expired due to Fees

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Doi, Hiroshi, Mimura, Masahiro, Matsumoto, Taisuke
• Primary Examiner(s): Hu, Jinsong
• Assistant Examiner(s): Georgewill, Opiribo
• Application Number:
  US11/815,023
• Publication Number:
  US 20090052366A1
• Time in Patent Office: 2,027 Days
• Field of Search: 370/315, 370/338, 370/351
• US Class Current: 370/351
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• 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

Abstract

A frame such as a beacon in wireless communication, with a maximum MAC address, hop count, and maximum hop count, described therein is exchanged between nodes. All the nodes measure the number of hops from a node with the maximum MAC address, and exchange the maximum hop count (hmax) out of the numbers with each other. Hop count H(a,b) between arbitrary nodes a and b is expressed by H(a,b)≦H(a,max)+H(max,b)≦2*hmax, where hmax is a hop count from node (max) with the maximum MAC address to the farthest node. That is, the number of hops between two arbitrary nodes in the group is always 2*hmax or less. Herewith, a numeric value assuredly exceeding the maximum value out of the numbers of hops between nodes in an ad-hoc network can be propagated in the entire ad-hoc network.

Claims

1. A communication method in an ad-hoc network in which a plurality of communication devices perform ad-hoc communication, comprising:

a step in which the communication devices determine a unique communication device in the ad-hoc network;

a step in which the communication devices measure hop counts from the unique communication device; and

a step in which the communication devices propagate a maximum hop count out of the hop counts, in the ad-hoc network,

wherein the communication device periodically transmits specific information, in a range communicatable by the communication device,

wherein the specific information includes an identifier specifying a communication device, a hop count from the unique communication device, and a lifetime formed by unifying a lifetime of the information on the identifier and a lifetime of the information on the hop count,

wherein the step for determining the unique communication device includes;

a step in which a communication device compares a self identifier as an initial value of an identifier to an identifier received from an other communication device, and selects an identifier larger, smaller, or closer to a specific value; and

a step in which the communication device retains information on the identifier selected, and transmits the information to an other communication device,

wherein the step for measuring the hop count includes;

a step in which the unique communication device transmits a hop count included in the specific information starting with ‘

0’

;

a step in which a communication device, when receiving the specific information, adds a given number of hops to the hop count;

a step in which a communication device compares the hop count with a given number of hops added, to information on a hop count from the unique communication device, retained until then, and selects a smaller hop count; and

a step in which the communication device updates information on the hop count included in the specific information, to the hop count selected, and transmits the information to an other communication device, and

wherein the communication device deletes the information on the identifier and the information on the hop count when the lifetime timeouts,

wherein the specific information include a maximum hop count, and

wherein the step for propagating a maximum hop count out of the hop counts retained by the communication devices, in an ad-hoc network includes;

a step for selecting a maximum hop count out of a hop count from the unique communication device, obtained by a communication device in the step for measuring;

the maximum hop count received; and

information on the maximum hop count retained until then; and

a step for updating information on a maximum hop count to a hop count selected by a communication device, for retaining the information, and for transmitting the information to an other communication device,

wherein the specific information further includes a lifetime indicating a time of validity of the specific information,

wherein an initial value of the lifetime is given by a communication device that is transmitting a maximum hop count, and

wherein information on the maximum hop count is deleted when the lifetime timeouts,

wherein the lifetime is given by

(time required for 1-hop relaying)*(k+n),

assuming that k is a value of the maximum hop count and n is a constant.

5. The communication method of claim 1, including:

a step for recording an identifier of a communication device as a transmission origin of the specific information when a communication device updates an identifier of the unique communication device, a hop count from the unique communication device, and the maximum hop count, respectively; and

a step for unconditionally updating an identifier of the unique communication device, a hop count from the unique communication device, and information on the maximum hop count when receiving the specific information from a communication device identified by the identifier recorded.

6. The communication method of claim 5, wherein the specific information further includes sequence numbers given to an identifier of the unique communication device, to a hop count from the unique communication device, and to the maximum hop count, respectively, and wherein the sequence number included in the specific information received is invalidated if smaller than the sequence number retained a self.

7. The communication method of claim 6, wherein a sequence number given to an identifier of the unique communication device and a sequence number given to the maximum hop count are unified.

2. A communication method in an ad-hoc network in which a plurality of communication devices perform ad-hoc communication, comprising:

a step in which the communication devices determine a unique communication device in the ad-hoc network;

a step in which the communication devices measure hop counts from the unique communication device; and

a step in which the communication devices propagate a maximum hop count out of the hop counts, in the ad-hoc network,

wherein the communication device periodically transmits specific information, in a range communicatable by the communication device,

wherein the specific information includes an identifier specifying a communication device, a hop count from the unique communication device, and a lifetime formed by unifying a lifetime of the information on the identifier and a lifetime of the information on the hop count,

wherein the step for determining the unique communication device includes;

a step in which a communication device compares a self identifier as an initial value of an identifier to an identifier received from an other communication device, and selects an identifier larger, smaller, or closer to a specific value; and

a step in which the communication device retains information on the identifier selected, and transmits the information to an other communication device,

wherein the step for measuring the hop count includes;

a step in which the unique communication device transmits a hop count included in the specific information starting with ‘

0’

;

a step in which a communication device, when receiving the specific information, adds a given number of hops to the hop count;

a step in which a communication device compares the hop count with a given number of hops added, to information on a hop count from the unique communication device, retained until then, and selects a smaller hop count; and

a step in which the communication device updates information on the hop count included in the specific information, to the hop count selected, and transmits the information to an other communication device, and

wherein the communication device deletes the information on the identifier and the information on the hop count when the lifetime timeouts,

wherein the specific information include a maximum hop count, and

wherein the step for propagating a maximum hop count out of the hop counts retained by the communication devices, in an ad-hoc network includes;

a step for selecting a maximum hop count out of a hop count from the unique communication device, obtained by a communication device in the step for measuring;

the maximum hop count received; and

information on the maximum hop count retained until then; and

a step for updating information on a maximum hop count to a hop count selected by a communication device, for retaining the information, and for transmitting the information to an other communication device,

wherein the specific information further includes a lifetime indicating a time of validity of the specific information,

wherein an initial value of the lifetime is given by a communication device that is transmitting a maximum hop count, and

wherein information on the maximum hop count is deleted when the lifetime timeouts,

wherein the lifetime is given by

(time required for 1-hop relaying)*(mk+n),

assuming that k is a value of the maximum hop count, and n and m are constants.

3. A communication method in an ad-hoc network in which a plurality of communication devices perform ad-hoc communication, comprising:

a step in which the communication devices determine a unique communication device in the ad-hoc network;

a step in which the communication devices measure hop counts from the unique communication device; and

a step in which the communication devices propagate a maximum hop count out of the hop counts, in the ad-hoc network,

wherein the communication device periodically transmits specific information, in a range communicatable by the communication device,

wherein the specific information includes an identifier specifying a communication device, a hop count from the unique communication device, and a lifetime formed by unifying a lifetime of the information on the identifier and a lifetime of the information on the hop count,

wherein the step for determining the unique communication device includes;

a step in which a communication device compares a self identifier as an initial value of an identifier to an identifier received from an other communication device, and selects an identifier larger, smaller, or closer to a specific value; and

a step in which the communication device retains information on the identifier selected, and transmits the information to an other communication device,

wherein the step for measuring the hop count includes;

a step in which the unique communication device transmits a hop count included in the specific information starting with ‘

0’

;

a step in which a communication device, when receiving the specific information, adds a given number of hops to the hop count;

a step in which a communication device compares the hop count with a given number of hops added, to information on a hop count from the unique communication device, retained until then, and selects a smaller hop count; and

a step in which the communication device updates information on the hop count included in the specific information, to the hop count selected, and transmits the information to an other communication device, and

wherein the communication device deletes the information on the identifier and the information on the hop count when the lifetime timeouts,

wherein the specific information include a maximum hop count, and

wherein the step for propagating a maximum hop count out of the hop counts retained by the communication devices, in an ad-hoc network includes;

a step for selecting a maximum hop count out of a hop count from the unique communication device, obtained by a communication device in the step for measuring;

the maximum hop count received; and

information on the maximum hop count retained until then; and

a step for updating information on a maximum hop count to a hop count selected by a communication device, for retaining the information, and for transmitting the information to an other communication device,

wherein the specific information further includes a lifetime indicating a time of validity of the specific information,

wherein an initial value of the lifetime is given by a communication device that is transmitting a maximum hop count, and

wherein information on the maximum hop count is deleted when the lifetime timeouts,

wherein the lifetime is given by

(time required for 1-hop relaying)*(k+n)

when the ad-hoc network is in a contracting or steady state, and

(time required for 1-hop relaying)*(mk+n)

when the ad-hoc network is in a expanding state,

assuming that k is a value of the maximum hop count, and n and m are constants.

4. The communication method of claim 3, wherein the ad-hoc network is judged to be in an expanding state if a communication device receives the specific information that increases the maximum hop count at least once during a period twice a cycle during which the communication device communicates specific information periodically, and to be in a contracting or steady state otherwise.