Scalable media access control for multi-hop high bandwidth communications

• US 7,957,356 B2
• Filed: 08/04/2006
• Issued: 06/07/2011
• Est. Priority Date: 05/13/2002
• Status: Active Grant

• Current Assignee: CommWorks Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Misomino CHI Acquisitions LLC
• Inventors: Wang, Weilan, Nova, Michael, Gui, Chao, Patil, Abhishek, Wang, Xudong
• Primary Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US11/462,663
• Publication Number:
  US 20060268908A1
• Time in Patent Office: 1,768 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/431, 370/442, 370/443, 370/445, 370/447, 370/337, 370/336, 370/345, 370/347, 370/329, 370/330, 370/338, 370/341, 370/351, 370/389, 370/390, 370/401, 370/448, 370/457, 370/458, 370/459, 370/461, 370/462, 370/349, 370/254, 370/238, 455/41.2, 455/450, 455/451, 455/452.1, 455/452.2
• US Class Current: 370/338
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/829 Topology based
• CPC Class Codes: H04W 28/086 among access entities
• CPC Class Codes: H04W 28/24 Negotiating SLA [Service Level Agreement]; Negotiating QoS [Quality of Service]
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/20 : Control channels or signalling for resource management
• CPC Class Codes: H04W 72/542 : using measured or perceived quality
• CPC Class Codes: H04W 74/0816 : with collision avoidance
• CPC Class Codes: H04W 76/18 : Management of setup rejection or failure
• CPC Class Codes: H04W 8/04 : Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 80/02 : Data link layer protocols
• CPC Class Codes: H04W 84/18 : Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 : in wireless communication networks

Abstract

A scalable medium access control (“MAC”) module is provided that avoids conflict resource reservation so that network performance does not degrade as the number of hops or nodes in a wireless network increases. The MAC also provides different access schemes for traffic with different quality of service (“QoS”) requirements such that QoS is guaranteed and network resources are efficiently utilized. Furthermore, the resource allocation scheme determines the routing path as resources is allocated for data traffic, thereby achieving more robust layer-2 routing at the MAC layer. Finally, the scalable MAC is compliant with both WiMedia MAC and IEEE 802.15.3 MAC.

Claims

1. A medium access control communication module system configured to be deployed in a wireless communication device capable of communication over a wireless mesh communication network comprising:

a topology module configured to parse a beacon signal to obtain information about nodes in the wireless mesh communication network, the topology module further configured to allocate timeslots for data communication;

a signaling module configured to send control messages to and receive control messages from one or more nodes in the wireless mesh communication network, the signaling module further configured to send routing messages to and receive routing messages from one or more nodes in the wireless mesh communication network; and

a resource allocation module configured to, responsive to receiving a request from a higher-layer protocol to establish a new connection, reserve data transmission resources in the wireless mesh communication network using fair resource allocation for any best effort traffic indicated in the request and using end-to-end admission control for any reliable transmission traffic indicated in the request.

2. The system of claim 1, wherein the topology module further comprises a beacon module configured to analyze the signal quality of a wireless link that provides the beacon signal, and to parse only those beacon signals that are provided by wireless links having a signal quality greater than a minimum signal quality level to maintain a connection.

3. The system of claim 1, wherein the topology module allocates timeslots in an interleaved manner so as to reserve non-contiguous timeslots distributed throughout a contention free period.

4. The system of claim 1, wherein the resource allocation module further comprises a best effort traffic module configured to reallocate timeslots between a plurality of links to improve best effort traffic communications.

5. The system of claim 1, wherein the resource allocation module further comprises a reliable traffic module configured to establish an end-to-end route between a first node and an end node in the wireless mesh communication network and confirm sufficient resource allocation at each node in the path between the first node and the end node, via control messages, prior to initiating reliable transmission of data to meet a predetermined quality of service level.

6. The system of claim 1, wherein best effort traffic is indicated in the request, and

wherein the resource allocation module reserves data transmission resources using fair resource allocation for best effort traffic by scheduling data transmissions in next available time slots that are not reserved for reliable end-to-end transmission during a contention free period to a next hop device without considering the availability of resources beyond the next hop device.

7. The system of claim 1, wherein reliable transmission traffic is indicated in the request, and

wherein the resource allocation module reserves data transmission resources using end-to-end admission control by transmitting a message with an ultimate destination the same as that included in the request for a new connection, the message requesting reservation of time slots at each link between the system and the ultimate destination.

8. The system of claim 7, wherein the resource allocation module is further configured to wait for a resource allocation success message from the ultimate destination device before establishing the new connection.

9. The system of claim 7, wherein the resource allocation module is further configured to, responsive to receiving a resource allocation failure message, inform the higher-layer protocol of the failure to establish the new connection using reliable transmission traffic.

10. The system of claim 1, wherein the signaling module is further configured to inform all one-hop devices of the data transmission resources reserved by the resource allocation module.

