HK1074124B - Method of operating a media access controller - Google Patents

Description

Method of operating a media access controller

Technical Field

This application claims priority to a provisional application entitled "MiniMAC tdmap protocol" filed on 3/10/2001, the disclosure of which is incorporated herein by reference in its entirety.

Background

The present invention relates to wireless personal area networks and wireless local area networks. More particularly, the present invention relates to systems, methods, devices and computer program products for controlling data transmission in a wireless personal network or wireless local area network environment.

The international organization for standardization (ISO) Open Systems Interconnection (OSI) standard provides a 7-layer hierarchy between end users and physical devices that can communicate with different systems. Each layer is responsible for different tasks, and the OSI standard specifies the interactions between layers, and between devices that conform to the standard.

Fig. 1 shows the hierarchy of the 7-layer OSI standard. As can be seen in fig. 1, the OSI standard 100 includes a physical layer 110, a data link layer 120, a network layer 130, a transport layer 140, a session layer 150, a presentation layer 160, and an application layer 170.

The Physical (PHY) layer 110 transmits bit streams at the electrical, mechanical, functional, and process levels through the network. Which provides the hardware means to send and receive data on a carrier. The data link layer 120 describes the representation of bits on the physical medium and the format of messages on the medium, sending blocks of data (e.g., frames) with the appropriate synchronization. The network layer 130 handles the routing and forwarding of data to the appropriate destination, maintaining and terminating connections. The transport layer 140 manages end-to-end control and error checking to ensure complete data transfer. The session layer 150 sets up, coordinates, and ends sessions, exchanges, and dialogs between applications on each end. The presentation layer 160 converts input and output data from one presentation format to another. The application layer 170 is the layer of identifying the communicating parties, identifying quality of service, considering user authentication and privacy, and identifying any restrictions on the data syntax.

The IEEE802 committee has developed a three-layer architecture for local area networks that generally corresponds to the physical layer 110 and the data link layer 120 of the OSI standard 100. Fig. 2 illustrates the IEEE802 standard 200.

As shown in fig. 2, the IEEE802 standard 200 includes a Physical (PHY) layer 210, a Medium Access Control (MAC) layer 220, and a Logical Link Control (LLC) layer 225. The PHY layer 210 basically operates as the physical layer 110 in the OSI standard 100. The MAC and LLC layers 220 and 225 share the functions of the data link layer 120 in the OSI standard 100. The LLC layer 225 places data in frames that can be communicated over the PHY layer 210; and the MAC layer 220 manages communication over the data link, transmitting data frames and receiving Acknowledgement (ACK) frames. The MAC and LLC layers 220 and 225 are responsible for error checking and retransmission of frames that are not received and acknowledged.

Fig. 3 is a block diagram of a wireless network 300 that may use the IEEE802.15 standard 200. In a preferred embodiment, the network 300 is a Wireless Personal Area Network (WPAN) or a piconet. However, it should be appreciated that the invention may also be applied to other arrangements in which bandwidth is shared between several users, such as a Wireless Local Area Network (WLAN) or any other suitable wireless network.

When the term "piconet" is used, it denotes a network of devices connected in an ad hoc (ad hoc) manner, with one device acting as a coordinator (i.e. as a server) and the other devices (sometimes called stations) following the time allocation instructions of the coordinator (i.e. they act as clients). The coordinator may be a designated device or simply a device selected as a coordinator. The main difference between the coordinator and non-coordinator devices is that the coordinator must be able to communicate with all devices in the network, and the various non-coordinator devices are not necessarily able to communicate with all other non-coordinator devices.

As shown in fig. 3, the network 300 includes a coordinator 310 and a plurality of devices 321 and 325. The coordinator 310 serves to control the operation of the network 300. As described above, the system of the coordinator 310 and the devices 321 and 325 may be referred to as a piconet, in which case the coordinator 310 may be referred to as a piconet coordinator (PNC). Each non-coordinator device 321-325 must be connected to the coordinator 310 by a primary wireless link 330 and may also be connected to one or more other non-coordinator devices 321-325 by a secondary wireless link 340, also referred to as a peer-to-peer link.

Additionally, although fig. 3 shows a bi-directional link between devices, it may also be unidirectional. In this case, each bidirectional link 330, 340 may be shown as two unidirectional links, a first lane in one direction and a second lane in the opposite direction.

In some embodiments, the coordinator 310 may be the same kind of device as any non-coordinator device 321-325, except for additional functions for coordinating the system and requiring communication with each device 321-325 in the network 300. In other embodiments, the coordinator 310 may be a separately designated control unit that serves as one of the devices 321 and 325.

During the following description, the coordinator 310 will be considered to be the same device as the non-coordinator device 321 and 325. However, other embodiments may use a dedicated coordinator 310. Additionally, each of the non-coordinator devices 321-325 may include the functional elements of the coordinator 310, but do not use them as non-coordinator devices. It may be the case that any device is a potential coordinator 310, but only one device actually plays such a role in a given network.

Each device of network 300 may be a different wireless device, such as a digital camera, digital video camera, Personal Digital Assistant (PDA), digital music player, or other personal wireless device.

The various non-coordinator devices 321-325 are limited to one available physical area 350, which is set according to the extent to which the coordinator 310 can successfully communicate with each of the non-coordinator devices 321-325. Any non-coordinator device 321-325 capable of communicating with the coordinator 310 (and vice versa) is within the available area 350 of the network 300. However, as described above, it is not necessary that each non-coordinator device 321- "325 in the network 300 communicate with each other non-coordinator device 321-" 325.

FIG. 4 is a block diagram of the devices 310, 321 and 325 in the network 300 of FIG. 3. As shown in fig. 4, each device (i.e., each coordinator 310 or non-coordinator device 321-325) includes a Physical (PHY) layer 410, a Medium Access Control (MAC) layer 420, a set of upper layers 430, and a management entity 440.

The PHY layer 410 passes through the primary or secondary wireless links 330 or 340. Which generates and receives data in a transmittable data format and converts it into a format usable through the MAC layer 420. The MAC layer 420 serves as an interface between a data format required by the PHY layer 410 and a data format required by the upper layer 430. The upper layer 205 includes the functionality of the devices 310, 321, 325. These upper layers 430 may include TCP/IP, UDP, RTP, IP, LLC, and the like.

Generally, the coordinator 310 and non-coordinator devices 321 and 325 in a WPAN share the same bandwidth. Accordingly, the coordinator 310 coordinates the sharing of the bandwidth. Standards have been developed to establish protocols for sharing bandwidth in wireless personal network (WPAN) settings. For example, IEEE standard 802.15.3 provides a standard for PHY layer 410 and MAC layer 420 in which bandwidth is shared using Time Division Multiplexing (TDMA). Using this standard, the MAC layer 420 defines frames and superframes through which the bandwidth shared by the devices 310, 321 and 325 is managed by the coordinator 310 and/or non-coordinator devices 321 and 325.

Of particular interest is how the various devices 321-325 can join the existing network 300 and how they communicate with the coordinator 310 during operation of the network 300. This is preferable to avoid collisions between different devices, which may occur if two or more devices 321 and 325 attempt to communicate (with each other or with the coordinator 310) at the same time.

Preferred embodiments of the present invention will be described below. Although the embodiments described herein are in the context of a WPAN (or a piconet), it will be appreciated that the invention may also be applied to other arrangements in which bandwidth is shared between several users, such as a Wireless Local Area Network (WLAN) or any other suitable wireless network.

Disclosure of Invention

Consistent with the headings in this section, only some of the features of the present invention will now be described briefly. A more complete description of the invention is the subject of this document.

It is an object of the present invention to provide an apparatus and method for joining an existing wireless network without collision with other devices.

It is another object of the present invention to provide a method of adapting communication between a device and a coordinator to avoid collisions.

Another feature of the present invention is to address the above and other deficiencies of conventional communication systems and methods.

Some such objects are achieved by a method for a remote device to monitor and communicate with a wireless network, the method comprising: receiving a beacon at the remote device, the beacon including beacon information defining a superframe; determining from the beacon information whether the received beacon and associated superframe are allocated to a network device; repeating the receiving and determining steps until the remote device receives M allocated beacons or an unallocated superframe; performing an association request if the remote device receives an unallocated superframe; performing a network saturation function if the remote device receives M allocated superframes, where M is an integer greater than 1, wherein the beacon information includes superframe allocation information indicating whether a superframe is allocated, wherein the superframe allocation information includes device identification information.

