Broadcast method in a WPAN network

<u>CROSS-REFERENCE TO RELATED APPLICATIONS</u>

0001This application claims the priority of Korean Patent Application No. <patcit id="pcit0001" dnum="KR200484309"><text>2004-84309 filed on October 21, 2004</text></patcit> in the Korean Intellectual Property Office and <patcit id="pcit0002" dnum="US54422604P" dnum-type="L"><text>U.S. Provisional Patent Application No. 60/544,226 filed on February 13, 2004</text></patcit> in the United States Patent and Trademark Office.

<u>BACKGROUND OF THE INVENTION</u>

Field of the Invention

0002The present invention generally relates to a broadcast method in a wireless network and a communication apparatus using the broadcast method. More particularly, the present invention relates to a broadcast method in a wireless network and a communication apparatus using the broadcast method, which are capable of efficiently broadcasting data by a link-based broadcast in a ZigBee network compliant to the IEEE 802.15.4 standard.

Description of The Related Art

0003In contrast to a Local Area Network (LAN) or a Wide Area Network (WAN), a Personal Area Network (PAN) is a network owned by an individual. Devices owned by the individual are interconnected to construct a network in order to provide convenience for the owner. The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 802.15 Working Group developed the WPAN for short distance wireless networks to standardize and implement the PAN. The IEEE 802.15 standard has four Task Groups. More particularly, IEEE 802.15.1 standardizes the well-known Bluetooth technology, whereas IEEE 802.15.3 and IEEE 802.15.3a standardizes the high rate WPAN. Additionally, IEEE 802.15.4, alias ZigBee, standardizes low rate WPAN which corresponds to data rates less than 250 kbps.

0004One of the goals of ZigBee is to standardize the protocol stacks above a media access control (MAC) layer for wireless sensor networks. To this end, the current ZigBee specification supports reliable data broadcast at a network layer. A broadcast method specified in the ZigBee specification consists of three major parts, which include a network-wide broadcast, a local broadcast repair, and a limited radius broadcast.

0005<figref idref="f0001 f0002">FIGS. 1 through 4</figref> illustrate conventional broadcast methods according to the ZigBee specification. Referring now to <figref idref="f0001 f0002">FIGS. 1 through 4</figref>, the conventional broadcast methods of the ZigBee specification and drawbacks associated with the conventional broadcast methods are described below.

0006<figref idref="f0001">FIG. 1</figref> illustrates the network-wide broadcast mechanism in the ZigBee network which is specified in the ZigBee specification. According to the ZigBee specification, the network-wide broadcast mechanism is a tree-based broadcast in which broadcast packets are only forwarded via a tree structure.

0007For example, if the source of a broadcast packet is a node A in a network as shown in <figref idref="f0001">FIG. 1</figref>, the broadcast packet must be transmitted through its parent node in order to reach neighbor nodes because the broadcast packet is delivered only following the tree structure. Thus, transmission of the broadcast packet from node A to node B or node C, as shown in <figref idref="f0001">FIG. 1</figref>, requires six transmissions and relays following the tree structure. However, by utilizing physical links instead of the tree structure, the broadcast packet can be delivered to node B or node C (of <figref idref="f0001">FIG. 1</figref>) via three or four nodes along links indicated as dotted lines in <figref idref="f0001">FIG. 1</figref>. Therefore, the transmission of the broadcast packets following the tree structure according to the ZigBee specification delays the delivery of the broadcast packets unnecessarily.

0008<figref idref="f0001">FIG. 2</figref> illustrates the local broadcast repair mechanism in the ZigBee network. As explained above, the broadcast method of the ZigBee specification utilizes a parent and child relationship based on the tree structure. If a node loses contact with its parent node, a broadcast packet is not delivered farther. The local broadcast repair mechanism is used to repair the lost link in such a situation.

0009The ZigBee specification specifies that a child node, which loses contact with its parent node, performs a local broadcast repair using a 'Lost Parent' bit in a packet control field included in a packet header. However, there is no solution with respect to delivery of a broadcast packet from a parent node when the parent node loses contact with the child node. For example, if a link between node C and node B is broken, as shown in <figref idref="f0001">FIG. 2</figref>, node F can receive a packet from a node, such as node G, via another branch of node C. However, since the packet received from node G is not delivered from its parent or child node, the packet is discarded. As a result, the sub-tree under node B is not covered.

