WO2007054872A1

WO2007054872A1 - A method to support a distributed error correction code

Info

Publication number: WO2007054872A1
Application number: PCT/IB2006/054108
Authority: WO
Inventors: Gustaf Sebastian Max; Guido Hiertz; Yunpeng Zang; Joerg Habetha
Original assignee: Koninklijke Philips Electronics NV; US Philips Corp
Current assignee: Koninklijke Philips NV; US Philips Corp
Priority date: 2005-11-10
Filing date: 2006-11-03
Publication date: 2007-05-18
Anticipated expiration: 2008-05-10

Abstract

Each node (42) or station in a wireless ad hoc multi hop network (40) uses an ECC generator polynomial that is probabilistically different from an ECC generator polynomial that is used in a neighboring node (72) when a frame (72 88) is being prepared for transmission. Further more, the data or cargo portion (76) of a data frame that is being prepared for transmission may be shifted by a determined amount prior to an ECC generator polynomial is used generate the ECC for the frame. A field in the data frame, either in the header or footer of the data frame, provides information to the receiving nod (48) about the ECC generator polynomial that was used in the transmitting nod and/or the amount of the data in the cargo portion of data frame is shifted. Although various embodiments of the method and apparatus of the present invention have been illustrated in the accompanying Drawings and described in the foregoing Detailed Description, it will be understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements, modifications and substitutions without departing from the scope of the invention as set forth herein.

Description

A METHOD TO SUPPORT A DISTRIBUTED ERROR CORRECTION CODE

The present invention relates generally to communication networks, and more specifically to methods and systems that improve error correction of data packets in multi- hop wireless networks.

Today, many people carry numerous portable devices, such as laptops, mobile phones, PDAs, and MP3 players, for use in their professional and private lives. For the most part, these devices are used separately. That is, their individual applications do not interact. Imagine, however, if they could interact directly. Imagine that participants at a meeting could share documents or presentations; that business cards would automatically find their way into address registers on a laptop and into the number register on a mobile phone; that as commuters exit a train, their laptops could remain online; likewise, incoming e-mail could now be diverted to their PDAs; and that as they enter their office, all communication could automatically be routed through the wireless corporate campus network.

These are examples of spontaneous; ad hoc wireless communication between devices that may be loosely defined or referred to as ad hoc networking. Ad hoc networking allows devices to establish communication, any time and anywhere without the aid of a central infrastructure or backbone. In the past, the notion of ad hoc networks was often associated with communication on combat fields and at the site of a disaster area. Now with the advancement of telecommunication and novel technologies, such as Bluetooth, the scenario of ad hoc networking is likely to change.

Wireless ad hoc networks are autonomous networks operating either in isolation or as "sub-networks" connected to a fixed infrastructure. Such networks have the potential to provide wireless and mobile computing capability in situations where efficient, economical and rapid deployment of communication is required, and where the use of wired or an infrastructure-based wireless network is either too expensive or impractical.

Perhaps the most widespread notion of a mobile ad hoc network is a network formed without any central administration that comprises mobile nodes that use a wireless interface to send packet data. Since each of the nodes in a network of this kind can serve as a router and a host, they can forward packets on behalf of other nodes and run user applications.

To put ad hoc networking in another perspective, one may only have to observe present day wireless communication and cellular systems. Such present day systems rely heavily on infrastructure: coverage is provided by statically located base stations, radio resources are managed from a central location, and services are integrated into the system. This leads to the good and predictable service of present day cellular systems. As communication moves away from central management, the communication industry finds itself moving in the direction of pure ad hoc operation, which can also be classified in terms of single or multiple hop systems.