The superframe allocation information may include a single bit indicating whether a superframe is allocated. The device identification information is a device identification of the associated network device if the superframe is allocated and a given unallocated value not corresponding to any network device but representing an unallocated superframe if the superframe is not allocated.

The network saturation function includes sending error messages to higher layers.

There is also provided a method for a remote device to monitor and communicate with a wireless network, comprising: receiving a beacon at the remote device, the beacon including beacon information defining a superframe; determining from the beacon information whether the received beacon and superframe are fully allocated to the N network devices; repeating the steps of receiving and determining until the remote device receives M fully allocated superframes or one unallocated superframe; performing an association request if the remote device receives an unallocated superframe; the network saturation function is performed if the remote device receives M fully allocated superframes, where M is an integer greater than 1 and N is an integer greater than 1. The value of N may be constant for each superframe or may vary.

The beacon information includes superframe allocation information indicating whether the superframe is fully allocated or unallocated.

The superframe allocation information includes first to nth device identification information. Each of the first through nth device identification information is preferably a device identification of an associated network device or a given unallocated value that does not correspond to any network device but represents an unallocated superframe. The superframe is considered to be fully allocated if all of the first to nth device information is the device identification, and is considered to be unallocated if any of the first to nth device information is the given unallocated value.

The network saturation function includes sending error messages to higher layers.

In addition, there is provided a method for a coordinator to transmit information in a wireless network employing a superframe structure, including: generating M beacons, each beacon including beacon information defining one of M superframes; and sequentially transmitting M beacons during M superframes, wherein the beacon information includes data indicating whether the beacon and associated superframes are allocated to devices in the network, wherein M is an integer greater than 1.

The steps of generating M beacons and sequentially transmitting the M beacons are continuously repeated throughout operation of the network.

M may be equal to the maximum number of devices allowed in the network, or M may be equal to the number of devices allocated in the network plus a given value. The given value may be 1.

Another method for a coordinator to transmit information in a wireless network employing a superframe structure is provided, which includes: generating M beacons, each beacon including beacon information defining one of M respective superframes; and sequentially transmitting M beacons during M respective superframes, wherein the beacon information includes data indicating whether the beacon and associated superframe are allocated to N devices in the network, and wherein M is an integer greater than 1, and wherein N is an integer greater than 1.

The steps of generating M beacons and sequentially transmitting M beacons are repeated continuously throughout operation of the network.

The (M × N) value may be equal to the maximum number of devices allowed in the network.

Drawings

A more complete appreciation of the invention and additional advantages thereof will be readily obtained and understood by reference to the following detailed description when considered in connection with the accompanying drawings. In the drawings, the same reference numerals designate the same or corresponding parts.

FIG. 1 is a block diagram of the OSI standard for a computer communications framework;

FIG. 2 is a block diagram of the IEEE802 standard for a computer communications architecture;

FIG. 3 is a block diagram of a wireless network;

fig. 4 is a block diagram of a device or coordinator in the wireless network of fig. 3;

fig. 5 is a block diagram of a superframe according to a preferred embodiment of the present invention;

FIG. 6 is a block diagram of a frame in accordance with a preferred embodiment of the present invention;

fig. 7A and 7B are block diagrams illustrating the MAC header of fig. 6 according to a preferred embodiment of the present invention;

FIGS. 8A through 8H are block diagrams illustrating the schematic payload from FIG. 6 in accordance with a first preferred embodiment of the present invention;

fig. 9 is a block diagram illustrating an arrangement of elements in one superframe according to a first preferred embodiment of the present invention;

fig. 10 is a block diagram illustrating an arrangement of elements in one superframe according to a second preferred embodiment of the present invention;

fig. 11 is a block diagram showing a copy of a superframe in a cyclic beacon superframe structure;

FIGS. 12A-12D are block diagrams illustrating the structure of the superframe of FIG. 11;

FIG. 13 is a flowchart of a startup process for identifying the presence of an existing network in accordance with a preferred embodiment of the present invention;

FIG. 14 is a flow chart of an association process in accordance with a preferred embodiment of the present invention;

fig. 15 is a sequence diagram of SDL messages for initiating a new device of a network in accordance with a preferred embodiment of the present invention; and

fig. 16 is a sequence diagram of SDL messages illustrating an initiation and association process according to a preferred embodiment of the present invention.

Detailed Description

The present invention provides a method of coordinating devices 310, 321 and 325 operating in the network 300 or attempting to join the network 300 by using a cyclic beacon within a superframe that defines a data path over the network 300.

Device ID and MAC address

An important aspect of coordinating the devices 310, 321 and 325 in the network 300 is to uniquely identify each device 310, 321 and 325. There are several ways in which this can be achieved.

Independent of any network in which it is located, each device 310, 321, 325 has a unique MAC address that can be used to identify the device. The MAC address is typically assigned by the manufacturer such that no two devices 310, 321, 325 have the same MAC address. One set of standards for managing MAC addresses in a preferred embodiment of the present invention may be found in IEEE standard 802-: overview and framework ".

For ease of operation, the network 300 may also assign a device ID to each device 310, 321 and 325 in the network 300 for use in conjunction with its unique MAC address. In a preferred embodiment, the MAC 420 uses a special device ID to identify the device 310, 321 and 325. These device IDs may be used, for example, in the MAC header. The device ID is typically much smaller than the MAC address for each device 310, 321 and 325. In the preferred embodiment, the device ID is 4 bits and the MAC address is 48 bits.

Each device 310, 321, 325 should maintain a mapping table that maps the correspondence between device IDs and MAC addresses. The table is populated based on the device ID and MAC address information provided by the coordinator 310 to the devices 321 and 325. This allows each device 310, 321 to refer to themselves or other devices by device ID or MAC address.

The present invention may use the IEEE803.15.3 standard for high-speed WPAN, which is currently developed by IEEE802.15 WPAN task group 3(TG 3). Specific details of the current draft 802.15.3 standard, including the files of the 802.15.3 workgroup, may be found at the website: http:// www.ieee802.ora/15/pub/TG3. html. The disclosure herein is considered to be compatible with the draft 802.15.3 standard presented on the IEEE802 LAN/MAN standards committee web page.

Super frame

The available bandwidth in a given network 300 is separated in time by the coordinator 310 into a series of repeated superframes. These superframes define how the available transmission time is divided among the various tasks. The individual data frames are then transmitted within the superframes according to the timing given in the superframes.

Fig. 5 is a block diagram of a superframe according to a preferred embodiment of the present invention. As shown in fig. 5, each superframe 500 may include a beacon period 510, a Contention Access Period (CAP)520, and a Contention Free Period (CFP) 530.

The coordinator 310 is left with a beacon period 510 to send a beacon frame (see, e.g., fig. 6 and 8H) to the non-coordinator devices 321 and 325 in the network 300. Each device 321-325 knows how to identify the beacon 510 prior to joining the network 300 and uses the beacon 510 to identify the existing network 300 to coordinate communications within the network 300.

The CAP 520 is used to send commands or asynchronous data over the network. The CAP 520 may be eliminated in many embodiments and the system will then only transmit commands during the CFP 530.

The CFP 530 includes a plurality of time slots 540. These time slots 540 are allocated by the coordinator 310 to the paired devices 310,321 and 325 for communicating information therebetween (i.e., each time slot 540 is allocated to a particular transmitter-receiver pair).

The time slot 540 may be a Management Time Slot (MTS) or a Guaranteed Time Slot (GTS). An MTS is a time slot for transmitting management information between the coordinator 310 and one of the non-coordinator devices 321 and 325. Thus, the coordinator 310 must be made a member of the transmission pair. An MTS may be further defined as an uplink MTS (umts) if the coordinator 310 is the receiving device, or as a downlink MTS (dmts) if the coordinator 310 is the transmitting device.

A GTS is a time slot for transmitting non-management data between devices 310,321 and 325 in network 300. This may include data sent between the two non-coordinator devices 321 and 325 or non-management data sent between the coordinator 310 and the non-coordinator devices 321 and 325.

As used in this application, a data stream is a communication between a source device and one or more target devices. The source and target devices may be any devices 310, 321 and 325 in the network 300. For data flow to multiple destinations, the target device may be all or some of the devices 310, 321 and 325 in the network 300.