0010<figref idref="f0002">FIG. 3</figref> illustrates the limited radius broadcast mechanism used in a ZigBee network. According to the limited radius broadcast mechanism, a range to which a broadcast packet reaches can be set using a radius counter (RC) value. Referring to <figref idref="f0002">FIG. 3</figref>, a node 0 performs the limited radius broadcast with RC=2. The RC value decreases by 1 every time the broadcast packet is retransmitted from each node. The broadcast packet is not retransmitted farther when the RC value becomes zero.

0011The limited radius broadcast, which allows the tree structure, may present undesired results. For example, as shown in <figref idref="f0002">FIG. 4</figref>, if nodes F and G are one-hop neighbor nodes and node F attempts to perform the limited radius broadcast with RC=3, the broadcast packet will not be delivered to the node G. In order to reach node G, the limited radius broadcast has to be performed with RC=4. That is, the RC value needs to be unnecessarily large to cover neighbor nodes, and therefore, unnecessary traffic increases.

0012<nplcit id="ncit0001" npl-type="s"><text>TSENG Y-C ET AL: "Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network" IEEE TRANSACTIONS ON COMPUTERS; IEEE SERVICE CENTER; LOS ALAMITOS; CA US; Vol. 52, no. 5, May 2003 (2003-05), pages 545-557, XP002349202 ISSN: 0018-9340</text></nplcit> discloses structures directed to a neighbor-coverage scheme. A corresponding broadcast packet is only further re-broadcast to a set of pending hosts in the neighborhood put of one host as long as the local set of neighbors is not empty. It is in particular said that a broadcast packet which is received for the first time is to be re-broadcast. It is also said that such a message will only be rebroadcast, at the most, once to prevent endless flooding of the packets. For this reason, the corresponding host can detect duplicate broadcast packets.

0013<patcit id="pcit0003" dnum="JP1107508A"><text>P-A-1 107 508 </text></patcit>(TELEFONAKTIEBOLAGET LM ERICSSON9 13 June 2001 (2001-06-13) discloses a method that concerns special networks, such as Bluetooth, and there is some kind of noted which receives a message. Such message is said to be a broadcast message. The corresponding broadcast message includes a unique identity and the broadcast message may be cancelled if it is again received with the same identity as one of the cached identities already received. In such a case, this message is discarded and will not be forwarded to other nodes.

0014<nplcit id="ncit0002" npl-type="s"><text>WILLIAMS B ET AL: "COMPARISON OF BROADCASTING TECHNIQUES FOR MOBILE AD HOC NETWORKS" MOBIHOC 2002. PROCEEDINGS OF THE 3RD. ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING: LAUSANNE; SWITZERLAND; JUNE ); ) June 2001 (2002-06-09), pages 194-205, XP001171559 ISBN: 1-58113-501-7</text></nplcit> discloses mobile ad-hoc networks, wherein a source node is used for broadcasting a packet to all neighbors. In particular, different methods of flooding are described as well as neighbour knowledge methods.

0015<nplcit id="ncit0003" npl-type="s"><text>NI S-Y ET AL. "THE BROADCAST STORM PROBLEM IN A MOBILE AD HOC NETWORK" MOBICOM '99. PROCEEDINGS OF THE 5TH ANNUAL ACM/IEEE INTERNATIONAL CONFERENCE ON MOBILE COMPUTING AND NETWORKING. SEATTLE, WA, AUG. 15-20, 1999, ANNUAL ACM/IEEE INTERNATIONAL CONFERENCE ON MOBILE COMPUTING AND NETWORKING; NEW YORK, NY: AMC, US, vol. CONF. 5, 15 August 1999 (1999-08-15), pages 151-162, XP000896082 ISBN: 1-58113-142-9</text></nplcit> describes a mobile ad-hoc network with flooding, wherein it is in particular said that redundancy, contention and collision of such a mechanism should be reduced such that some hosts are inhibited from rebroadcasting the corresponding message. Different schemes are then discussed.