Error detection and correction becomes an important aspect of ad hoc networks. Current wireless technology method of error correction is based primarily on and uses cyclic redundancy checks (CRC) in their operation. All the stations or nodes of a network share and use the same CRC generator polynomial. Packet errors in received data are detected by calculating the CRC locally at the receiving node or station. The calculated result is compared against the CRC received from the sending node or station. Error correction codes (ECC) are also used to help recover erroneous frames received by a node or station. If the ECC at the receiving node fails to be able to recover an erroneous frame, the packet must be resent by the sending node. However, for this type of failure-recovery process the same ECC operation is performed each time the packet is re-received at the receiving node. No extra information is gained at the receiving node except that the ECC calculation may continue to be unable to recover the packet. It is noted that all transmission trails have the same error probability when one assumes that both nodes are stationary. For mobile ad hoc networks, the issue of routing the packets between any pair of nodes or stations becomes a challenging task because the nodes or stations can move randomly within a network. The path that was considered optimal at a given point in time may not work at all or produce frame errors a few moments later. Moreover, the stochastic properties of wireless channels add to the uncertainty of path quality and error rate. The operating environment as such, might also cause problems for indoor scenarios. For example, the closing of a door might cause a path to be disrupted and additional or frame errors to result.

Figure 1 depicts a generic wireless or wired ad hoc multi-hop network 10. No wired backbone is available so all the information has to be transmitted using the wireless infrastructure.

To organize the highly dynamic, frequently changing topology of a wireless ad hoc multi-hop network, unicast and broadcast frames are used throughout the network. Especially broadcast frames are used by routing protocols to establish a neighborhood connectivity and to support route discovery procedures. Therefore, frames are repeatedly broadcast by several nodes or stations by providing the same information and by also using the same ECC. Looking at Figure 1, a generic ad hoc multi-hop network 10 is shown with several nodes 12-28. There is one node 12 that provides access to external networks 30. In Figure 2 the generic network 10 is shown in three frames. In the first frame, node 12 is broadcasting information (data or cargo) using a standard ECC. In the second frame, node 14 is broadcasting the same information, which node 12 broadcasted, using the same ECC. In frame three, node 16 is broadcasting the same information once again, using the same ECC. Node 18, even after the repetitive transmissions may still not have received the broadcasted information correctly without errors. That is, even though three neighboring nodes 14, 12 and 16 transmitted the information, node 18 still may not have received and been able to recover the data in the received frames using ECC. Node or station 18 receives the same frame three times, once or more from each of the nodes or stations 12, 14 and 16. No additional information is provided by nodes 12, 14 and 16 that might allow station or node 18 to combine the independently received frames into a usable frame that is without error(s) in its data. Thus, what is needed is a system or method to improve the error correction of data packets and/or frames in a multi-hop network.

In order to overcome the above-stated problems and/or other problems not specifically discussed, embodiments of the present invention provide a method for improving the error correction of data packets in an ad hoc network and/or a multi-hop ad hoc network. A method of an exemplary embodiment utilizes incremental redundancy. Each node in an exemplary multi-hop network uses its own or determines its own generator polynomial for its Error Correction Code (ECC). Each node in the network, when receiving a frame or other form of information from neighboring nodes also receives information about the transmitting node's ECC generator polynomial. As such, each node (i.e. station) can check received data frames from neighboring nodes for errors. An exemplary node, in accordance with an embodiment of the present invention, can also recombine subsequently received frames that have errors, which were transmitted by different neighboring nodes or by a single neighboring node that varies its ECC generator ploynomial. By being able to recombine frames that have errors, continued or additional retransmission of the same data can be avoided.

In one embodiment of the invention each node in the ad hoc network has its own ECC generator polynomial. Each node may exchange their ECC generation polynomials with a neighboring node prior to data transmission or each node may provide its ECC generation polynomial in, or encoded in, part of the data packet or frame itself. Furthermore, the data in the cargo portion of the data frame can be shifted in order to create a differing ECC. Embodiments of the invention are not necessarily restricted to wireless or wired technology. Embodiments of the invention may be used in a variety of different types of communication networks to aid in error recovery. Such other networks also include, without limitation, Wireless LANs (WLANs) and Wireless PANs (WPANs).