In some embodiments, the uplink MTS may be located at the front of the CFP 530 and the downlink MTS at the end of the CFP 530, so that the coordinator 310 has an opportunity to respond to the uplink MTS in the downlink MTS in the same superframe 500. However, this does not require the coordinator 310 to respond to a request in the same superframe 500. Instead, the coordinator 310 may respond to another downlink MTS allocated to the non-coordinator device 321 in the later superframe 500 and 325.

The superframe 500 is a fixed time structure that repeats in time. The particular duration of the superframe 500 is described in the beacon 510. In practice, the beacon 510 generally includes information regarding the frequency with which the beacon 510 repeats, which effectively corresponds to the duration of the superframe 500. The beacon 510 also includes information about the network 300, such as the identity of the transmitter and receiver for each time slot 540, and the identity of the coordinator 310.

The system clock for the network 300 is preferably synchronized through the generation and reception of the beacons 510. Each non-coordinator device 321-325 will store the synchronization point time after successful reception of the valid beacon 510 and then use that synchronization point time to adjust its own timing.

Although not shown in fig. 5, there is preferably a guard time distributed among the time slots 540 in the CFP 530. Guard times are used in TDMA systems to prevent time overlap of two transmissions due to inevitable errors in clock accuracy and propagation time differences based on spatial location.

In a WPAN, the propagation time is generally unimportant compared to the clock accuracy. Thus, the amount of guard time required is preferably based primarily on clock accuracy and duration due to previous synchronization events. Such a synchronization event typically occurs when the device 321 receives a beacon frame successfully from the coordinator 310.

For simplicity, a single guard time value may be used for the entire superframe. The guard time is preferably placed at the end of each beacon frame, GTS and MTS.

Frame

Within each superframe 500, information is transmitted between the devices 310, 321-325 via frames, which define how the signals are sent. In particular, a frame defines how the bits making up the signal are organized so that they are transmitted in a recognizable format.

Fig. 6 is a block diagram of a frame according to a preferred embodiment of the present invention. As shown in fig. 6, the frame 600 may include a preamble 610, a header 620, a Header Check Sequence (HCS)630, a payload 640, a Frame Check Sequence (FCS)450, and a post-amble 660. The header 620 is preferably divided into a physical header 622 and a MAC header 624. These elements will be discussed in detail below.

Preamble

The preamble 610 is a given bit pattern that is used to synchronize the timing of transmissions between the two communicating devices 310, 321 and 325. It ensures that the receiver translates correctly when initiating data transmission by giving it a uniform, known starting point. In addition, the preamble 610 may include a start frame Separator (SFD) that is used to synchronize clocks among the various devices 310, 321 and 325.

Header

As described above, the header 620 is divided into a physical header 622 and a MAC header 624. The physical header 622 provides information about the physical signals transmitted between the devices 310, 321-325 and preferably includes at least the length of the current payload 640. It may also include information related to the data rate at which payload 640 is transmitted or other information.

The MAC header 624 preferably includes data related to the transmission of frames between the devices 310, 321 and 325. Fig. 7A and 7B are block diagrams illustrating the MAC header of fig. 6 according to a preferred embodiment of the present invention. Fig. 7A is a block diagram showing a MAC header according to the first preferred embodiment, and fig. 7B is a block diagram showing a MAC header according to the second embodiment.

As shown in fig. 7A, MAC header 624 includes version identifier 705, ACK policy indicator 710, sequence number 715, frame type 720, target device ID 725, and source device ID 730.

The version identifier 705 includes the version of the header 620 used. In the preferred embodiment, the version identifier 705 is a single digit. In another embodiment, it may be larger.

The ACK policy indicator 710 is used to set when an Acknowledgement (ACK) is needed after the current frame 600 is transmitted. In the preferred embodiment, ACK policy indicator 710 is a single bit that is set to a "true" value (e.g., "1") when an ACK is needed and to a "false" value (e.g., "0") when an ACK is not needed. In broadcast and multicast frames, a "false" value should be set so that the receiver will not generate an ACK frame. Additionally, acknowledgement frames will have the ACK policy indicator 710 set to a "false" value because they are not acknowledged.

Sequence number 715 is used to track the transmission of data frames and is responsible for duplicating frames. The sequence number 715 cycles through an F value, which is assigned to consecutively transmitted data frames. If the receiver receives two consecutive frames with the same sequence number 715, it knows that one repeat frame was received due to retransmission. The repeated frame should be acknowledged but discarded. In this preferred embodiment (F ═ 3). The sequence number remains zero for all other frames 600.

The frame type 720 indicates what type of frame 600 is transmitted. In the preferred embodiment, the frame type 720 is 4 bits. The frame type 720 includes: beacon, status request, association reply, disassociation indication, ACK, data, stream allocation request, stream allocation reply, stream deallocation, stream reallocation.

One beacon frame type indicates that the frame is a beacon 510, which is generated by the coordinator 310 at the beginning of each superframe 500. A status request frame is transmitted by the coordinator 310 in the MTS to check the status of the target device. An association request frame is sent by a new device requesting the coordinator 310 to have it join the coordinator 310. In response to the association request frame, an association request frame is sent by the coordinator 310 to the new device. A detach indication frame is sent by the current device 321 and 325 to the coordinator 310 to indicate detachment from the network 300. An ACK frame represents an immediate Acknowledgement (ACK) of a previous frame. One data frame is sent between any two devices to transmit synchronization data along one data stream. A stream allocation request frame is sent by the current device 321 and 325 to the coordinator 310 to request that it be allocated a data stream. A stream allocation reply frame is sent from the coordinator 310 to a current device 321 in response to a stream request frame 325. A stream de-allocation frame is sent from the current device 321 + 325 to the coordinator 310 to indicate that the current device 321 + 325 no longer requires a data stream. A stream re-allocation frame is sent from a device 321 and 325 to the coordinator 310 to request a change to the already allocated data stream.

The target device ID 725 is the device ID of the device 310,321 and 325 receiving the frame 600.

The source device ID730 is the device ID of the device 310,321 and 325 that sent the frame 600.

Fig. 7B illustrates a MAC header 624 according to a second embodiment of the present invention. This embodiment conforms to the header format of the ieee802.15.3 standard. As shown in fig. 7B, the MAC header 624 includes a frame control 755, a network ID 760, a target device ID 725, a source device ID730, a fragmentation control 765, and a flow control 770.

Frame control 755 provides information about the version, frame type, acknowledgement policy, retry policy, and the like. In the preferred embodiment, the frame control 755 is 16 bits and is divided into a number of fields: a protocol version field indicating a version of a header format; a frame type field indicating a type of a frame to be transmitted; an SEC field indicating whether a security protocol is to be used; an ACK policy field indicating an acknowledgement policy to be used for the frame; a delayed ACK request field indicating whether delayed acknowledgement should be made to the current frame; a retry field indicating whether the frame is a retransmission of a previous frame; and indicating whether the transmitting device has more data to transmit after the current frame in the same GTS.

Network ID 760 represents an identification number for network 300. Preferably, the number remains constant for the duration of the network 300 and also remains fixed for any network 300 created by a given coordinator 310.

The target device ID 725 is the device ID of the device 310,321 and 325 receiving the frame 600.

The source device ID730 is the device ID of the device 310,321 and 325 that sent the frame 600.

Fragmentation control 765 is used to facilitate fragmentation and reassembly of Service Data Units (SDUs) in network 300. Which preferably includes information relating to the current service data unit, the current fragment number and the previous fragment number.

The flow control 770 represents a unique flow identifier for the data flow used by the current frame 600.

In the first preferred embodiment, the header 620 is 32 bits. Unused bits may be reserved if fewer bits are needed for a given portion of header 620. In other words, they may account for the header length and transmit with each header, but are not used by the receiving device. As a result, the actual number of bits used is not important.

For example, in the first preferred embodiment (see fig. 6 and 7A), the following values are selected. Both physical header 622 and MAC header 624 are 16 bits. Within the physical header 622, the frame is 15 bits long and 1 bit is reserved. Within the MAC header 624, the version identifier 705 is 1 bit, the ACK policy indicator 710 is 1 bit, the sequence number 715 is 2 bits, the frame type 720 is 4 bits, the destination address 725 is 4 bits, and the source address 730 is 4 bits.

Header Check Sequence (HCS)

