Decentralized Media Access Control for Ad-Hoc Mobile Wireless Network

• US 20090103501A1
• Filed: 10/22/2007
• Published: 04/23/2009
• Est. Priority Date: 10/22/2007
• Status: Active Grant

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Farrag, Osama I., Benmohamed, Lotfi, D'Amico, William P.
• Granted Patent: US 7,881,340 B2
• Time in Patent Office: Days
• US Class Current: 370/337
• CPC Class Codes: H04W 74/02 Hybrid access

Abstract

A method of operating a decentralized ad-hoc wireless network including wireless stations, comprises establishing a common time reference which is used by the wireless stations to share access to a common wireless channel, the common time reference having a periodic superframe structure including a Scheduled Beacon Period, a Contended Beacon Period, Contention Periods (CPs) and Contention Free Periods (CFPs). The method further comprises time-scheduling, using wireless communication between the wireless stations, the CFPs in the SBTT interval to at least some of the wireless stations requesting access to the CFPs, and granting access to the CPs to at least some of the wireless stations requesting access to the CPs.

Claims

1. A method of operating a decentralized ad-hoc wireless network including wireless stations, each of the wireless stations including a wireless transceiver configured to wirelessly communicate with each of the other wireless stations over a common wireless channel, comprising:

establishing, through wireless communication between the wireless stations, a common time reference among the wireless stations, which is used by the wireless stations to share access to the common wireless channel, the common time reference having a periodic superframe structure based on a repeating Scheduled Beacon Transmit Time (SBTT) interval, the SBTT interval including

a Scheduled Beacon Period near a start time of the SBTT interval during which only one of the wireless stations is scheduled to transmit a Scheduled Beacon Message to all of the other wireless stations, the Scheduled Beacon Message including wireless network information used by the wireless stations for managing the wireless stations in the ad-hoc network and controlling access of the wireless stations to the shared channel,

a Contended Beacon Period, following the Scheduled Beacon Period, during which each of the wireless stations that failed to receive the Scheduled Beacon Message, if any, transmits a respective Contended Beacon Message in contention with any of the other wireless stations that also failed to receive the Scheduled Beacon Message, and

following the Contended Beacon Period,

Contention Periods (CPs) during each of which the wireless stations may contend with each other for access to the common wireless channel for communication with each other over the common wireless channel, and

Contention Free Periods (CFPs) during each of which only one of the wireless stations is scheduled for access to the common wireless channel for communication with each other over the common wireless channel;

granting access, using wireless communication between the wireless stations, to the CPs to at least some of the wireless stations requesting the access to the CPs; and

time-scheduling, using wireless communication between the wireless stations, the CFPs to at least some of the wireless stations requesting access to the CFPs.

2. The method of claim 1, wherein said establishing includes transmitting the Scheduled Beacon Message from each of the wireless stations one after the other in a specific order in successive SBTT intervals according to a Beacon Schedule shared in common across the wireless stations.

3. The method of claim 2, wherein each of the wireless stations is uniquely identified by an address, and wherein the Beacon Schedule includes a list of the addresses of the wireless station arranged so as to indicate the specific order in which the wireless stations are to transmit the Scheduled Beacon Message in the successive SBTT intervals.

4. The method of claim 2, wherein the Scheduled Beacon Message further includes

a Contention Free Period Schedule (CFPS) for a current SBTT interval, wherein the CFPS

defines a timing of the CFPs in the current SBTT interval, and

identities of the wireless stations allocated thereto.

5. The method of claim 2, wherein said scheduling of the CFPs includes transmitting, in the Schedule Beacon Message, a Contention Free Period Schedule (CFPS), the CFPS defining for each said Contention Free Period (CFP) in a current SBTT interval:

(i) when that CFP occurs in the current SBTT interval;

(ii) a duration of that CFP; and

(iii) an identity of the wireless station to which that CFP is assigned for non-contended access to the shared communication channel during that CFP.

6. The method of claim 2, wherein said establishing includes transmitting, during the Contended Beacon Period by each of the wireless stations that failed to receive the Scheduled Beacon Message, if any, a respective Contended Beacon Message in contention with any of the other wireless stations that also failed to receive the Scheduled Beacon Message.

7. The method of claim 6, further comprising, suspending transmission of the Contended Beacon by a wireless station that failed to receive the Scheduled Beacon Message when that wireless station detects that a Contended Beacon was transmitted earlier from another wireless station.