Another embodiment of the present invention provides a node in an ad hoc network with a method of transmitting a data frame. The method includes using an ECC generation polynomial that is probabilistically different from another ECC generation polynomial that is being used by a neighboring node. The node uses the ECC generation polynomial to generate a first ECC for a data frame that is being transmitted. The exemplary node then, transmits the data frame to neighboring nodes. The transmitted data frame includes a field that contains information to identify the ECC generation polynomial that was used by the transmitting node to generate the first ECC.

In other embodiments of the invention, each node is assigned an ECC generation polynomial. In yet other embodiments of the invention, a node may select an ECC generation polynomial from a predetermined list of ECC generation polynomials. The selection from the list of ECC generation polynomials may be incremented or random. Still in other embodiments of the invention, the ECC generation polynomial may be randomly generated by the transmitting node.

Embodiments of the invention further allow a receiving node to receive the data frame and determine, using the provided ECC generation polynomial information found in the received data packet or frame, where the received data frame has an error in it. The receiving node may receive the same cargo data in a frame from another neighboring node that used a different ECC generation polynomial when generating its data frame. As such, a receiving node may be able to recombine the cargo data into error free data by using the data frames received from different neighboring nodes. In yet another embodiment of the present invention, a node in an ad hoc network that is transmitting a data frame, shifts the data in the cargo portion of the data frame by a determined amount prior to performing an ECC calculation. The determined amount of shift can always be the same for frames that are transmitted by a specific node, or can be incremented each time (or at predetermined times) a frame is to be prepared for transmission by the node. By shifting the data in the cargo field of the frame, the ECCs will most likely be different for the same data in frames sent by different nodes. The transmitting node provides the shift information in a shift field of the data frame so that the receiving node can perform the same ECC calculation as the transmitting node performed. Again, a receiving node will be able to recombine erred cargo data fields received from different nodes or the same node if the same cargo data field was transmitted using different ECC generator polynomials or had the ECCs calculated from differently shifted data.

The above summary of the invention is not intended to represent each embodiment or every aspect of the present invention.

A more complete understanding of the method and apparatus of the present invention may be obtained by reference to the following Detailed Description when taken in conjunction with the accompanying Drawings wherein:

FIGURE 1 is a block diagram of a generic ad hoc network; FIGURE 2 is a block diagram with time three frames of communication between stations or nodes in a generic ad hoc network;

FIGURE 3 is a block diagram of an ad hoc and/or multi hop network in accordance with embodiments of the present invention;

FIGURE 4 depicts a data or cargo field in a frame that is shifted according to an embodiment of the invention; and

FIGURE 5 depicts an identification mechanism of a plurality of ECC generator polynomials in accordance with an embodiment of the present invention.

Embodiments of the present invention provide a method and means for improving the error correction of data packets in a multi- hop network 10. Embodiments of the invention can be based on incremental redundancy that is supported by each node in the ad hoc network. Referring now to Figure 3, an exemplary wireless ad hoc multi- hop network 40 is depicted. In this network one node 42 is connected to external networks 60. Other nodes or stations can also be connected to external networks as well. The exemplary ad hoc multi- hop network incorporates various nodes or stations 42-58. Each node or station can be mobile or stationary and may wirelessly communicate with another node. A node or station may be substantially any type of wireless device including, without limitation, computers, microprocessor based devices, mobile phones, PDAs, notebook computers, automotive or transportation vehicles, printer equipment, fax machines, MP3 or other audio devices, video devices, machinery, tools and appliances, internet devices, grocery carts, communication equipment, and identification devices to name a few. Each node 42-58 in the exemplary wireless ad hoc network has its own ECC generator polynomial. That is, each node 42-58 performs an ECC function using a different generator polynomial than the other nodes. Each node when communicating with its neighboring nodes or stations receives the neighboring node's ECC generator polynomial. Each station can check frames from their neighboring sending nodes for errors using the same ECC generator polynomial that was used by the sending node when the frame was sent. Because each station (e.g. 42, 44, 46), sends data to a neighboring station (e.g. 48), using a different polynomial than the other sending stations for its ECC generator polynomial, then each receiving station (e.g. 48) can check the received frames for errors and subsequently combine the non-error portions of two or more frames received from the different stations (e.g. 42, 4, 46), into error-free usable frames. This will allow exemplary nodes in an exemplary ad hoc multi- hop network to avoid, in some cases, the requirement of additional retransmissions from transmitting stations because a receiving station can combine partially received frames from a plurality of transmitting nodes or stations. An exemplary embodiment and method may require that there be one ECC generator polynomial per station. The ECC generator polynomials may not all be unique, but there should be a plurality of different ECC generator polynomials that are used. Each transmitting station would exchange its ECC generator polynomial to a receiving station either just previous to the data transmission or as part of the header or footer portion of the data transmission or frame.