The HCS 630 is a circuit containing a Cyclic Redundancy Check (CRC) code for the acknowledgement header 620. In a first preferred embodiment, the HCS is 16 bits and it is preferably calculated using a 16-degree standard generator polynomial called CRC-CCITT as follows:

G(x)＝x¹⁶+x¹²+x⁵+1 (1)

the HCS 630 is the complement of 1 (modulo 2) of the sum of the numbers: (1) x is the number of^k×(x¹²+x¹¹+x¹⁰+x⁸+x³+x²+x¹+1) divided by g (x) (modulo 2), where k is the digit in the calculation field; and (2) multiplying the content in the calculation field (as a polynomial) by x³²Then divided by the remainder after g (x).

The HCS 630 is preferably transmitted starting with the coefficients of the highest order terms.

In the preferred embodiment, the initial remainder of the division is preset to 1 at the transmitter and then modified by the generator polynomial g (x) by calculating the division of the field. The complement (complement) of 1 of the remainder is then transmitted, with the upper order bits being transmitted first, as in HCS 630.

At the receiver, the initial remainder is then preset to all 1's, and the series of input bits of the calculation field when divided by g (x) and HCS 630 result in a single non-zero remainder value in the absence of transmission errors. The single remainder value is a polynomial:

x¹²+x¹¹+x¹⁰+x⁸+x³+x²+x+1 (2)

or 0x1D0F

In the first preferred embodiment, the CRC in the HCS 630 is 16 bits. In other embodiments, the number of bits may be increased or decreased.

Payload

Payload 640 contains the data needed by current frame 600 (if needed). Fig. 8A to 8H are block diagrams illustrating an exemplary payload 640 from fig. 6 according to a first preferred embodiment of the present invention. In particular, FIG. 8A is an association request payload; FIG. 8B is an association reply payload; FIG. 8C is a flow request payload; FIG. 8D is a flow reply payload; FIG. 8E is a no flow payload; FIG. 8F is a flow redistribution payload; FIG. 8G is a data payload; and figure 8H is a beacon payload.

Fig. 8A is a block diagram illustrating an association request payload according to the first preferred embodiment. This MAC 420 in the new device becomes a part of the network 300 to be used. As shown in fig. 8A, association request payload 810 includes the MAC address of requester 812.

Fig. 8B is a block diagram of an association reply payload according to the first preferred embodiment. This is used when the coordinator 310 responds to the association request frame 820. As shown in fig. 8B, the association request frame 820 includes a MAC address 822, a padding block 824, and a device ID 826.

The MAC address 822 is the address of the requestor and may be any unicast address.

Pad 824 is a set of bits that are unused but allocated to reply payload 820. This is because the frame is preferably aligned to octets and padding block 824 is needed to provide the correct alignment. In another embodiment, padding blocks may be eliminated in the event that octet alignment is not used or padding is not required to maintain octet alignment. Preferably, the values stored in the pad 824 are zero, i.e., a string of 0 s.

Device ID 826 is an address assigned to the requesting device by coordinator 310. In the preferred embodiment of fig. 7A, there is one 4-bit device ID. If the coordinator 310 rejects association, the device ID 826 is returned with a value designated as unassigned.

Fig. 8C is a block diagram of a streaming request payload according to the first preferred embodiment. This is used when device 321 requests a data stream to communicate with another device 325. As shown in fig. 8C, the stream request payload 830 includes a destination address 832, GTS lower value 834, GTS upper value 836, and reserved block 838.

Destination address 832 is the MAC address of the receiver of the packet in the current data stream. The destination address 832 may be any unicast address or broadcast address. It may not be a multicast address.

GTS lower value 834 is the minimum acceptable amount of GTS that can be allocated to data to be transmitted. The GTS upper value 836 is the GTS that is requested the most for data transmission. In this embodiment, the GTS lower value 834 and GTS upper value 836 should be between 1 and 64, including 1 and 64. Additionally, the GTS lower value 834 should be less than or equal to the GTS upper value 836.

The hold block 838 represents a bit in the payload 640 that is not used in this embodiment. In another embodiment, other parameters may be altered to reduce or eliminate the retention block 838.

Fig. 8D is a block diagram of streaming back a payload according to the first embodiment. This is used when the coordinator 310 responds to the stream request payload 830 from the devices 321 and 325. As shown in fig. 8D, the stream reply payload 840 includes a stream ID842, a target ID 844, a GTS slot value 846, and a reserved block 848.

Stream ID842 is a unique identifier given to devices 321 and 325 assigned to the requesting device. If the allocation fails, the value is set to a specified attrition loss value. (e.g., encoded as 0xF in the first embodiment).

The target ID 844 is a device ID of the specified receiver device. If no receiver is found, the value is returned as unassigned.

After successful allocation, the GTS slot value 846 indicates the number of allocated slots. After an allocation failure, the GTS slot value 846 contains the amount of slots available for allocation.

The retention block 838 represents bits in the payload 640 that are not used in this embodiment. In other embodiments, other parameters may be changed to reduce or eliminate the retention block 838.

Fig. 8E is a block diagram of a streamless payload according to the first preferred embodiment. This is used by device 321 along with 325 to inform the coordinator 310 that it no longer needs to use the data stream and can reuse the corresponding GTS. As shown in fig. 8E, the streamless payload 850 includes a padding block 852, a stream ID 854, and a reserved block 856.

The pad 852 is a set of bits that are unused but allocated to the streamless payload 850. This is because the frame is preferably aligned to octets and padding 852 is needed to provide the correct alignment. In other embodiments, the padding block may be eliminated without using octet alignment or padding to maintain octet alignment. Preferably, the values stored in the pad 852 are zero, i.e., it is a string of 0's.

The stream ID 854 is the same stream ID842 as the stream ID returned in an associated stream reply payload 840. Which provides a unique identifier for the assigned stream.

The reserved block 856 represents bits in the payload 640 that are not used in this embodiment. In other embodiments, other parameters may be altered to reduce or cancel reservation block 856.

Fig. 8F is a block diagram of a stream reallocation payload according to the first preferred embodiment. This is used by a device to increase or decrease the amount of GTS for a flow request. In other embodiments, this may also be used to request changes to other parameters. As shown in fig. 8F, the stream reallocation payload 860 includes a padding block 862, a stream ID 864, and a GTS requested value 866.

The pad 862 is a set of bits that are unused but allocated to the stream reallocation payload 860. This is because the frame is preferably aligned into octets and padding block 862 is needed to provide the correct alignment. In other embodiments, the padding block may be eliminated without using octet alignment, or without padding to maintain octet alignment. Preferably, the value stored in pad 862 is 0, i.e., it is a string of 0 s.

The stream ID 864 is the same stream ID842 returned in the associated stream reply payload 840. It provides a unique identifier for the assigned stream.

The GTS requested value 866 is the new amount of GTS required by the requester. Coordinator 310 may deny the request and leave the GTS allocation unchanged, or it may allow the request and increase or decrease the GTS allocation accordingly, or it may partially allow the request, allocating the increase or decrease to less than the requested amount.

Fig. 8G is a block diagram of a data payload according to the first preferred embodiment. Which is used when data must be sent between the two devices 310,321 and 325. As shown in fig. 8G, the data payload 870 includes a data block 872. The data block 872 is simply a string of data bits of a certain length given in the physical header 622.

Fig. 8H is a block diagram of a beacon payload according to the first preferred embodiment. This is used for the beacon frames 520 sent at the beginning of each superframe 500. As shown in fig. 8H, the beacon payload 880 includes an MTS count 881, an MTS flag 882, a stall value 884, an associated address 887, and an RxTx table. In the preferred embodiment, there is also a reserved portion 885 between the stall value 884 and the associated address 887.

The MTS count 881 shows the number of current beacons in the beacon period. This is also used to identify the device, if any, that is currently assigned to the superframe 500, i.e., that has used the MTS in the superframe 500.

MTS flag 882 indicates whether the current beacon 510 is assigned to a device. This will be described in more detail below. In the first preferred embodiment, the MTS flag 882 is a single digit.

The shutdown value 884 is a value indicating whether the network 300 is ready to shutdown. This is preferably set to a "false" value during normal operation, and to a "true" value for a given number of superframes 500 before the network 300 is shut down. In the preferred embodiment, see fig. 7A, the stall value is a single digit (e.g., "0") that is set to a "false" value for normal operation, but is set to a "true" value for three superframes before the network 300 is shut down. During the time period that the coordinator initiates the network shutdown process, no further requests will be allowed.