11. The system of claim 10, wherein the signaling module is further configured to inform all two-hop devices of the data transmission resources reserved by the resource allocation module.

12. A wireless communication device for transmitting data to a second wireless communication device via a wireless communication network, the wireless communication device comprising:

a radio configured to communicate with one or more intermediate wireless communication devices over the wireless communication network via MAC protocol superframes, each superframe comprising a beacon period in which network topology information and timeslot utilization information is broadcast, a contention access period during which access to the medium is provided via carrier sense multiple access/collision avoidance (“

CSMA/CA”

), and a contention free period during which access to the medium is provided via time division multiple access (TDMA);

a media access control (MAC) module configured for multi-hop wireless communications with the one or more intermediate wireless communication devices using said radio, and configured to exchange and process routing information with wireless communication devices within communication range at the MAC layer; and

a resource allocation module configured to, responsive to receiving a request from a higher-layer protocol to establish a new connection with the second wireless communication device, reserve data transmission resources with the one or more intermediate devices in the contention free period of one or more MAC protocol superframes using fair resource allocation for any best effort traffic indicated in the request and using end-to-end admission control for any reliable transmission traffic indicated in the request.

13. The device of claim 12, wherein the radio is one selected from the group consisting of an ultra-wide band (UWB) radio, a WiFi radio, and a WiMAX radio.

14. The device of claim 12, wherein the first, intermediate, and second wireless communication devices form a mesh network.

15. The device of claim 12, wherein the initial set of time slots are interleaved.

16. The device of claim 15, wherein the first wireless communications device is further configured to reserve additional timeslots to meet an increased quality of service level between the first and second wireless communications device.

17. The device of claim 16, wherein the additional timeslots are contiguous with the initial set of timeslots so as to maintain the interleaved distribution of time slots in the contention free period.

18. The device of claim 15, wherein the first wireless device is further configured to cause the selected initial set of timeslots to be broadcast in a subsequent beacon period.

19. The device of claim 12, wherein the first wireless communications device is configured to align a MAC layer superframe with a superframe from the second wireless communications device one, the superframe being comprised of the beacon period, the contention access period, and the contention free period.

20. The device of claim 12, wherein the resource allocation module further comprises a best effort traffic module configured to reallocate timeslots between a plurality of links to improve best effort traffic communications.

21. The device of claim 12, wherein the resource allocation module further comprises a reliable traffic module configured to establish an end-to-end route between the wireless communication device and the second wireless communication device in the wireless communication network and confirm sufficient resource allocation at each node in the path between the wireless communication device and the second wireless communication device, via control messages, prior to initiating reliable transmission of data to meet a predetermined quality of service level.

22. The device of claim 12, wherein best effort traffic is indicated in the request, and

wherein the resource allocation module reserves data transmission resources using fair resource allocation for best effort traffic by scheduling data transmissions in next available time slots that are not reserved for reliable end-to-end transmission during a contention free period to a next hop device without considering the availability of resources beyond the next hop device.

23. The device of claim 12, wherein reliable transmission traffic is indicated in the request, and

wherein the resource allocation module reserves data transmission resources using end-to-end admission control by transmitting a message with an ultimate destination the same as that included in the request for a new connection, the message requesting.

24. A medium access control communication module system configured to be deployed in a wireless mesh communication device capable of communication over a wireless mesh communication network, the module comprising:

a beacon module configured to parse a beacon signal broadcast in a beacon period of a MAC protocol superframe to obtain information about nodes in the wireless mesh communication network and determine allocated timeslots in a contention free period of the MAC protocol superframe already in use by the nodes;

a topology module configured to allocate an initial set of timeslots from currently un-allocated timeslots available in the contention free period for data communication with the nodes;

a signaling module configured to send control messages to and receive control messages from one or more nodes in the wireless mesh communication network, the signaling module further configured to send routing messages to and receive routing messages from one or more nodes in the wireless mesh communication network at the MAC layer; and

a resource allocation module configured to, responsive to receiving a request from a higher-layer protocol to establish a new connection, reserve data transmission resources not determined to already be allocated to other nodes in the wireless mesh communication network using fair resource allocation for any best effort traffic indicated in the request and using reserved end-to-end admission control for any reliable traffic indicated in the request.

25. The system of claim 24, wherein the topology module is configured to allocate additional timeslots to meet an increased quality of service level.

26. The system of claim 25, wherein the initial set of timeslots are selected in an interleaved manner, and the additional timeslots are selected at an offset from the initial set of timeslots so as to maintain the interleaved distribution of time slots in the contention free period.

27. The system of claim 24, wherein the system is configured to align a MAC layer superframe with one or more superframes from the one or more nodes, the superframe being comprised of the beacon period, a contention access period during which access to the medium is provided via carrier sense multiple access/collision avoidance (“

CSMA/CA”

), and the contention free period during which access to the medium is provided via time division multiple access (TDMA).