In a second embodiment of the present invention and method for improving the error correction of data packets in a multi-drop network, the bits in the data packet may be shifted. That is, each station when transmitting a frame will indicate, via a shift field in the header of each frame, how the data in part of the frame is shifted or was shifted before the ECC was calculated by the transmitting station. By shifting the data in part of the frame a different amount when data is transmitted at each station or node 42-58, no data frame will be transmitted on a channel from one node to another node having the same ECC redundancy information. Variations of embodiments of the present invention may set each station or node to have its own static shift value for shifting the data within a frame prior to performing an ECC calculation. In other embodiments, a randomly chosen shift value can be calculated in each node prior to performing the ECC calculation and transmitting the frame. Furthermore, the shift value can be incremented a predetermined amount, or random amount, so that the data part of the frame is shifted the same predetermined or a random amount before each ECC is calculated and the frame is transmitted from a node. Statistically speaking, it would be unlikely that a frame would then be transmitted on a channel to another node using the same ECC redundancy information multiple times. Hence, if nodes or stations 42, 44 and 46 each transmit the same frames to node or station 48, most likely, no data frame will have been transmitted on the channel using the same ECC redundancy information. Thus, the receiving station 48 would be enabled to combine faulty frames by recombining independently coded ECC information.

Figure 4 depicts original data 70 that has data bits from zero (0) to n. A frame 72 is also depicted wherein shift information is provided in the shift field 73 of the header of the frame. The shift field 73 indicates that the data or cargo portion 76 of the frame has been shifted at the k bit such that the k+1 through n bit precede the 0-k bits in the data or cargo portion 76 of the frame. Thus, the ECC is calculated based on a different data bit pattern thereby resulting in a different ECC value than the value of an unshifted data or cargo portion. The check sum CRC portion 74 is calculated after the data is shifted. By having each transmitting node (e.g. 42, 44, 46) calculate the ECC and/or CRC portion of the frame using shifted data and providing a different ECC value, the receiving node (e.g. 48) will be able to successfully recombine previous and current frame receptions that have errors into a useful frame. The receiving node or station (e.g. 48) reads the header of the frame including the shift field 73 to recalculate the ECC and/or CRC and compare the results with the provided CRC field 78 in the frame. If an error is found the ECC can be used, in conjunction with duplicate frames received from the same or other transmitting nodes that have the data field 76 shifted differently, to combine the other duplicated frames into error free data without requiring additional transmissions of the same data. In yet another embodiment of the present method to improve the error correction of data packets in a multi-hop network, each station or node may have a memory portion (not specifically shown) that stores all of the valid ECC generator polynomials in its network 40. When a station (e.g. 46) transmits a data frame, it may select and use one of the known ECC generator polynomials and provide an ECC ID number of the generator polynomial that was used in and ECC ID filed in the header of the data frame. In another embodiment, each station or node may randomly choose an ECC generator polynomial ID from a plurality of predetermined ECC generator polynomials stored in the node for each or a predetermined number of frames. In yet another embodiment, each station may choose an ECC generator polynomial ID via a round robin technique where it steps through all the ECC generator polynomials stored in the transmitting node and provide the ECC ID in a header field of the frame being transmitted.