The association address 887 is an IEEE802 MAC address of the device, which is assigned to the current beacon, if any.

The RxTx table 888 provides an indication of how to allocate GTS in the current superframe 500. In the embodiment represented in fig. 7A. Each superframe includes 4 GTSs (see fig. 9). The RxTx table 888, referred to as Channel Time Allocation (CTA) in other embodiments, stores the device ID assigned to the transmitter-receiver pair of each GTS. Therefore, it stores 128 pieces of 4 as device IDs: 64 sender device IDs and 64 associated receiver device IDs. Other embodiments may use Channel Time Allocations (CTAs) that include information related to the number, duration, placement and allocation of time slots.

In addition, some frame types do not require payload 640. For example, an Acknowledgement (ACK) frame does not require payload 640. In such a frame 600, both the payload 640 and the FCS 650 may be cancelled.

Frame Check Sequence (FCS)

The FCS 650 contains a Cyclic Redundancy Check (CRC) code that is used to validate the payload 640. In a first preferred embodiment, the FCS field is a 32-bit field that includes a 32-bit CRC. More details on this can be found in the american national standards institute "advanced data communication processing (ADCCP)", ANSI X3.66, 1979.

The FCS is computed on the payload 640, and the HCS payload 640 is referred to herein as a computation field. The FCS is calculated using a standard generator polynomial of order 32 as follows;

G(x)＝x³²+x²⁶+x²³+x²²+x+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1 (3)

the HCS 630 is numbered as followsComplement to 1 of the sum (modulo 2): (1) x is the number of^k×(x³¹+x³⁰+x²⁹+...+x²+x¹+1) divided by g (x) (modulo 2), where k is the digit in the calculation field; and (2) multiplying the content in the calculation field (as a polynomial) by x³²Then divided by the remainder after g (x).

The FCS field 650 is preferably transmitted starting with the coefficients of the highest order term.

In a first preferred embodiment, the initial remainder of the division is preset to 1 at the transmitter and then modified by the generator polynomial g (x) by calculating the division of the field. The 1's complement (complement) of the remainder is then transmitted, with the upper order bits being transmitted first, as in the FCS field 650.

At the receiver, the initial remainder is then preset to all 1's, and the series of input bits of the calculation field when divided by g (x) and FCS result in a single non-zero remainder value in the absence of transmission errors. The single remainder value is a polynomial:

x³¹+x³⁰+x²⁶+x²⁵+x²⁴+x¹⁸+x¹⁵+x¹⁴+x¹²+x¹¹+x¹⁰+x⁸+x⁶+x⁵+x⁴+x³+x+1 (4)

post-amble code

The frame 600 may also include a post-synchronization code 660, which is a sequence of bits disposed at the end of each frame 600 to facilitate synchronization or to perform other management functions. A postamble 660 may be canceled in some embodiments. In fact, the preferred embodiment described below with reference to FIG. 7A does not use the postamble 660.

It should be appreciated that the above frames are described by way of example and are not limiting. Other frames having other frame formats may also be used. In particular, the present invention may be used for frame formats used in the ieee802.15.3 standard.

Superframe embodiments

The specific design of one superframe 500 may vary depending on the application. Fig. 9 and 10 show two preferred embodiments of a specific superframe design. Fig. 9 is a diagram showing an arrangement of elements in one superframe according to the first preferred embodiment. Fig. 10 is a view showing an arrangement of elements in one superframe according to a second preferred embodiment of the present invention.

First preferred embodiment

As shown in fig. 9, the transmission diagram 900 involves dividing the available transmission time into superframes 910. This embodiment uses the MAC header 622 disclosed in fig. 7A and the payload 640 disclosed in fig. 8A to 8H.

In this embodiment, each independent superframe 910 includes a beacon frame 920, an uplink MTS930, a plurality of GTSs 940, and a downlink MTS 950.

The beacon frame 920 is a frame 600 whose HCS payload 640 is a beacon payload 880, as shown in fig. 8H. It indicates the devices 321-325 allocated to the current superframe 910 by association IDs (referred to as device IDs in the ieee802.15.3 draft standard). It also represents the transmitter/receiver pairs assigned to the various GTS 940 via an RxTx table 888.

In other embodiments, a stream index may be added to allow multiple streams at the same source-destination pair. This is shown, for example, in the standard for draft 802.15.3, which allows such multiple flows.

The uplink MTS930 is reserved for the devices 321 and 325 allocated to the current superframe 910 to upload signals to the coordinator 310. During this time slot all other devices 321-325 remain silent on the current channel, and all other stations on this channel must remain silent during the uplink MTS930, although they may still be transmitting on other channels.

A plurality of GTSs 940 (64 in the first preferred embodiment) are time slots reserved for each device 310, 321 and 325 to communicate with each other. They are also implemented according to the information given in the RxTx table 888 in the beacon frame 920. Each GTS 940 is preferably large enough to transmit one or more data frames. When a device pair is assigned multiple GTSs 940, they are preferably contiguous.

The downlink MTS 950 is reserved for the coordinator 310 to download signals to the devices 321 and 325 allocated to the current superframe 910. All other devices 321-325 may ignore all transmissions during the time slot.

The length of the downlink MTS 950 is fixed and is preferably selected to have a duration between 10 and 30ms to minimize data buffering requirements.

The length of the uplink MTS930 and 950 must be selected to handle the largest possible management frame, immediate acknowledgement frame, and receiver-transmitter turnaround time. For GTS 940, its length and number must be selected to accommodate the particular requirements of frame 600 to be transmitted, e.g., short MPEG frames, large frames of maximum allowable length, and streaming and immediate acknowledgment operations.

The length of any given payload 640 is limited by the length field in the physical header 622 and the FCS 650. In the first preferred embodiment, the length field in the physical header 622 is 15 bits and the FCS 650 is 4 bytes. Thus, payload 640 cannot be greater than 2¹⁵32766 bytes.

Although the first preferred embodiment uses 64 GTSs, one UMTS before the GTS and one DMTS after the GTS, in other embodiments the number, allocation and distribution of GTSs, UMTS and DMTS may vary according to the requirements of different applications.

Second preferred embodiment

As shown in fig. 10, the transmission diagram 1000 involves dividing the available transmission time into a plurality of superframes 1010. This embodiment uses the MAC header 624 disclosed in fig. 7B. The payload 640 preferably used is the IEEE802.15.3 standard.

In this embodiment, the data transmission diagram 1000 includes transmitting a temporally contiguous superframe 1010 over the network 300. Each superframe 1010 includes a beacon 1020, a Contention Access Period (CAP)1030, and a Contention Free Period (CFP) 1040. The contention-free period 1040 may include one or more Management Time Slots (MTS)1050 and one or more Guaranteed Time Slots (GTS) 1060.

The management time slot 1050 may be a Downlink Management Time Slot (DMTS) in which information is transmitted from the coordinator 310 to the non-coordinator device 321 + 325 or an Uplink Management Time Slot (UMTS) in which information is transmitted from the non-coordinator device 321 + 325 to the coordinator 310.

In the preferred embodiment, two management time slots 1050 are used per superframe 1010, one uplink and one downlink, although other embodiments may select a different number of management time slots 1050 and a mix of uplink and downlink. The MTS is also shared among multiple devices 321-325. In this case, a conventional solution, such as a slotted Aloha group broadcast system (slotted Aloha), must be used. In addition, if one CAP 1030 is used to communicate management information, the use of the MTS 1050 must be reduced or eliminated.

In the second preferred embodiment, there are as many guaranteed time slots 1060 as there are in the active primary and secondary wireless links 330 and 340. However, this may vary in other embodiments. There may be more or fewer guaranteed time slots 1060 in any given superframe 500 than there are active primary and secondary wireless links 330 and 340. In this case, the coordinator 310 specifies how the devices 310, 321, 325 should use the available guaranteed time slots 1060.

The size of GTS1060 in this embodiment is preferably dynamic. Each transmitter-receiver pair assigned one GTS1060 is also informed of the GTS1060 duration for assigning the device to the beacon. These durations may have different sizes for different GTSs in a single superframe 1010. Additionally, the length and location of a given GTS1060 may change over different superframes 1010, limited only by the ability of the coordinator 310 to successfully notify non-coordinator devices 321-325 of the change. The start time and duration of the guaranteed time slot 1060 are determined by the coordinator 310 and sent to the device 321-325 during the contention access period 1030 or a management time slot 1050 depending on the application.