8. The method of claim 2, wherein the Contended Beacon includes

a Beacon Schedule defining the specific order in which the wireless stations are to transmit the Scheduled Beacon Message in the successive SBTT intervals, and

a Contention Free Period Schedule (CFPS) for a current SBTT interval, the CFPS defining a timing of the CFPs for the current SBTT interval and identities of wireless stations allocated thereto for contention free access to the shared communication channel.

9. The method of claim 1, wherein the CFPs are non-contiguous and adjacent CFPs in an SBTT interval are separated from each other by a CP.

10. A method of operating a decentralized ad-hoc wireless network including wireless stations, each of the wireless stations including a wireless transceiver configured to wirelessly communicate with each of the other wireless stations over a common wireless channel, comprising:

establishing, by wireless communication between the wireless stations, a common time reference which is used by the wireless stations to share access to the common wireless channel, the common time reference having a periodic superframe structure based on a repeating Scheduled Beacon Transmit Time (SBTT) interval, the SBTT interval including

a Scheduled Beacon Period near a start of the SBTT interval during, in any given SBTT interval, only one of the wireless stations is scheduled to transmit a Scheduled Beacon Message to all of the other wireless stations,

a Contended Beacon Period, following the Scheduled Beacon Period, during which each of the wireless stations that failed to receive the Scheduled Beacon Message, if any, transmits a respective Contended Beacon Message in contention with any of the other wireless stations that also failed to receive the Scheduled Beacon Message, and

following the Contended Beacon Period,

Contention Periods (CPs) during each of which the wireless stations may contend with each other for access to the common channel for communication with each other over the common channel, and

Contention Free Periods (CFPs) during each of which only one of the wireless stations is scheduled for access to the common channel for communication with each other over the common channel; and

transmitting the Scheduled Beacon Message from each of the wireless stations one after the other in a specific order in successive SBTT intervals, the Scheduled Beacon Message including

a Beacon Schedule identifying the wireless stations and defining the specific order in which the wireless stations are to transmit the Scheduled Beacon Message in the successive SBTT intervals, and

a Contention Free Period Schedule (CFPS) for a current SBTT interval, the CFPS defining a timing of the CFPs for the current SBTT interval and identities of wireless stations allocated thereto for contention free access to the shared communication channel.

11. The method of claim 10, further comprising:

maintaining, in each of the wireless stations, local copies of each of the Beacon Schedule and the CFPS;

determining differences between the local copies of the Beacon Schedule and the CFPS and the Beacon Schedule and the CFPS in the Scheduled Beacon Message transmitted in the current SBTT interval; and

updating the local copies of the Beacon Schedule and the CFPS so as to minimize the determined differences.

12. The method of claim 10, further comprising

maintaining, in each of the wireless stations, local copies of each of the Beacon Schedule and the CFPS;

and

for each wireless station, transmitting during a CFP in a current SBTT interval only when all of (i) the local copy of the CFPS for that wireless station, (ii) the Scheduled Beacon Message received by that wireless station in the current SBTT interval, if any, and (iii) any Contended Beacon Messages received by that wireless station in the current SBTT interval, indicate, in agreement, that the wireless station is scheduled to transmit in that CFP.

13. The method of claim 10, further comprising, for each wireless station, not transmitting during a CFP in a current SBTT interval when (i) the local copy of the CFPS for that wireless station, (ii) the Scheduled Beacon Message received by that wireless station in the current SBTT interval, if any, or (iii) any Contended Beacon Messages received by that wireless station in the current SBTT interval, indicates that another wireless station is scheduled to transmit in that CFP.

14. The method of claim 10, further comprising, permitting each wireless station to transmit non-Beacon Message data on the common wireless channel using CSMA/CA contention access during any time period within a current SBTT interval if the time period will not overlap the Scheduled Beacon Period, the Contended Beacon Period, nor any CFP listed in the local CFPS for that wireless station or any CFP listed in the Scheduled Beacon Message or any Contended Beacon Message received during the current SBTT interval.

15. A network that uses a common wireless channel, comprising:

wireless stations each having a wireless transceiver configured to wirelessly communicate with each of the other wireless stations over the common wireless channel, the wireless stations configured to establish, through wireless communication between themselves, a common time reference among themselves, which is used by the wireless stations to share access to the common wireless channel, the common time reference having a periodic superframe structure based on a repeating Scheduled Beacon Transmit Time (SBTT) interval, the SBTT interval including