Figure 5 depicts an exemplary embodiment wherein each station or node stores a number n of valid ECC generator polynomials 82. The code may be stored in a memory device 80 within each node. Each node stores the plurality of ECC generator polynomials 82 and labels each one of them with an ECC ID 84. The ECC generator polynomials 82 each coincide with an ECC ID number 1 through n 84. An ECC generator polynomial is used with every frame that is transmitted and the ECC ID 84 is provided an ECC ID field 90 in the header 86 of each transmitted frame 88. Since a different ECC generator polynomial is most likely used for two identical data fields being transmitted from different nodes, then the receiving station or node could combine partially received frames or frames with errors therein into a usable frame using the different respective ECC generator polynomials from the transmitting nodes or stations. Although only certain embodiments of the apparatus and method of the present invention have been illustrated in the accompanying drawings and described in the foregoing detailed description, it would be understood that the invention is not limited to the embodiments disclosed but is capable of additional rearrangements, modifications, combinations, and substitutions without departing from the invention as set forth and defined by the following claims. Accordingly, it should be understood that the scope of the present invention encompasses all such arrangements and is solely limited by the claims as follows.

Claims

CLAIMSWhat is claimed is:

1. In a node (42) of an ad hoc network (40) a method of transmitting a data frame, said method comprising; using an ECC generation polynomial, which is probabilistically different from another ECC generation polynomial used in a neighboring node (44), to generate a first ECC for said data frame; and transmitting, by said node (42), said data frame (72, 88), said data frame comprising a first field having information to identify said ECC generation polynomial.

2. The method of claim 1, wherein said ECC generation polynomial is assigned to said node (42).

3. The method of claim 1 , wherein said ECC generation polynomial is one of a plurality of predetermined ECC generation polynomials (80).

4. The method of claim 3, wherein prior to the step of using, said method further comprises randomly selecting said ECC generation polynomial from said plurality of predetermined ECC generation polynomials (80).

5. The method of claim 3, wherein prior to the step of using, said method further comprises selecting said ECC generation polynomial from said plurality of predetermined ECC generation polynomials (80) using a round robbin technique.

6. The method of claim 3, wherein prior to the step of using, the method further comprises selecting said ECC generation polynomial from said plurality of predetermined ECC generation polynomials (80) by incrementing through a list of said plurality predetermined ECC generation polynomials by a calculated or predetermined amount.

7. The method of claim 1, wherein prior to the step of using, the method further comprises generating a random ECC generation polynomial that is used as said ECC generation polynomial in said step of using.

8. The method of claim 1, wherein said ad hoc network (40) is also a multi-hop network (40).

9. The method of claim 1, wherein said step of using further comprises enabling a receiving node (48) to recombine faulty received frames by recombining independently coded ECC information from said node (42) and at least said neighboring node (44).

10. In a node (42) in an ad hoc network (40), a method of transmitting a data frame (72), said method comprising: shifting a data field (70) of a data frame a first determined amount; using an ECC generator polynomial to calculate ECC for the data frame with the shifted data (76); indicating in a shift field (73) of said data frame (72) said first determined amount; and transmitting said data frame (72) from said node (42).

11. The method of claim 10, wherein said first determined amount (k) is a static number.

12. The method of claim 10, wherein said first determined amount (k) is a randomly chosen number.

13. The method of claim 10, wherein said first determined (k) amount is incremented at each transmission.

14. The method of claim 10, wherein said ad hoc network (40) is also a multi- hop network (40).

15. The method of claim 10, wherein said first determined (k) amount is probabilistically different from an amount that another data field, comprising identical data as said data field (70), is shifted in a neighboring node (44) prior to being transmitted.