In the second preferred embodiment, the coordinator 310 uses the beacon 1020 (whatever format it is) and the MTS to coordinate the scheduling of the various devices 310, 321 and 325 into their respective guaranteed time slots 1060. All devices 310, 321-325 listen to the coordinator 310 during the beacon period 1020. Each device 321- "325 will receive zero or more time slots 1050, 1060 that are notified of each start time and duration from the coordinator 310 during the beacon period 1020. The coordinator 310 automatically allocates the management time slots 1050 to each of the devices 321 and 325. However, the management slots 1050 are only allocated when required by the devices 321-325.

The Channel Time Allocation (CTA) field in beacon 1020 includes a start time, packet duration, source device ID, destination device ID, and stream index. The beacon information uses a format commonly referred to as TLV, which represents type, length, and value. As a result, each device knows when to transmit and when to receive. At all other times, the devices 310, 321, 325 may stop listening and enter a power saving mode. Thus, the beacon period 1020 is used to coordinate the transmission and reception of the devices 310, 321 and 325.

At the beginning of each superframe 1010, the coordinator 310 sends a beacon 1020 to all non-coordinator devices 321 and 325. The beacon 1020 informs 325 each non-coordinator device 321 of the duration of the superframe 1010 and other information about its MAC address. Each beacon 1020 also includes information that is not exactly one CTA. One piece of information will define the beacon period 1020 and describe the start time and duration of the beacon period 1020. The other will define the contention access period 1030 (if present) and describe the start time and duration of the contention access period 1030. Each beacon may also have multiple CTAs. Here, there is one CTA (MTS or GTS) for each time slot 1050, 1060. With dynamic slots, the slot allocation can change CTA every superframe.

During transmission, each device 321-325 must listen to the beacon 1020 so that they will know which time slots 1050, 1060 have been allocated to them as transmitters or receivers. If the device misses the beacon 1020, it must listen to the entire superframe 1010 in case it is receiving data. Additionally, in some applications, transmission may not be allowed for the duration of the superframe 1010 because it does not know when transmission is allowed. This is detrimental to the system as it may lead to an interruption of the data transmission.

The network may communicate control and management information between the coordinator 310 and the various devices 321 and 325 through an optional contention access period 1030, a management slot 1050, or both. This may involve, for example, information about a new device to join the network 300. The particular application will decide what special options to use: it may include a contention access period 1030, one or more management slots 1050, or some combination thereof.

The devices 310,321, 325 transmit frames during the contention-free period 1040 according to the schedule given at the beacon 1020. The device pairs 310, 321-325 assigned to a given guaranteed time slot 1060 use their assigned GTS1060 to transmit frames 1070 between them. This may be data from the designated sender to the designated receiver or an Acknowledgement (ACK) frame from the designated receiver to the designated sender.

As described above, a guard time 1080 is preferably provided between frames to account for differences in clock accuracy and propagation delay based on the spatial location of the devices 310, 321 and 325.

In superframes without the CAP 1030 or MTS 1050, it may be desirable to set a delay between the beacon 1020 and the first GTS1060 to give the respective device 321 time to process the beacon 1020. Otherwise the device 321-325 assigned to the first GTS1060 may not enter the transmit/listen mode in time to use the assigned time slot 1060.

Cyclic beacon

One problem in an ad hoc network 300 is coordinating the entry and exit of devices into the network 300 and the transmission of management frames between the coordinator 310 and the devices 321 and 325. The present invention solves this problem by using a cyclic beacon to monitor the network 300 and the devices 321 and 325 therein.

Each network preferably has a given number N of devices 310, 321 and 325. In the preferred embodiment, N is a power of 2, such as 4 or 8 (i.e., coordinator 310 and three non-coordinator devices 321 + 325 or coordinator 310 and 7 non-coordinator devices 321 + 325), although the exact number of devices allowed N may vary. However, the N maximum value for the network may be achieved by extending the available transmission time and allowing each device to communicate sufficiently often and sufficiently to maintain the desired level of operation. Powers of 2 are preferred, but not required.

The superframes 500 are grouped together in batches of N superframes 500. Within the group, a superframe 500 is allocated to each device 310, 321 and 325 currently in the network 300. Preferably, a specific superframe (e.g., a first superframe) is always allocated to the coordinator 310.

Each non-coordinator device 321-325 may then use the superframe 500 assigned to it to send and receive management commands (e.g., in management slots) from the coordinator 310. The superframe 500 assigned to the coordinator 310 may be used to allow devices outside the network 300 to communicate with the coordinator, such as to request entry into the network 300. They are also used for the coordinator to send information to all non-coordinator devices 321 and 325. Additionally, in some embodiments, the unallocated superframe 500 may also be used for communication with the coordinator 310 at devices outside of the network.

The coordinator 310 will indicate at the beacon 510 which device 310,321 and 325 is allocated to a given superframe 500. Thus, the allocation of the superframe 500 to a given device 310, 321- "325 is sometimes referred to as the allocation of the beacon 510 to one device 310, 321-" 325.

In other embodiments, the coordinator 310 may allocate multiple devices to a single superframe. For example, each superframe may include management slots for two devices. As a result, two devices are associated with the superframe before becoming "allocated".

Fig. 11 and 12A-12D are block diagrams illustrating a structure of a cyclic beacon superframe according to a preferred embodiment of the present invention. Fig. 11 is a diagram showing repeated copies of superframes in a one-cycle beacon superframe structure. Fig. 12A to 12D are block diagrams illustrating the structure of the superframe of fig. 11.

In the embodiment disclosed in fig. 11 and 12A-12D, four devices 310,321 and 325 are allowed to enter the network 300. This means that the network 300 will allow at most one coordinator 310 and three non-coordinator devices 321 and 325. Other embodiments may vary this number. For example, other embodiments may have 8 or 16 devices.

Superframe structure

As shown in fig. 11, each device 310, 321, 325 is assigned a superframe. The coordinator is assigned a coordinator superframe 1101; the first device is assigned a first non-coordinator device superframe 1102; the second non-coordinator device is assigned a third device superframe 1104; and a third non-coordinator device is assigned a third device superframe 1104. These superframes 1101, 1102, 1103, and 1104 are repeated sequentially as long as the network 300 is operational.