a Scheduled Beacon Period near a start time of the SBTT interval during which only one of the wireless stations is scheduled to transmit a Scheduled Beacon Message to all of the other wireless stations, the Scheduled Beacon Message including wireless network information used by the wireless stations for managing the wireless stations in the ad-hoc network and controlling access of the wireless stations to the shared channel,

a Contended Beacon Period, following the Scheduled Beacon Period, during which each of the wireless stations that failed to receive the Scheduled Beacon Message, if any, transmits a respective Contended Beacon Message in contention with any of the other wireless stations that also failed to receive the Scheduled Beacon Message, and

following the Contended Beacon Period,

Contention Periods (CPs) during each of which the wireless stations may contend with each other for access to the common wireless channel for communication with each other over the common wireless channel, and

Contention Free Periods (CFPs) during each of which only one of the wireless stations is scheduled for access to the common wireless channel for communication with each other over the common wireless channel,

wherein the wireless stations time-schedule, using wireless communication between the wireless stations, the CFPs in the SBTT interval to at least some of the wireless stations requesting access to the CFPs.

16. The network of claim 15, wherein the wireless stations establish the common time reference by transmitting the Scheduled Beacon Message from each of the wireless stations one after the other in a specific order in successive SBTT intervals according to a Beacon Schedule shared in common across the wireless stations.

17. The network of claim 16, wherein each of the wireless stations is uniquely identified by an address, and wherein the Beacon Schedule includes a list of the addresses of the wireless station arranged so as to indicate the specific order in which the wireless stations are to transmit the Scheduled Beacon Message in the successive SBTT intervals.

18. The network of claim 16, wherein the Scheduled Beacon Message further includes

a Contention Free Period Schedule (CFPS) for a current SBTT interval, wherein the CFPS

defines a timing of the CFPs in the current SBTT interval, and

identities of the wireless stations allocated thereto.

19. A network that uses a common wireless channel, comprising:

wireless stations each having a wireless transceiver configured to wirelessly communicate with each of the other wireless stations over the common wireless channel, the wireless stations configured to establish, through wireless communication between themselves, a common time reference among themselves, which is used by the wireless stations to share access to the common wireless channel, the common time reference having a periodic superframe structure based on a repeating Scheduled Beacon Transmit Time (SBTT) interval, the SBTT interval including

a Scheduled Beacon Period near a start of the SBTT interval during, in any given SBTT interval, only one of the wireless stations is scheduled to transmit a Scheduled Beacon Message to all of the other wireless stations,

a Contended Beacon Period, following the Scheduled Beacon Period, during which each of the wireless stations that failed to receive the Scheduled Beacon Message, if any, transmits a respective Contended Beacon Message in contention with any of the other wireless stations that also failed to receive the Scheduled Beacon Message, and

following the Contended Beacon Period,

Contention Periods (CPs) during each of which the wireless stations may contend with each other for access to the common channel for communication with each other over the common channel, and

Contention Free Periods (CFPs) during each of which only one of the wireless stations is scheduled for access to the common channel for communication with each other over the common channel,

wherein the wireless stations take turns transmitting the Scheduled Beacon Message one after the other in a specific order, the Scheduled Beacon Message including

a Beacon Schedule defining the specific order in which the wireless stations are to transmit the Scheduled Beacon Message, and

a Contention Free Period Schedule (CFPS) for a current SBTT interval, the CFPS defining a timing of the CFPs for the current SBTT interval and identities of wireless stations allocated thereto for contention free access to the shared communication channel, and

wherein the wireless stations schedule the CFP in the SBTT interval to at least some of the wireless stations requesting access to the common wireless channel, and

wherein the wireless stations each maintain therein local copies of the Beacon Schedule and CFPS.

20. The network of claim 19, wherein each of the wireless stations:

determines differences between the local copies of the Beacon Schedule and the CFPS and the Beacon Schedule and CFPS in the Scheduled Beacon Message transmitted in the current SBTT interval; and

updates the local copies of the Beacon Schedule and CFPS so as to minimize the determined differences.

21. The network of claim 19, wherein:

