Method and apparatus for connecting devices via an ad hoc wireless communication network

• US 20030096576A1
• Filed: 12/29/2000
• Published: 05/22/2003
• Est. Priority Date: 12/29/2000
• Status: Active Grant

• Current Assignee: Wistron Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bhagwat, Pravin, Salonidis, Theodoros, LaMaire, Richard O.
• Granted Patent: US 6,865,371 B2
• Time in Patent Office: Days
• US Class Current: 455/41.1
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 84/00 Network topologies

Abstract

A method for connecting two or more devices via a wireless communication channel is provided. In one embodiment, a method of connecting a first device to a second device includes the steps of arbitrarily assigning one of two possible states to each device, wherein in a first state, a device seeks to establish a connection with another device, and in a second state, the device renders itself available for connection with the other device; and alternating a present state of each device between the first state and the second state in accordance with a predefined probability distribution until either a predetermined timeout period has expired or a connection between the devices has been established, the length of time that each device remains in the first and second states being controlled by the probability distribution. In a second embodiment, a method of forming a scatternet between a plurality of devices or nodes in an ad hoc wireless communication network is provided.

Claims

1. A method of connecting a first device to a second device via a wireless communication channel, the method comprising the steps of:

arbitrarily assigning one of a first state and a second state to the first device, wherein in the first state the first device seeks to establish a connection with the second device, and in the second state the first device renders itself available for connection with the second device; and

alternating a present state of the first device between the first state and the second state in accordance with a probability distribution until at least one of a predetermined timeout period has expired and a connection with the second device has been established, the length of time that the first device remains in the first and second states being at least partially controlled by the probability distribution.

2. The method of claim 1, further comprising the step of modifying at least one parameter associated with the probability distribution, the at least one parameter affecting an alternating state sequence of the first device, whereby a period of time that the first and second devices are in complimentary states is optimized, thereby minimizing a connection establishment time.

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

initializing an elapsed time counter; and

periodically measuring an elapsed time from the counter to determine whether the predetermined timeout period has been exceeded.

4. The method of claim 3, wherein the step of measuring the elapsed time is performed before each change of state of the first device.

5. The method of claim 1, wherein the probability distribution is a random distribution.

6. The method of claim 1, wherein the first and second devices include Bluetooth-enabled devices.

7. The method of claim 6, wherein the first state is an INQUIRY state and the second state is an INQUIRY SCAN state.

8. A method of establishing a connection between a plurality of devices via at least one wireless communication channel, the method comprising the steps of:

arbitrarily assigning one of a first state and a second state to each of the devices, wherein in the first state a device seeks to discover and establish a connection with another device, and in the second state a device renders itself available for discovery and connection with another device; and

alternating a present state of each of the devices between the first state and the second state until at least one of a predetermined timeout period has expired and a connection between the devices has been established, a length of time that each of the devices remains in its present state being at least partially determined by one or more predefined probability distributions.

9. The method of claim 8, wherein each of the devices includes a probability distribution associated therewith for separately controlling the length of time that the device remains in its present state.

10. The method of claim 8, further comprising the steps of:

electing a coordinator, the coordinator being a device selected from the plurality of devices and storing information corresponding to each of the devices;

assigning one of a master role, a slave role, and a bridge role to each of the devices, the roles being assigned by the coordinator in accordance with predefined rules; and

connecting the devices together in accordance with the role assignment for each device to form a wireless network.

11. The method of claim 10, wherein the step of electing a coordinator comprises the steps of:

establishing a point-to-point connection between two devices;

determining a winning device and a losing device in accordance with predetermined criteria;

receiving, from the losing device, information relating to the losing device and any devices that the losing device has previously established a connection with; and

repeating the coordinator election steps until all devices have been accessed.

12. The method of claim 11, further comprising the step of disabling the losing device from further participating in the coordinator election process after receiving the information relating to the losing device and any devices that the losing device has previously accessed.

13. The method of claim 11, wherein the step of determining the winning device further comprises comparing information corresponding to each of the plurality of devices.

14. Apparatus for connecting a first device to a second device via a wireless communication channel, the apparatus comprising:

at least one processor operative to;

(i) arbitrarily assign one of a first state and a second state to the first device, wherein in the first state the first device seeks to establish a connection with the second device, and in the second state the first device renders itself available for connection with the second device; and

(ii) alternate a present state of the first device between the first state and the second state in accordance with a probability distribution until at least one of a predetermined timeout period has expired and a connection with the second device has been established, the length of time that the first device remains in the first and second states being at least partially controlled by the probability distribution.

15. The apparatus of claim 14, further comprising at least one input/output (I/O) device operatively coupled to the processor for entering data to the processor, the data modifying at least one parameter associated with the probability distribution for affecting the length of time that the first device remains in the first and second states.

16. The apparatus of claim 15, further comprising a memory operatively coupled to the at least one processor, the memory storing at least one of the probability distribution and the entered data.

17. The apparatus of claim 14, wherein the at least one processor is further operative to:

(iii) initialize an elapsed time counter; and

(iv) periodically measure an elapsed time from the counter to determine whether the predetermined timeout period has been exceeded.

18. The apparatus of claim 14, wherein the first device includes a Bluetooth-enabled device.

19. Apparatus for establishing a connection between a plurality of devices via at least one wireless communication channel, the apparatus comprising:

at least one processor operative to;

(i) arbitrarily assign one of a first state and a second state to each of the devices, wherein in the first state a device seeks to discover and establish a connection with another device, and in the second state the device renders itself available for discovery and connection with another device; and

(ii) alternate a present state of each of the devices between the first state and the second state until at least one of a predetermined timeout period has expired and a connection between the devices has been established, a length of time that each of the devices remains in its present state being at least partially determined by one or more predefined probability distributions.

20. The apparatus of claim 19, wherein the processor is further operative to:

(iii) elect a coordinator, the coordinator being a device selected from the plurality of devices and storing information corresponding to each of the devices;

(iv) assign one of a master role, a slave role, and a bridge role to each of the devices, the roles being assigned by the coordinator in accordance with predefined rules; and

(v) connecting the devices together, in accordance with the role assignment for each device, to form a wireless network.