0016<nplcit id="ncit0004" npl-type="s"><text>CHUNHUI ZHU ET AL: "A border-aware broadcast scheme for wireless ad hoc network" CONSUMER COMMUNICATIONS AND NETWORKING CONFERENCE; 2004. CCNC 2004. FIRST IEEE LAS VEGAS, NV, USA 5-8 JAN. 2004, PISCATAWAY, NJ, USA, IEEE, 5 January 2004 (2004-01-05), pages 134-139, XP010696813 ISBN: 0-7803-8145-9</text></nplcit> describes flooding with different approaches to avoid such flooding.

<u>SUMMARY OF THE INVENTION</u>

0017It is an object of the present invention to provide a link-based broadcast method in a wireless network and a corresponding communication apparatus which is more reliable.

0018This object is solved by the features of the independent claims.

0019Advantageous embodiments are disclosed by the subclaims.

0020The broadcast method way further comprises the step of destroying the broadcast packet when all of the neighbor nodes from which the broadcast packet is received are marked as 'relayed'.

0021A rebroadcast timer can count the predetermined time, thereby setting a rebroadcast time. The predetermined time may be set based on a link quality indicator (LQI) value of the received broadcast packet.

0022The rebroadcast step can be repeated a number of times corresponding to a predetermined value at intervals of the predetermined time until all of the neighbor nodes relay the broadcast packet. Thus, unrestricted rebroadcast is prevented.

0023The marking step can set a neighbor list corresponding to information relative to the neighbor nodes, and marks nodes listed in the neighbor list. The neighbor list is set using a bitmap based on an index of the listed neighbor nodes. The listed neighbor nodes are located within one hop from a broadcast source. The listed neighbor nodes are grouped based on a ZigBee address and the grouped neighbor nodes are checked to determine whether the grouped neighbor nodes are marked as 'relayed'.

0024The reliable broadcast method rebroadcasts the broadcast packet if the broadcast packet is first received, and rebroadcasts the broadcast packet after a predetermined time if there is a node, among the neighbor nodes, which does not relay the broadcast packet. If the packet is not first received, the reliable broadcast method destroys the broadcast packet. The unreliable broadcast method rebroadcasts the broadcast packet if the broadcast packet is first received, and destroys the broadcast packet if the broadcast packet is not first received.

0025The designated field is a 'Lost Parent' field in a packet control field included in the header of the broadcast packet.

0026Consistent with an aspect of the present invention, a communication apparatus using a broadcast method in a wireless network, comprises a means for receiving a broadcast packet, a means for determining whether the broadcast packet is first received, a means for storing and rebroadcasting the broadcast packet to neighbor nodes if the broadcast packet is first received, a means for cleaning the broadcast packet if the broadcast packet is not first received, a means for marking a node, among the neighbor nodes, from which the broadcast packet is received, as 'relayed', a means for checking whether all of the neighbor nodes are marked as 'relayed' after a predetermined time, and a means for rebroadcasting the broadcast packet if all of the neighbor nodes are not marked as 'relayed'. The communication apparatus further comprises a means for destroying the broadcast packet if all of the neighbor nodes are marked as 'relayed'.

<u>BRIEF DESCRIPTION OF THE FIGURES</u>

0027These and/or other aspects and advantages of the invention will become apparent and more readily appreciated from the following description of the exemplary embodiments, taken in conjunction with the accompanying drawing figures of which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001 f0002">FIGS. 1 through 4</figref> are diagrams of conventional broadcast methods according to a ZigBee specification;</li><li><figref idref="f0003">FIGS. 5A</figref> and <figref idref="f0004">5B</figref> are flowcharts of a broadcast method according to a first embodiment of the present invention;</li><li><figref idref="f0005">FIG. 6</figref> is a diagram of an exemplary embodiment of a neighbor list;</li><li><figref idref="f0006">FIG. 7</figref> is a diagram of an exemplary embodiment of a packet control field; and</li><li><figref idref="f0007">FIG. 8</figref> is a diagram illustrating that a neighbor list is built by grouping neighbor nodes.</li></ul>

<u>DETAILED DESCRIPTION OF THE EMBODIMENTS</u>

0028Reference will now be made in detail to the exemplary embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The exemplary embodiments are described below in order to explain the present invention by referring to the drawings.