Even though there are four devices 310,321 and 325 in the network 300. For example, if there are only two devices in the network 300 (i.e., the coordinator 310 and one non-coordinator device 321- "325), the delivery time is still divided into four superframes 1101, 1102, 1103 and 1104, with each device 310, 321-" 325 being assigned to a single superframe.

However, in other embodiments, the coordinator 310 may select a cycle such that there is only a specified number of unallocated superframes (e.g., one) to the maximum number of licensed superframes in an unsaturated network 300. For example, in the above environment, there are a maximum of four devices, but only two devices are present, the coordinator 310 may cycle through three superframes 1101, 1102, and 1103, with two allocated and one unallocated.

As shown in fig. 12A, the coordinator superframe 1101 includes one coordinator beacon 1211 and a contention-free period 1231. The contention-free period 1231 includes a coordinator uplink mts (umts)1251, coordinator downlink mts (dmts)1261, and GTS 1271.

The coordinator beacon 1211 includes information indicating that it is allocated to the coordinator 310 (there will be only one coordinator 310 in any network). The coordinator UMTS 1251 is used for coordinator broadcast to the entire network, or for association requests from devices attempting to join the network; the coordinator DMTS 1261 is used for coordinator broadcasting to the entire network; and GTS1271 is used to transmit frames of information between devices 310,321 and 325.

As shown in fig. 12B, the first device superframe 1102 includes a first device beacon 1212 and a contention-free period 1232. The contention-free period 1232 includes a first device uplink mts (umts)1252, a first device downlink mts (dmts)1262, and a plurality of GTS 1272.

The first device beacon 1212 includes information indicating whether the first device superframe 1102 is allocated to the devices 310, 321 and 325, and if so, which of the devices 310, 321 and 325 is allocated. The first device UMTS 1252 is used to send a management request from the first device (if 1 is allocated) to the coordinator 310; the first device DMTS 1262 is used to send management instructions from the coordinator 310 to the first device (if 1 is assigned); and GTS1272 is used to transmit frames of information between devices 310,321 and 325.

As shown in fig. 12C, the second device superframe 1103 includes a second device beacon 1213 and a second device idle period 1233. The second device idle period 1233 includes a second device uplink mts (umts)1253, a second device downlink mts (dmts)1263, and a plurality of GTS 1273.

The second device beacon 1213 includes information indicating whether the second device superframe 1103 is allocated to the device 310,321- "325, and if so, which of the devices 310,321-" 325. The second device UMTS 1253 is used to send a management request from the second device (if 1 is allocated) to the coordinator 310; the second device DMTS 1263 is used to send management instructions from the coordinator 310 to the second device (if 1 is assigned); and GTS 1273 is used to transmit frames of information between devices 310,321 and 325.

As shown in fig. 12D, the third device superframe 1104 includes a third device beacon 1214 and a third device idle period 1234. The contention-free period 1234 includes a third device uplink mts (umts)1254, a third device downlink mts (dmts)1263, and a plurality of GTS 1274.

The third device beacon 1214 includes information indicating whether the third device superframe 1104 was allocated to the device 310,321- "325 and, if so, which of the devices 310,321-" 325. The third device UMTS 1254 is used to send a management request from the third device (if 1 is allocated) to the coordinator 310; the third device DMTS 1264 is used to send management instructions from the coordinator 310 to the third device (if 1 is assigned); and GTS 1274 is used to transmit frames of information between devices 310,321 and 325.

This embodiment is shown without the CAP 520 to illustrate that in some designs, the CAP 520 may be eliminated. In this embodiment, management between the coordinator 310 and the non-coordinator devices 321 and 325 is achieved solely through the use of the MTSs 1251, 1261, 1252, 1262, 1253, 1263, 1254, and 1264. However, other embodiments may include a CAP 520 in each superframe 1101, 1102, 1103, and 1104.

In addition, the embodiment is shown with two MTSs, UMTS 1251, 1252, 1253, 1254 and DMTS 1261, 1262, 1263, 1264. As described above, the number, allocation, and distribution of the MTSs may be altered in other embodiments.

Beacon information

As described above, each beacon includes two important information blocks regarding its allocation status: (1) whether it is assigned to the device 310, 321- "325, and (2) to which of the devices 310, 321-" 325 if it is assigned. The two information blocks can be disclosed in a number of different ways.

For example, in the first preferred embodiment, the beacon frame includes a bit (MTS flag 882) indicating when a superframe is allocated and when it is idle, and a counter indicating the device ID (MTS count 881) of the device 310, 321- "325 (if any) that is allocated to the superframe associated with the beacon.

A device listening to a given superframe can tell whether it is assigned by checking the MTS flag 882. And if the MTS flag 882 indicates that the superframe is assigned, the device checks the MTS count 881 to see which device is assigned to it. A device in the network 300 may use this information to find the superframe assigned to it. A device external to the network 300 may use this information to find a desired empty superframe or a coordinator superframe that communicates other management information to the coordinator 310.

In other embodiments, the beacon frame may simply include holding an identifier (device ID, MAC address, etc.) associated with the device assigned to the given superframe. And if no device is assigned to the superframe, the register may be filled with a virtual address that does not correspond to the licensed device, but represents an unallocated superframe.

A device listening to a given superframe can tell whether it is assigned by checking the identifier register. If the register has a valid identifier (e.g., a valid device ID), the device will know that the superframe is assigned. In particular, if the register has an identifier assigned to the coordinator, the device will know that a specific superframe is assigned to the coordinator. And if the identifier register has the virtual address, the device knows that the superframe is unassigned and can perform operations accordingly.

As described above, a device in the network 300 may use this information to find the superframe to which it is assigned. A device outside the network may use this information to look for a required empty superframe, or coordinator superframe, to communicate other management information to the coordinator 310. It may also use this information to look up the MAC address for the device assigned to the particular beacon.

During the superframe 1102, 1103, 1104 assigned thereto, a non-coordinator device 321-325 may transmit management frames to and from the coordinator 310 using UMTS and DMTS. During the course of a superframe that is not assigned to it, a given device will remain silent during the MTS of that superframe. However, GTS allocated to it during the superframe can be freely used.

When a new device wishes to enter a network, it begins listening for a beacon. Once it finds the beacon, it waits until it listens for an unallocated superframe. If it finds an unallocated superframe, it sends a join request during the uplink MTS of the superframe.

However, if it passes through the entire batch of N superframes without detecting an unallocated superframe, it knows that the network is saturated and can take appropriate steps, such as sending an error message to its user or higher layers, retrying after a given period of time, changing channels, and so forth.

As described above, other embodiments may allocate multiple devices to a single superframe and manage time slots accordingly. In this case, the superframe will remain unallocated until it is allocated to its maximum number of devices. The new device checking the allocation status of the superframe has to check whether there is any free space in the superframe. As described above, this may be accomplished with a flag or a series of device IDs that represents the devices assigned to the superframe.

Joining or initiating a network

Fig. 13-16 illustrate how a device determines whether a network exists and attempts to join the network or create a network if a network does not exist. Fig. 13 is a startup procedure for identifying whether there is an existing network according to a preferred embodiment of the present invention. Fig. 14 is a flow chart of an association process according to a preferred embodiment of the present invention. Fig. 15 is a sequence diagram of SDL messages for a new device initiating a network in accordance with a preferred embodiment of the present invention. Fig. 16 is a sequence diagram of SDL messages illustrating an initiation and association process according to a preferred embodiment of the present invention.

As shown in fig. 13, a new device initiates a process 1300 to determine if a network exists as follows. In the start-up procedure 1300, the new device first waits for a given beacon interval to check whether it listens for beacons 510 from the existing network (step 1305). The beacon interval should be at least the duration of the superframe 500, as the beacon 510 is typically repeated only once in each superframe 500.

If no signal is received at the end of the beacon interval (step 1310), the device preferably listens for the beacon at an additional random interval (step 1315). The random interval is preferably shorter than the beacon interval, but longer than a beacon transmission duration.

If no signal is received at the end of the random interval (step 1320), the device will assume that there is no network 300 and will initiate a new network 300 with itself as the coordinator 310 (step 1325). The device (now the coordinator 310) will then issue a new beacon 510 (step 1330) and will operate normally as coordinator 310.

However, if the device receives a signal after the beacon interval (step 1310) and the random interval (step 1320), the device will determine whether the signal is a beacon 510 (step 1335).

If the received signal is a beacon 510, the device will determine that an existing network 300 exists therein and will perform an association procedure with the coordinator 310 of the network, requesting to join (step 1340).

However, if the received signal is not a beacon 510, the device will enter an error state because the required bandwidth is blocked by other signals (step 1345). In this case, the device will switch channels depending on the particular application, then try again, give up and send an error message to its user or higher layers, etc.

This random spacing is not required, but is included in the preferred embodiment to facilitate operation. This is because there are situations that may cause multiple devices to enter the boot process 1300 simultaneously. For example, if a network 300 is disbanded, multiple devices will begin the boot process 1300 immediately after the network 300 is disbanded. By including a random interval (step 1315), the process reduces the likelihood that multiple devices will attempt to transmit a new beacon at the same time (step 1330), thus reducing the likelihood that beacon collisions will occur.

As shown in fig. 14, each device performs an association process 1400 when deciding to enter an existing network 300. The association process 1400 begins when the device receives a beacon 510 (step 1405).

As described with reference to fig. 11, the superframe 500 in the network 300 is divided into N superframes 1101, 1102, 1103, 1104 (one superframe for each potential device in the network 300), which are cyclically repeated during network operation. These superframes 1101, 1102, 1103, 1104 are assigned to each device location, and each superframe represents its status in the association beacon 510.

After receiving a beacon 510 in step 1405, the device determines that the beacon 510 indicates that the current superframe 1101, 1102, 1103, 1104 is allocated (sometimes referred to as allocating the beacon 510) (step 1410).

If the received beacon 510 indicates that the current superframe 1101, 1102, 1103, 1104 is unallocated, the device transmits an association request frame to the coordinator 310 at the next appropriate time, for example, in the course of UMTS, which does not allocate a superframe (step 1415). If two devices collide (i.e., they try and transmit to the coordinator 310 at the same time), they use a contention resolution algorithm, such as slotted Aloha.

If the received beacon 510 indicates that it was allocated at step 1410, the device determines if it has cycled through all possible beacons (step 1420). In other words, it determines whether it has checked N consecutive beacons, where N is the total number of available devices 310, 321 and 325 in the network 300.

If the device has not cycled through all possible beacons, it waits for the next beacon (step 1425) and then processes the beacon as it did on the previous beacon (step 1410 and subsequent steps). H

Once it finishes processing all beacons and determines that they are all allocated, the device determines that the network is saturated and performs any required "saturated network" processing (step 1430). This may include notifying the operator of the device or higher layers of the device that the network is saturated, switching channels, or waiting until attempted again at a later time.

Fig. 15 is an exemplary SDL message sequence diagram 1500 for a new device performing startup processing. As shown in fig. 15, a new device 1505 proceeds along a new device timeline 1510 that performs the startup process.

First, the new device 1505 sets a beacon timer 1515 for the random interval and waits the time period for incoming beacons. (step 1305 in fig. 13 is performed).

At the end of the beacon interval, the new device 1505 has not received an incoming beacon yet, so it sets a random timer 1520 for a random interval and waits the time period to look up the incoming beacon again (taking the "no" branch of step 1310 and performing step 1315 of fig. 13).

At the end of the random interval, the new device 1505 has not received an incoming beacon, so it enters the coordinator state 1525, starts a new network 300 with itself as a coordinator 310 (taking the "no" branch of fig. 1320 and performing step 1325 of fig. 13).

Once in the coordinator state 1525, the new device 1505 starts sending beacons 1530 and continues to operate as a coordinator 310 for the new network 300 (step 1330 of fig. 13 is performed).

Fig. 16 is a sequence diagram of SDL messages illustrating the initiation and association process. In this process, the allowable network size is four devices.

As shown in FIG. 16, a new device 1605 progresses along a new device timeline 1610 in beginning the startup process 1500 and continuing the association process. First, the new device 1505 sets a beacon timer 1515 for the beacon interval and waits the time period for an incoming beacon (step 1305 of fig. 13 is performed).

In this case, the new device 1505 receives the beacon 1635 sent by the coordinator 1640 along the coordinator timeline 1645 before the end of the beacon interval. (the "YES" branch of step 1310 of FIG. 13 is taken). This interrupts the beacon interval timer 1515 and the new device 1505 begins processing the incoming beacon. In this case, the new device 1505 determines that the incoming signal is a beacon and begins the association process (step 1335 of fig. 13 is performed and the yes branch is taken).

The new device 1505 the first input beacon 1635 is an assigned beacon. This is simply the first beacon it receives, so it continues to wait for the next beacon. (the yes branch of step 1410 is taken in fig. 14, the no branch of step 1420 is taken and step 1425 is performed).

The new device 1505 then receives the next beacon 1650 and determines that the beacon is also assigned. It checks how many beacons (two) it has passed so far and determines that it has not yet cycled through all the admitted beacons. Therefore, it waits for the next beacon (in fig. 14, go to step 1405, take the yes branch of step 1410, take the no branch of step 1420, and go to step 1425).

The new device 1505 then receives the next beacon 1655 and determines that the beacon is unassigned. It then waits until the next appropriate time, the coordinator will listen for an association request 1660 and send it to the coordinator 1640 (step 1405 is performed in fig. 14, taking the "no" branch of step 1410).

After receiving the association request 1660 from the new device 1505, the coordinator 1640 sends an Acknowledgement (ACK)1670 and an association response 1675 to the new device 1505. In this case, the coordinator 1640 sends an unspecified beacon and its associated superframe to the new device 1505. The new device 1505 sends an ACK 1680 to the coordinator 1640 and performs normal operations in the network 300.

Obviously, many modifications and variations of the present invention are possible in light of the above teachings. For example, although described in the context of a wireless network, the disclosed methods may be used to apply to a wired network. It is, therefore, to be understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described herein.

Claims (18)

1. A method for a remote device to monitor and communicate with a wireless network, comprising:

receiving a beacon at the remote device, the beacon including beacon information defining a superframe;

determining from the beacon information whether the received beacon and associated superframe are allocated to a network device;

repeating the receiving and determining steps until the remote device receives M allocated beacons and associated superframes or one unallocated beacon and associated superframe;

performing an association request if the remote device receives an unassigned beacon and associated superframe;

if the remote device receives M allocated beacons and associated superframes, a network saturation function is performed,

wherein M is an integer greater than 1,

wherein the beacon information includes superframe allocation information indicating whether a superframe is allocated,

wherein the superframe allocation information includes device identification information.

2. A method for a remote device to monitor and communicate with a wireless network as recited in claim 1, wherein the superframe assignment information includes a single bit indicating whether a superframe is assigned.

3. The method for a remote device to monitor and communicate with a wireless network of claim 1,

wherein the device identification information is a device identification of the associated network device if the superframe is allocated, an

Wherein if a superframe is not allocated, the device identification is a given unallocated value that does not correspond to any network device but represents an unallocated superframe.

4. A method for a remote device to monitor and communicate with a wireless network as recited in claim 1, wherein the network saturation function includes sending an error message to higher layers.

5. A method for a remote device to monitor and communicate with a wireless network, comprising:

receiving a beacon at the remote device, the beacon including beacon information defining a superframe;

determining from the beacon information whether the received beacon and superframe are fully allocated to the N network devices;

repeating the steps of receiving and determining until the remote device receives M fully allocated beacons and superframes or one unallocated beacon and superframe;

performing an association request if the remote device receives an unassigned beacon and superframe;

if the remote device receives M fully allocated beacons and superframes, a network saturation function is performed,

wherein M is an integer greater than 1 and N is an integer greater than 1.

6. A method for a remote device to monitor and communicate with a wireless network as recited in claim 5, wherein the value of N may vary for each superframe.

7. A method for a remote device to monitor and communicate with a wireless network as recited in claim 5, wherein the beacon information includes superframe allocation information indicating whether the superframe is fully allocated or unallocated.

8. A method for a remote device to monitor and communicate with a wireless network as recited in claim 7, wherein the superframe assignment information includes first through nth device identification information.

9. The method for a remote device to monitor and communicate with a wireless network of claim 8,

wherein each of the first to nth device identification information is one of a device identification of an associated network device and a given unallocated value that does not correspond to any network device but represents an unallocated superframe, and

wherein if all of the first to nth device information are device identifications, the superframe is considered to be fully allocated, and if any of the first to nth device information is the given unallocated value, the superframe is considered to be unallocated.

10. A method for a remote device to monitor and communicate with a wireless network as recited in claim 5, wherein the network saturation function includes sending an error message to higher layers.

11. A method for a coordinator to transmit information in a wireless network employing a superframe structure, comprising:

generating M beacons, each beacon including beacon information defining one of M superframes; and

the M beacons are sequentially transmitted during the course of M respective superframes,

wherein the beacon information includes data indicating whether the beacon and associated superframe are allocated to devices in the network, wherein M is an integer greater than 1.

12. A method for a coordinator to communicate information in a wireless network employing a superframe structure, as recited in claim 11, wherein the steps of generating M beacons and sequentially transmitting the M beacons are continuously repeated throughout operation of the network.

13. A method for a coordinator to communicate information in a wireless network that employs a superframe structure, as recited in claim 11, wherein M is equal to the maximum number of devices allowed in the network.

14. A method for a coordinator to communicate information in a wireless network that employs a superframe structure, as recited in claim 11, wherein M is equal to the number of devices allocated in the network plus a given value.

15. A method for a coordinator to communicate information in a wireless network employing a superframe structure, as recited in claim 14, wherein the given value is 1.

16. A method for a coordinator to communicate information in a wireless network employing a superframe structure, comprising:

generating M beacons, each beacon including beacon information defining one of M respective superframes; and

the M beacons are sequentially transmitted during the course of M respective superframes,

wherein the beacon information includes data indicating whether the beacon and associated superframe are allocated to N devices in the network, an

Wherein M is an integer greater than 1, and wherein N is an integer greater than 1.

17. A method for a coordinator to communicate information in a wireless network that employs a superframe structure, as recited in claim 16, wherein the steps of generating M beacons and sequentially transmitting the M beacons are continuously repeated throughout operation of the network.

18. A method for a coordinator to communicate information in a wireless network that employs a superframe structure, as recited in claim 16, wherein (mxn) is equal to the maximum number of devices allowed in the network.