28. The system of claim 24, wherein the topology module is further configured to cause the selected initial set of timeslots to be broadcast in a subsequent beacon period.

29. The system of claim 24, wherein best effort traffic is indicated in the request, and

wherein the resource allocation module reserves data transmission resources using fair resource allocation for best effort traffic by scheduling data transmissions in next available time slots that are not reserved for reliable end-to-end transmission during a contention free period to a next hop device without considering the availability of resources beyond the next hop device.

30. The system of claim 24, wherein reliable transmission traffic is indicated in the request, and

wherein the resource allocation module reserves data transmission resources using end-to-end admission control by transmitting a message with an ultimate destination the same as that included in the request for a new connection, the message requesting reservation of time slots at each link between the system and the ultimate destination.

31. The system of claim 30, wherein the resource allocation module is further configured to wait for a resource allocation success message from the ultimate destination device before establishing the new connection.

32. The system of claim 30, wherein the resource allocation module is further configured to, responsive to receiving a resource allocation failure message, informing the higher-layer protocol of the failure to establish the new connection using reliable transmission traffic.

33. The system of claim 24, wherein the signaling module is further configured to inform all one-hop devices of the data transmission resources reserved by the resource allocation module.

34. A medium access control method in a wireless communication device capable of communication over a wireless mesh communication network, the method comprising:

the wireless communication device parsing a beacon signal to obtain information about nodes in the wireless mesh communication network, and allocating timeslots for data communication;

the wireless communication device sending control messages to and receiving control messages from one or more nodes in the wireless mesh communication network, and sending routing messages to and receiving routing messages from one or more nodes in the wireless mesh communication network; and

the wireless communication device, responsive to receiving a request from a higher-layer protocol to establish a new connection, reserving data transmission resources in the wireless mesh communication network using fair resource allocation for any best effort traffic indicated in the request and using end-to-end admission control for any reliable transmission traffic indicated in the request.

35. The method of claim 34, further comprising the wireless communication device reallocating timeslots between a plurality of links to improve best effort traffic communications.

36. The method of claim 34, further comprising the wireless communication device establishing an end-to-end route between a first node and an end node in the wireless mesh communication network and confirming sufficient resource allocations at each node in the path between the first node and the end node, via control messages, prior to initiating reliable transmission of data to meet a predetermined quality of service level.

37. The method of claim 34, wherein best effort traffic is indicated in the request, and

wherein the wireless communication device reserves data transmission resources for the best effort traffic indicated in the request using fair resource allocation by scheduling data transmissions in next available time slots that are not reserved for reliable end-to-end transmission during a contention free period to a next hop device without considering the availability of resources beyond the next hop device.

38. The method of claim 34, wherein reliable transmission traffic is indicated in the request, and

wherein the wireless communication device reserves data transmission resources for the reliable transmission traffic indicated in the request using end-to-end admission control by transmitting a message with an ultimate destination the same as that included in the request for a new connection, the message requesting reservation of time slots at each link between the system and the ultimate destination.

39. An article of manufacture including a computer readable medium having instructions stored thereon that, in response to execution by a computing device, cause the computing device to perform operations comprising:

parsing a beacon signal to obtain information about nodes in the wireless mesh communication network, and allocating timeslots for data communication;

sending control messages to and receiving control messages from one or more nodes in the wireless mesh communication network, and sending routing messages to and receiving routing messages from one or more nodes in the wireless mesh communication network; and

responsive to receiving a request from a higher-layer protocol to establish a new connection, reserving data transmission resources in the wireless mesh communication network using fair resource allocation for any best effort traffic indicated in the request and using end-to-end admission control for any reliable transmission traffic indicated in the request.

40. The article of manufacture of claim 39, wherein the operations further comprise reallocating timeslots between a plurality of links to improve best effort traffic communications.

41. The article of manufacture of claim 39, wherein the operations further comprise establishing an end-to-end route between a first node and an end node in the wireless mesh communication network and confirming sufficient resource allocations at each node in the path between the first node and the end node, via control messages, prior to initiating reliable transmission of data to meet a predetermined quality of service level.

42. The article of manufacture of claim 39, wherein best effort traffic is indicated in the request, and

wherein reserving data transmission resources further comprises reserving data transmission resources for the best effort traffic indicated in the request using fair resource allocation by scheduling data transmissions in next available time slots that are not reserved for reliable end-to-end transmission during a contention free period to a next hop device without considering the availability of resources beyond the next hop device.

43. The article of manufacture of claim 39, wherein reliable transmission traffic is indicated in the request, and

wherein reserving data transmission resources further comprises reserving data transmission resources for the reliable transmission traffic indicated in the request using end-to-end admission control by transmitting a message with an ultimate destination the same as that included in the request for a new connection, the message requesting reservation of time slots at each link between the system and the ultimate destination.