0029A broadcast method in a wireless network according to exemplary embodiments of the present invention utilizes a link-based broadcast rather than a parent node and child node relationship which is based on a tree-based broadcast. Accordingly, the parent node and the child node relationship which is based on the tree structure are not the only nodes that can participate in the delivery of broadcast packets. In other words, all nodes can participate in the delivery of broadcast packets according to the broadcast method of the present invention. The broadcast method in the wireless network according to the present invention is primarily applied to a ZigBee network compliant to the IEEE 802.15.4 standard However, the broadcast method according the present invention is not limited to the ZigBee network. For instance, any network meeting the criteria corresponding to embodiments of the present invention may be employed.

0030<figref idref="f0003">FIGS. 5A</figref> and <figref idref="f0004">5B</figref> are flowcharts of the broadcast method in the wireless network according to a first embodiment of the present invention. Referring initially to <figref idref="f0003">FIG. 5A</figref>, a node linked to the wireless network receives a broadcast packet (S100), and the node determines whether the received packet is first received (S105). The first received packet denotes that the received packet is not the same as a previously received packet. A determination is made as to whether the packet is first received by checking the presence of packet information corresponding to the received packet in a broadcast transaction record (BTR) of a broadcast transaction table (BTT).

0031If the determination performed at step S105 reveals that the packet is first received, a BTR corresponding to the received packet is created and stored in the BTT (S110). The BTR created corresponding to the received packet contains a source address and a broadcast sequence number (BCSN) of the packet.

0032After creating the BTR, the received broadcast packet is stored in a buffer and a rebroadcast timer is set (S115). The rebroadcast timer is used to determine a rebroadcast time. Subsequently, the received packet is rebroadcast at step S 120.

0033In step S125, each of the neighbor nodes in the neighbor list from which the broadcast packet is received are checked and marked as 'relayed', as shown in <figref idref="f0005">FIG. 6</figref>.. According to the present invention, the neighbor list organizes information relating to neighbor nodes within one hop from a broadcast source. In order to mark a relayed field of the neighbor list a bitmap based on an index of each node is utilized. The length of the bitmap equals the number of neighbor nodes in the neighbor list.

0034If it is determined at step S105 that the packet has been received, each of the neighbor nodes in the neighbor list from which the broadcast packet is received are checked and marked as 'relayed' when the source address of the received packet corresponds to the neighbor nodes in the neighbor list (S130). After the neighbor nodes in the neighbor list are marked as 'relayed' in step S130, the received packet is destroyed in step S140. As a result, the received broadcast packet is processed.

0035Referring to <figref idref="f0004">FIG. 5B</figref>, when the set rebroadcast timer expires after a predetermined time (S150), a determination is made as to whether all of the neighbor nodes in the neighbor list are marked as 'relayed' (S155). If the determination reveals that each of the neighbor nodes are not marked as 'relayed', the received packet is rebroadcast in step S170 and the rebroadcast timer is re-set in step S175. A Maximum Retransmission Limit parameter to count the number of times rebroadcast has occurred is increased (S180). If the Maximum Retransmission Limit parameter is below a predetermined value (S195), steps S150 through S180 are repeated. Accordingly, the number of the times rebroadcast may occur is limited to the predetermined value. As a result, unrestricted rebroadcast is not allowed.

0036If all of the neighbor nodes in the neighbor list are marked as 'relayed' at step S155, the packet stored in the buffer is cleared (S160) and the BTR is cleared (S165). In other words, the packet is destroyed when all of the neighbor nodes from which the packet is received are marked as 'relayed'. As a result, it is guaranteed that all the neighbor nodes receive the broadcast packet according to the link-based broadcast.

0037A broadcast method according to a second embodiment of the present invention selectively utilizes a reliable broadcast method and an unreliable and best-effort broadcast. According to the second embodiment of the present invention, an 'Unreliable Broadcast' field is newly defined, and the broadcast method is selected depending on whether the 'Unreliable Broadcast' field is set. For example, if the 'Unreliable Broadcast' field is not set, the broadcast method using the neighbor list according to the first embodiment of the present invention is used. In other words, when the 'Unreliable Broadcast' field is not set, the reliable broadcast method rebroadcasts the broadcast packet if the broadcast packet is first received, and rebroadcasts the broadcast packet after a predetermined time if there is a node, among the neighbor nodes listed in the neighbor list, which does not relay the broadcast packet. If the packet is not first received, the reliable broadcast method destroys the broadcast packet On the contrary, if the 'Unreliable Broadcast' field is set, the broadcast packet is not forwarded according to the reliable method as in the first embodiment of the present invention. Instead, according to the unreliable broadcast method, the broadcast packet is forwarded if the packet is first received and the broadcast packet is destroyed if the broadcast packet is not first received. Additionally, when the 'Unreliable Broadcast' field is set, the creation of the BTR is maintained. However, marking of the corresponding neighbor node in the neighbor list as 'relayed' is not utilized.

