US 6,587,453 B1Grant
Method of communicating first and second data types
Issue Date:2003-07-01
•18 Claims
•4 Drawing Sheets
Abstract
In a medium access control (MAC) protocol for a wireless communications network, communications between a control point and other nodes are coordinated by a repeated superframe. This superframe contains in sequence a contention-free period (CFP1), a contention-based period, and second contention-free period (CFP2). Prior to CFP1a node hops from one channel frequency to another. CFP2in a superframe is used for initial transmission of isochronous data (such as voice signals); CFP1of the following superframe is used for retransmission of any such data which were not correctly received at the first attempt, after the frequency hop at the start of that following superframe. This arrangement minimises delay before retransmission of data, and improves the robustness of the system.
Metadata
Assignees
- Hewlett-Packard Company
- Symbionics Limited
Inventors
- Christopher Gwyn Romans
- Louis Mario Gaiot
- Kevin James Negus
- Jean Tourrilhes
- Paul John Morris
- Rajinder Gawera
Application Information
Application Number:US 09/213,749
Filing Date:1998-12-17
Priority Date:1997-12-17
Art Unit:7
Classifications
IPC:
H04B 7212
Field of Search:
370336370337370347370442370444370445370446370447370461370478370319370321370344370338370349370350370435370436370458375135375133455 8
Patent Drawings (4 sheets)
Description
TECHNICAL FIELD
[0002] This invention relates to network communications.
DISCLOSURE OF INVENTION
[0003] According to one aspect of this invention there is provided a method of communicating data among a plurality of stations in a network, wherein:
[0004] first data are communicated during a period of a one kind in a communications cycle;
[0005] second data are communicated during a first period of another kind in said cycle, occurring before said period of one kind, and during a second period of the other kind in said cycle, occurring after said period of one kind;
[0006] a change in communications frequency is effected between a said second period in one cycle and a said first period in an immediately following cycle; and
[0007] said first period in a cycle is used for retransmitting data which were not successfully transferred during said second period of an immediately preceding cycle.
[0008] In a specific embodiment, the invention concerns a Medium Access Control (MAC) protocol for a wireless network which can adapt to the type of traffic and support the delivery of both isochronous and asynchronous data.
BRIEF DESCRIPTION OF DRAWINGS
[0009] Methods and apparatus in accordance with this invention for communicating data in a wireless network will now be described, by way of example, with reference to the accompanying drawings, in which:
[0010] FIG. 1 shows a network operating in ad-hoc mode;
[0011] FIG. 2 shows a network operating in managed mode;
[0012] FIG. 3 shows a network operating in managed mode, with a connection to a public switched telephone network (PSTN);
[0013] FIG. 4 shows the composition of a data frame in accordance with the invention;
[0014] FIG. 5 illustrates transmission of a data packet in asynchronous contention-based operation of the network; and
[0015] FIG. 6 illustrates steps involved in re-ordering of protocol connections between nodes.
BEST MODE FOR CARRYING OUT THE INVENTION, & INDUSTRIAL APPLICABILITY
[0016] This invention provides a medium access control (MAC) protocol which enables a wireless network to carry both isochronous (e.g voice) and asynchronous (data) traffic. Elements of the protocol include:
[0017] A “superframe” which is repeated periodically;
[0018] A contention-free service used to support the delivery of isochronous data;
[0019] A contention-based service used to support the delivery of asynchronous data;
[0020] A contention-free period at the end of the superframe in which isochronous data are transmitted. All data transmitted are acknowledged. If the data are not acknowledged they are repeated in a contention-free period at the start of the next superframe period.
[0021] In a Frequency Hopping system where the superframe equals the dwell period (the duration of operation at any one frequency, including the time taken to hop to that frequency), data are retransmitted on a different frequency providing frequency diversity and robustness. If there are no data to be retransmitted the duration of the contention-free period at the start of the superframe is zero.
[0022] The contention period occupies the time remaining between the two contention-free periods.
[0023] To support the isochronous data service a Beacon (CPB) is transmitted by a Control Point (CP) at the start of the superframe. The Beacon defines the duration of each of the three periods.
[0024] If no isochronous data are to be transmitted the contention period can occupy the whole superframe.
[0025] A Control Point is required to support the isochronous service. However a Control Point is not required for network operation; if no CP is present then the network supports the asynchronous data service only and operates as an ad-hoc network.
Network Topology
[0026] There can be four different station types in a network:
[0027] A Control Point which provides support for isochronous services.
[0028] An Isochronous Data Terminal or Voice Terminal. This only uses the time division multiple access (TDMA) mechanism in the contention-free period to communicate with a Control Point.
[0029] A Data Node. A data node only uses the carrier sense multiple access/collision avoidance (CSMA/CA) mechanism in the contention period and can communicate with a Control Point and other data nodes.
[0030] A Voice and Data Node. This can use both access mechanisms.
[0031] The network can operate as either an ad-hoc network or as a managed network under the control of a Control Point. In an ad-hoc network all stations are equal (see FIG. 1) and control of the network is distributed between the stations. If a CP is present, as shown in FIG. 2, then the network is termed a managed network and can support isochronous voice services as well as asynchronous data services. The network may have a connection to external services, as shown in FIG. 3.
MAC Layer
[0032] The MAC is designed to provide two services:
[0033] An asynchronous contention-based (CSMA/CA) data service.
[0034] An isochronous contention-free (TDMA) voice service.
[0035] The MAC protocol is designed to operate in the presence of other RF systems and interference sources (e.g. microwave ovens) and therefore includes selective re-transmission of data.
[0036] The MAC protocol uses a superframe which incorporates two contention-free periods (CFP) and a contention period. The start of the superframe is the point at which a station begins to hop to a new channel and ends immediately before the station starts to hop to the next channel. The duration of the superframe is fixed and is the same as the dwell period. The access mechanism used during each CFP is TDMA, whilst the access mechanism used during the contention period is CSMA/CA. FIG. 4 shows the overall structure of the superframe.
[0037] The contention-free periods (CFP1 before the contention period and CFP2 after it) are only applicable in the case of a Managed Network. If no Control Point is present then the CSMA/CA contention period occupies the whole superframe and the network operates as an ad-hoc network.
[0038] Short Inter-Frame Space (SIFS) Period: This is the time required to switch between receive mode and transmit mode.
[0039] Default Inter-Frame Space (DIFS) Period: When the channel is free for a DIFS period it indicates that the previous packet exchange is complete and other nodes may contend for the channel.
[0040] Slot Time: The slot time is the time required for a node to sample the channel, determine its state and either prepare for transmission or hold off.
TDMA Access Mechanism
[0041] Access to the medium during the CFPs is managed by a Control Point using the Control Point Beacon (CPB). The CPB is transmitted at the start of each superframe and specifies the number of active TDMA connections (which dictates the length of CFP2) and whether any re-transmissions are required (which dictates the length of CFP1).
[0042] Each CFP is divided into a variable number of pairs of fixed length TDMA slots, one pair per TDMA connection. The first slot in each pair is used by the CP to transmit to a node (the downlink slot) and the second slot is used by the node to transmit to the CP (the uplink slot).
[0043] CFP1 starts immediately after the end of the Beacon. The duration of CFP1 is:
[0044] (Number of connections*2) * (SIFS+Duration of TDMA Voice Data message)
[0045] The start of CFP2 occurs one SIFS period before the first downlink transmission from the CP. The start of CFP2 is measured from the start of the Hop. Its duration is also:
[0046] (Number of connections*2) * (SIFS+Duration of TDMA Voice Data message)
[0047] The CFP at the end of the superframe (CFP2) is used for the initial transmission of TDMA data. The CFP at the beginning of the superframe (CFP1) is used for the retransmission of TDMA data which were not received correctly. The two CFPs are separated by a hop (giving frequency diversity), and since retransmission of a TDMA packet occurs soon after initial transmission, retransmission delays are minimised.
[0048] The service slot is used by a voice terminal to send management messages to a Control Point.
[0049] Voice data are transmitted in a TDMA uplink or downlink slot using the Voice Data message.
[0050] Acknowledgment and Re-transmission Procedure
[0051] If a Voice Terminal does not receive an expected Voice Data packet, or receives a Voice Data packet with an incorrect CRC, then it sets the TDMA Resend bit in the TDMA Control Field of the next Voice Data packet it transmits to the CP (transmitted immediately in the associated uplink slot).
[0052] During CFP2 if a CP:
[0053] 1. does not receive an expected Voice Data packet;
[0054] 2. receives a Voice Data packet with an incorrect Cyclic Redundancy Check (CRC) code; or
[0055] 3. receives a Voice Data packet in which the TDMA Resend flag is set; then it will reserve a pair of slots in the re-transmission period (CFP1) for re-transmission of both the uplink and downlink data. In cases (1) and (2) the CP sets the TDMA Resend flag in the TDMA Control Field of the Voice Data packet re-transmitted to the Voice Terminal.
[0056] Only a single re-transmission of a Voice Data packet is supported. If the re-transmission of a packet fails then the failed packet is discarded.
[0057] It is possible for both the CP and TDMA terminal to receive duplicate messages during the re-transmission period; such duplicate messages are discarded.
[0058] Service Slot
[0059] To set up connections voice terminals need to communicate with a CP. In order to transmit the necessary management messages they use the service slot, which starts a SIFS period immediately after the CPB and any retransmission slots. Any message transmitted in the service slot will pre-empt any CSMA/CA transmissions. Responses to these management messages are contained within the CPB.
[0060] There is a reasonable probability that two TDMA terminals will attempt to transmit at the same time, or that a management message is not received correctly by the CP. In either of these cases the next CPB transmitted by the CP will not include any acknowledgment of the management message transmitted by the TDMA terminal. In this case the TDMA terminal retransmits the management message in a subsequent service slot after performing a random backoff. The TDMA terminal selects a backoff value between 1 and a predetermined maximum and after that number of dwell periods have elapsed retransmits the management message.
[0061] If a node supports both the TDMA and CSMA/CA services, it can also transmit management messages during the contention period.
[0062] Using a TDMA Slot for Management Messages
[0063] A node that has been allocated a connection by a Control Point can use the uplink TDMA slot for management messages. The management message is transmitted in place of a TDMA Data message.
[0064] Missed Control Point Beacons
[0065] If a node has been receiving CPBs and then does not receive a CPB in a dwell period it will use the slot allocation information in the last CPB it received for that dwell period.
[0066] If a node does not receive CPBs for a specified period then it will assume that it is itself no longer part of a managed network.
CSMA/CA Access Mechanism
[0067] A CSMA/CA access mechanism is used during the contention period of the superframe. FIG. 5 illustrates how the medium is accessed during the contention period. This mechanism is very similar to that defined in the IEEE 802.11 Wireless MAC and Physical Layer (PHY) specification.
[0068] The CSMA/CA access procedure is designed to provide fair access to the medium for all nodes by using a contention window and a backoff mechanism. Before any node transmits a packet it selects a backoff value and then starts listening. When the medium has been clear for a predefined Default Inter-frame Space (DIFS) period it decrements its backoff value for each elapsed free slot. When the backoff value reaches zero the node transmits the message. Whenever the medium is busy the countdown is suspended and only resumes when the medium has been free for a DIFS. This backoff mechanism reduces the probability of collision, and performing a backoff before transmission also ensures that responses from multiple nodes responding to a broadcast message on an otherwise idle network do not all collide.
[0069] Unicast data packets transmitted during the contention period are acknowledged by the recipient. If no acknowledgment is received they are re-transmitted.
[0070] If a retransmission is required because of a collision or transmission failure the size of the contention window is increased from an initial value (e.g. 16) exponentially up to a maximum value (e.g. 128) to avoid congestion.
Packet Format
[0071] The following diagram shows the layout of a MAC packet. Lengths are in octets.
| 2 | 1 | 1 | (0 − MaxMSDULength + 6) | 4 | |
| PHY | Frame | Dest | Source | Body | CRC |
| Hdr | Control | Addr | Addr | (Payload) | |
[0072] Frame Control
[0073] This is used to control the operation of the MAC protocol and includes, but is not limited to, the following fields:
[0074] Packet type;
[0075] TDMA acknowledgement/resend flag: Set, the TDMA packet was received correctly; Clear, no packet was received or a received packet failed the CRC check;
[0076] Sequence number: the sequence number distinguishes a received unicast DATA message from the previous unicast DATA message from the same sending node. MAC Protocol Data Unit (MPDU) retransmissions maintain the same sequence number as the initial transmission;
[0077] Retry flag: the retry bit will be set on all transmissions of a DATA packet which are not the first transmission of that packet.
| Control Point Beacon Format |
| The format of the message payload is: |
[0078] Control Frame
[0079] Each bit in the control frame is used to indicate whether one of the optional parts is present in the Beacon.
| TABLE 1 |
|---|
| Control Point Beacon Control Frame |
[0080] Slot Assignment
[0081] Slots are always assigned in pairs (connections), a downlink slot followed by an uplink slot. The Slot Assignment information is an implicit list of connections and the address of the node allocated to each connection. If a connection is not allocated the address is set to 00h.
| 8 bits | bits | 8 bits | |
|---|---|---|---|
| Length in octets of | Address for | Address for | |
| the slot assignment | connection 1 | connection N | |
| information | |||
[0082] Connection 1 is the pair of slots next to the hop boundary.
[0083] Retransmission Information
[0084] Identifies the nodes which should prepare to receive a retransmission of the data transmitted by the Control Point in the previous dwell period, and also retransmit their own last data transmission to the Control Point. The Retransmission Information is an implicit list of connections and the address of the node allocated to each connection (see Slot Assignment).
[0085] Connection 1 is the pair of slots immediately following the CP Beacon.
[0086] Connection Management Information
[0087] The Connection Management information includes connection notifications and paging requests and consists of a series of 2-tuple fields as follows:
| Node 1 | Node N |
[0088] Valid Event Flags include the following and can be logically OR'd to indicate multiple events.
| Bit Position | Description |
|---|---|
| 0 | Connection Request flag. |
| 1 | Connection Established flag |
| 2 | Connection Denied flag. |
| 3 | Terminate Connection Command. |
| 4-6 | Reserved, set to Zero |
| 7 | Paging Request flag |
[0089] Connection Request flag
[0090] Notifies a TDMA terminal that the Control Point has received a connection request to the node from another source, and has allocated a connection.
[0091] Connection Established flag
[0092] Notifies a TDMA terminal that the Control Point has received a connection request to the node and has allocated a connection.
[0093] Connection Denied flag
[0094] Notifies a TDMA terminal that the Control Point has received a connection request from the node and is unable to allocate a connection.
[0095] Terminate Connection Command
[0096] Notifies a TDMA terminal that the Control Point has terminated a connection and will reallocate the slots/connection.
[0097] Paging Request
[0098] Paging requests are used by the Control Point to determine if a node is present in the network. The addressed node responds to a paging request by sending a Control Point Service (CPS) Request message.
Control Point Operation
[0099] Periodic Transmissions
[0100] A CP transmits a CPB at the start of each and every dwell period.
[0101] TDMA Terminal Connection Request
[0102] A TDMA terminal requiring a TDMA connection to the Control Point will transmit a CPS Request message in the service slot. If there is a connection available the Control Point will allocate two slots to the node, one for downlink and the other for uplink.
[0103] The requesting node is notified by the CP of the success of its request by the CP's setting the Connection Established flag in the CPB. The slots/connection allocated to the node are also included in the Slot Assignment part of the CPB.
[0104] If there are no available slots, the CP will deny the connection request by setting the Connection Denied flag in the CPB. The requesting node may make another request at some later time.
[0105] If the Connection Established flag is not set in the CPB (and no slots are allocated), and the connection request is not denied then the TDMA terminal repeats the CPS Request message.
[0106] Control Point Connection Request
[0107] To establish a connection from a Control Point to a TDMA terminal the CP allocates slots for a connection and sets the Connection Request flag in the CP Beacon for the relevant TDMA terminal.
[0108] The node responds using a CPS Request message transmitted in the uplink slot allocated by the Control Point, each time it receives the connection request.
[0109] If the CP does not receive a CPS Request message from the node after a specified time the connection is deallocated.
[0110] Terminating a Connection
[0111] A TDMA terminal releases a connection by sending a CPS End message to the Control Point in its uplink slot. The message is repeated whilst CP Beacons are received by the node indicating that the connection is still active.
[0112] A CP terminates a connection by sending a Terminate Connection command in the CPB. The TDMA terminal must stop using the connection allocated to it on receipt of the Terminate Connection command and send a CPS End message to the Control Point in its uplink slot. On receipt of the CPS End message the CP will de-allocate the connection. The CPB will repeat the Terminate Connection command for a specified time or until it receives a CPS End message. If the CP has not received a response after a specified time it will de-allocate the slots.
[0113] If the CP does not receive any data from a TDMA terminal for a specified time then it will page the TDMA terminal using the paging facility in the CP Beacon. The node should immediately respond with a CPS Request message in its uplink slot or in the service slot if it wishes to keep its connection. If the Control Point does not receive a CPS Request message or any data from the node after sending a specified number of CP Beacons with the paging bit set it will assume that either the node is no longer in range or the CPS End message(s) sent by the node was never received, and that the connection should be cleared and the slots made available.
[0114] Connection Management
[0115] If a TDMA terminal that has been allocated a connection receives a CPB that does not include the node in the slot allocation list, then the node must stop using the slots it has been using and make a new connection request.
[0116] The Control Point can determine whether TDMA terminals are still active by setting a paging bit in the CPB. A TDMA terminal whose paging bit is set must respond with a CPS Request message.
[0117] If a node misses a specified number of consecutive scheduled CPB messages, it must assume that the current slot number assigned to it is invalid. The node must then stop using that slot and issue a new CPS Request message to get a new connection and slot number.
[0118] Re-ordering Connections
[0119] Once a connection is closed the slots being used for that connection can be reallocated to maximise the duration of the contention period. Only one pair of slots can be reallocated at any time.
[0120] To limit the number of nodes which have to move slots, the node allocated the earliest slots in the CFP is moved to the vacant slots. If it was the connection to this node that was closed then no reallocation of slots is required.
[0121] The Control Point notifies the node of its new slots using the Slot Assignment portion of the Beacon. On receipt of the Beacon the node starts using the new slot and will transmit uplink data in the new slot.
[0122] To ensure that no data are lost during the re-allocation process the Control Point does not de-allocate the old slots assigned to the repositioned node until it receives an uplink message from the node in the new slot. Until it receives this message it transmits downlink data in both the downlink slot of the old connection and the downlink slot of the new connection. Thus if the node does not receive the CPB containing the re-allocation command it can still receive data using its old slots. The slot re-allocation command is repeated until the Control Point receives an uplink message in the new slot.
[0123] FIG. 6 shows an example of the connection re-ordering process.
Claims
What is claimed is:
1. A method of communicating via communication frequencies first and second data types among plural stations of a network comprising
communicating data of the first and second data types between the stations in a series of sequential frames on communication frequencies, each of the frames including sequential periods, each of the frames having a communication frequency,
changing the communication frequency from a first frame in the series to the next frame in the series;
communicating the data of the first data type during one of the periods of each frame;
communicating the data of the second data type during another of the periods of each frame;
repeating the communication of the data of the second data type during an initial period of the next frame if the data of the second data type are not successfully communicated during the another period of the first frame.
2. The method of claim 1, wherein the data of the first data type are communicated during said periods used for contention-based communications.
3. The method of claim 1, wherein the data of the second data type are communicated during said periods used for contention-free communications.
4. The method of claim 3 wherein said second data type is isochronous.
5. The method of claim 1 wherein said first data type is asynchronous.
6. The method of claim 1 wherein the another periods are the final periods of the frames.
7. The method of claim 1 wherein the communications are performed wirelessly.
8. A method of transmitting via communication frequencies isochronous and asynchronous data among a plurality of stations in a network comprising:
transmitting the data in a series of frames, each of the frames having a communication frequency,
changing the communication frequency for data transmission from one frame in the series to the next frame in the series;
during transmission or retransmission of isochronous data, forming at least some of the frames so they include at least a first period, a second period and a third period, the second period occurring after the first period and before the third period;
transmitting the asynchronous data in said second period;
transmitting the isochronous data in said third period; and
retransmitting the isochronous data in the first period of the next frame in the series if the isochronous data are not successfully transmitted in the third period of said one frame.
9. The method of claim 8, further including using a contention-free access mechanism during the first and third periods of each frame.
10. The method of claim 8, further including using a contention access mechanism during the second period of each frame.
11. The method of claim 8, further including forming the frames so that there is no third period in frames that do not include isochronous data.
12. The method of claim 8 further including forming the frames so that if there is no isochronous data to retransmit in a frame there is no first period in that frame.
13. The method of claim 8 wherein isochronous data are considered not to be successfully transmitted if they are not-acknowledged by a recipient to whom the frame is transmitted.
14. The method of claim 8, wherein said frames are transmitted wirelessly.
15. A method of transmitting data among a plurality of stations in a network comprising:
transmitting data in a series of frames, each of the frames having a communication frequency,
changing the communication frequency for data transmission from one frame in the series to the next frame in the series;
during transmission or retransmission of isochronous data, forming at least some of the frames so they include at least a first period, a second period and a third period, the second period occurring after the first period and before the third period;
transmitting asynchronous data in said second period according to a contention access mechanism;
transmitting the isochronous data in said third period according to a contention free access mechanism; and
retransmitting, according to a contention free access mechanism, the isochronous data in the first period of said next frame in the series if the isochronous data are not successfully transmitted in the third period of said one frame.
16. Apparatus for transmitting via communication frequencies first and second data types to at least one other station of a network comprising
a transmitter,
a processor adapted to be responsive to data of the first and second data types for driving the transmitter, the processor being arranged for causing the transmitter to (a) transmit data of the first and second data types to the at least one other station in a series of sequential frames on communication frequencies, each of the frames including sequential periods, each of the frames having a communication frequency, (b) change the communication frequency from a first frame in the series to the next frame in the series, (c) transmit the data of the first data type during one of the periods of each frame, (d) transmit the data of the second data type during another of the periods of each frame, and (e) repeat the communication of the data of the second data type during an initial period of the next frame if the data of the second data type are not successfully communicated during the another period of the first frame.
17. Apparatus for transmitting via communication frequencies isochronous and asynchronous data to at least one other station in a network comprising:
a transmitter,
a processor adapted to be responsive to data of the first and second data types for driving the transmitter, the processor being arranged for causing the transmitter to (a) transmit the data in a series of frames, each of the frames having a communication frequency, (b) change the communication frequency for data transmission from one frame in the series to the next frame in the series, (c) during transmission or retransmission of isochronous data, form at least some of the frames so they include at least a first period, a second period and a third period, the second period occurring after the first period and before the third period, (d) transmit the asynchronous data in said second period, (e) transmit the isochronous data in said third period, and (f) retransmit the isochronous data in the first period of the next frame in the series if the isochronous data are not successfully transmitted in the third period of said one frame.
18. Apparatus for transmitting data to at least one other station in a network comprising:
a transmitter,
a processor adapted to be responsive to data of the first and second data types for driving the transmitter, the processor being arranged for causing the transmitter to (a) transmit data in a series of frames, each of the frames having a communication frequency, (b) change the communication frequency for data transmission from one frame in the series to the next frame in the series, (c) during transmission or retransmission of isochronous data, form at least some of the frames so they include at least a first period, a second period and a third period, the second period occurring after the first period and before the third period, (d) transmit asynchronous data in said second period according to a contention access mechanism, (e) transmit the isochronous data in said third period according to a contention free access mechanism, and (f) retransmit, according to a contention free access mechanism, the isochronous data in the first period of said next frame in the series if the isochronous data are not successfully transmitted in the third period of said one frame.
Patent Citations (11)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US5123029(A) | 1992-06-01 | Bantz et al. | Applicant |
| US5329531(A) | 1994-07-01 | Diepstraten et al. | Examiner |
| US5384777(A) | 1995-01-01 | Ahmadi et al. | Examiner |
| US5862452(A) | 1999-01-01 | Cudak et al. | Examiner |
| US5892769(A) | 1999-04-01 | Lee | Examiner |
| US5953344(A) | 1999-09-01 | Dail et al. | Examiner |
| US6061389(A) | 2000-05-01 | Ishifuji et al. | Examiner |
| US6078609(A) | 2000-06-01 | Nago | Examiner |
| US6141336(A) | 2000-10-01 | Bauchot et al. | Examiner |
| US6275517(B1) | 2001-08-01 | Izumi | Examiner |
| US6275518(B1) | 2001-08-01 | Takahashi et al. | Examiner |