each wireless station transmits during a CFP in a current SBTT interval only when all of (i) the local copy of the CFPS for that wireless station, (ii) the Scheduled Beacon Message received by that wireless station in the current SBTT interval, if any, and (iii) any Contended Beacon Messages received by that wireless station in the current SBTT interval, indicate, in agreement, that the wireless station is scheduled to transmit in that CFP; and

wherein each wireless station does not transmit during a CFP in a current SBTT interval when (i) the local copy of the CFPS for that wireless station, (ii) the Scheduled Beacon Message received by that wireless station in the current SBTT interval, if any, or (iii) any Contended Beacon Messages received by that wireless station in the current SBTT interval, indicates that another wireless station is scheduled to transmit in that CFP.

22. A network, comprising:

at least one Independent Basic Service Set (IBSS), where an IBSS includes member wireless communication stations (WSs) that share access to a common wireless channel, the WSs including

one or more Channel Resources Allocation and Management (CRAM) stations that each perform CRAM functions, the CRAM stations including an initiator WS (IWS) that initially formed the IBSS, and

non-CRAM stations, if any, that do not perform CRAM functions, wherein the CRAM functions include;

establishing, through wireless inter-communication with the other CRAM stations over the wireless channel, a common time reference for the IBSS including a repeating SBTT interval, the SBTT interval including

a period for a Beacon Message during which only one of the wireless stations is scheduled to transmit a Beacon Message,

Contention Free Periods (CFPs) during which only one of the wireless stations is scheduled for non-contended access to the wireless channel,

Contention Periods (CPs) during which the wireless stations may contend with each other for access to the wireless channel;

transmitting a Beacon Message including

an IBSS Beacon Schedule (IBS) identifying the CRAM stations and an order in which they are to transmit their respective Beacon Messages in successive SBTT intervals, and

a Contention Free Period Schedule (CFPS) that defines a timing of the CFPs in the current SBTT interval, and identities of the wireless stations allocated thereto; and

scheduling WSs to the CFPs,

wherein each CRAM station performs the CRAM functions only when it is no more than a first predetermined number of hops away from the IWS and no more than a second predetermined number of hops away from at least one other of the CRAM stations.

23. The network of claim 22, wherein a CRAM station that is a member of a first IBSS transitions to a border state in which it stops transmitting Beacon Messages if that CRAM station

is more than the first predetermined number of hops away from the IWS for the first IBSS for a predetermined number of SBTT intervals, or

receives Beacon Messages from a second IBSS, of which the CRAM wireless station is not a member, that is a dominant over the first IBSS, wherein the second IBSS is dominant if

the Beacon Messages in the second IBSS indicate a higher number of CFPs in the second IBSS than that of the first IBSS, or

if the number of CFPs is the same, then the number of CRAM stations in the second IBSS is higher than that of the first IBSS, or

if both the number of CFPs and the number of CRAM stations are the same, then an address identifying the IWS of the first IBSS and an address identifying the IWS of the second IBSS have a predetermined relationship to each other.

24. The network of claim 23, wherein the CRAM station, from the border state, joins the dominant second IBSS, and thereby becomes a member of the second IBSS, if the CRAM station is no more than the first predetermined number of hops away from the IWS of the second IBSS, wherein the CRAM station is added to the IBS of the second IBSS and begins transmitting Beacon Message in the second IBSS according to the common time reference of the second IBSS.

25. The network of claim 23, wherein:

the CRAM station, from the border state, becomes an initiator WS and forms a new IBSS when the CRAM station fails to receive a predetermined number of Beacon Messages from the first IBSS, wherein, as the IWS of the new IBSS, the CRAM station begins transmitting Beacon Messages for the new IBSS so as to align a start of an SBTT interval of the new IBSS within a randomly selected CP of the first IBSS, and wherein the CFPS of the new IBSS includes every CFP listed in the CFPS of the first IBSS, and wherein, for each CFP listed in the CFPS of the new IBSS, a time offset of the CFP from a start time of the SBTT interval for the new IBSS is such that the CFP in the new IBSS will occur at the same absolute time at which it would have occurred in the first IBSS; and

CRAM stations and non-CRAM stations from the first IBSS that receive Beacon Messages from the first IBSS and at least one other IBSS transmits periodically in a Contention Period common to both the first IBSS and the other IBSS an IBSS-Borders-Exposed-CFPS message, including a CFPS for the first IBSS and a time offset from a start of the SBTT interval of the first IBSS in during which the IBSS-Borders-Exposed-CFPS is transmitted.