0038Referring to <figref idref="f0006">FIG. 7</figref>, the 'Unreliable Broadcast' field can use a 'Lost Parent' field in a packet control field which is added into a header at a network layer. A 'Broadcast' bit, a 'Lost Parent' bit, and a 'Broadcast Radius Present' bit in the packet control field respectively relate to the network-wide broadcast, the local broadcast repair, and the limited radius broadcast of the ZigBee specification. As described above, broadcast method according to the exemplary embodiments of the present invention allows all nodes to participate in the forwarding of the broadcast packet. Thus, there is no need to utilize the local broadcast repair to find the link to the parent node. Accordingly, the 'Lost Parent' field can be used as the 'Unreliable Broadcast' field.

0039A broadcast method according to a third embodiment of the present invention selectively utilizes tree-based and link-based limited radius broadcasts. To this end, a 'Tree-based Broadcast' sub-field is added in the header of a packet control field. By default, the 'Tree-based Broadcast' sub-field is not set, and the link-based limited radius broadcast according to the first embodiment of the present invention is utilized. However, if the 'Tree-based Broadcast' sub-field is set, the tree-based limited radius broadcast is utilized according to the conventional broadcast methods of the ZigBee specification.

0040When building a neighbor list which includes information regarding the nodes within one hop from a broadcast source, it is possible to group the nodes based on the parent and child relationship by using a ZigBee address.

0041<figref idref="f0007">FIG. 8</figref> illustrates that a neighbor list is built by grouping neighbor nodes. Referring to <figref idref="f0007">FIG. 8</figref>, the first to third neighbor lists 210, 310 and 410 are built for the first to third areas 200, 300 and 400, respectively. Nodes 6 and 7 are in the parent and child relationship in the first and second neighbor lists 210 and 310. Nodes 8, 9, and 10 are in the parent and child relationship in the third neighbor list 410.

0042After grouping the neighbor nodes in the parent and child relationship, and once the broadcast packet is received from one of the nodes in a specific group, all nodes in the corresponding group are checked and marked as 'relayed' according to the normal reception of the broadcast packet in the neighbor list. Nodes in a group, which share a superframe, enable reliable transmission within the group. In addition, waiting time at a source node is reduced.

0043When determining a rebroadcast time, the received broadcast packet may be rebroadcast to nodes in an order corresponding to the distance away from the source node by setting a backoff value in proportion to a link quality indicator (LQI) value of the received broadcast packet. In this situation, if the rebroadcast packet generated at the node farthest from the source node is received, the nodes close to the source node receive the packet in the usual manner. Since the node farthest from the source node performs the rebroadcast, high-speed broadcast can be performed over the entire network. In light of the foregoing each of the nodes linked to a wireless network can participate in the forwarding of the broadcast packet according to the link-based broadcast. Since the broadcast packet is delivered along the links, the broadcast packet is performed faster than the tree-based broadcast. The tree structure is not utilized according to the embodiments of the present invention, and therefore, the local broadcast repair mechanism to repair the tree structure is not needed. Since the link-based limited radius broadcast is utilized, it is possible to efficiently set the transmission range of the broadcast packet, and the RC value represents the actual limited hop. If needed, it is possible to selectively utilize the reliable broadcast and the unreliable and best-effort broadcast. The rebroadcast time can be efficiently set by grouping the neighbor list by use of the ZibBee address, or according to the LQI value. While the exemplary embodiments of the present invention have been described, additional variations and modifications of the exemplary embodiments may occur to those skilled in the art once they learn of the basic inventive concepts. Therefore, it is intended that the appended claims shall be construed to include the aforementioned exemplary embodiments and all such variations and modifications that fall within the scope of the invention.