Forward Error Correction in Sensor NetworksJaein Jeong and Cheng Tien EeDepartment of Electrical Engineering and Computer ScienceUniversity of California, BerkeleyMay 16, 2003AbstractIn any network, there are two basic methods to recover errorneous packets. One way is to useAutomatic Repeat Request (ARQ), and another is Forward Error Correction (FEC). Since, in sen-sor networks, power is scarce and is primarily consumed by wireless transmission and reception,we would prefer to use FEC rather than ARQ. In this paper we determine empirically the errorcharacteristics of wireless transmission signals, and from that, we implement and evaluate differenttypes of encoding schemes that are shown to be successful in reducing the error rates.Key words: sensor networks, forward error correction, ChipCon Radio1 IntroductionSensor nodes are physically small, and when fitted with various sensors such as digital thermometersas well as a means of wireless communications, can form a sensing network. These properties allowthe sensor networks to be easily deployed in all types of environments, and we expect such networksto become ubiquitous in the near future. However, having a small form factor and being distributedwithout a connection to any power grid means that the sensors have limited power. Table 1 shows thepower consumption due to various types of instructions, as determined in [3].Table 1: Power ConsumptionInstruction type Energy per cycle (nJ) Energy per instr (nJ)idle 1.70 1.70arithmetic/logic 3.41 3.41Device Energy per CPU cycle Energy per quantumLED 1.89 1.89 nJ/cycleRFM send 2.56 2050 nJ/bitRFM receive 2.44 1950 nJ/bitFrom Table 1 it is clear that most of the power is consumed during the transmission and receptionof data. By using FEC, we hope to reduce the need to retransmit data packets, thereby reducing thepower consumed in the process.Various encoding schemes, such as Reed-Solomon and LT Codes, are available and can be readilyimplemented. However, the choice of the encoding scheme depends on the application and the errorcharacteristics of the wireless channel. For sensor networks, most data transmitted are that of readings1taken periodically. For instance, the sensors might be gathering data every 5 mintues on the tempera-ture distribution of the geographical region over which they are scattered, sending just one packet pernode. This is in contrast to a Internetwork, where the transfer of data can be rapid and frequent as inthe case of streaming video. Also, the encoding scheme should be of relatively low complexity, sincea typical sensor currently has low processing power (8MHz) and a small memory (8Kbytes flash, 512bytes DRAM). Since Reed-Solomon and LT codes are relatively complex and require high processingpower and storage, they may not be ideal for our application. Furthermore, packets are sent betweenlong intervals, thus encoding schemes that need to work with several packets at a time can result in anincrease in latency to an unacceptable level. Thus, depending on the error characteristics, we wouldprefer using a simpler encoding scheme.1.1 BackgroundFigure 1: Network stack in wireless sensorsA wireless sensor node communicates with other sensor nodes using the network stack as shownin Figure 1. At the application level, data can be sent in packet form. Since the radio chip at thehardware layer can transmit and receive data byte-by-byte, these packets need to be fragmented beforethey can be sent and reassembled after being received. The media access control (MAC) layer inter-faces the application layer with the radio chip. When a packet is sent by an application, the packet isfragmented into bytes. A special sequence of bytes called the preamble is sent before the data bytes sothat the receiver can synchronize and detect the beginning of a packet. After receiving a byte, the radiochip bit-encodes the data and transmits them. At the receiver side, the radio chip signals the arrivalof bytes after detecting and decoding the data bits. Then, the MAC layer reassembles the packet be-ginning after the preamble. After that, the MAC layer signals the arrival of a packet to the upper layer.Data bytes can be optionally encoded after being fragmented with error correction code (ECC)to recover data bits in case of a small number of bit errors. One or more data bytes are mapped ontoanother sequence of data bytes, which are then passed to the radio chip. At the receiver side, thereceived data bytes are decoded to give the original data bytes.Bit modulation converts a bit input into an analog bit sequence [4]. The simplest bit modulationscheme is NRZ (Non-Return to Zero) encoding. NRZ encoding simply generates a waveform withvoltage level A for for an input bit 0 and voltage level B for the input bit 1. The radio transceiverkeeps track of the mean analog signal level to distinguish between the incoming bits. By comparingthe received signals with the average level, the transceiver converts the analog waveform to eitherthe binary value 0 or 1. This can pose a problem when there is a long sequence of 0s or 1s, whichskews the mean analog signal level, thus reducing the ability of the transceiver to correctly interpretthe transmitted digital signal. In NRZ encoding, stuffing, where we add the complement of the in-put bit after itself, needs to be done to avoid this problem. Manchester encoding removes this issueby generating the same number of 0s and 1s for any bit sequence. This encoding scheme encodes a20 to give a rising edge (A → B) and a 1 to give a falling edge (B → A). An example is shown in Figure 2.Figure 2: Comparison of NRZ encoding and Manchester encodingChipCon radio is the radio transceiver that is currently used in the latest generation of wirelesssensor nodes. Compared to RFM radio that was used in earlier platforms, the ChipCon radio hasseveral advanced features. Firstly, wireless sensor nodes with ChipCon radios have greater range thanthose with the RFM radio. In an outdoor test, ChipCon sensor nodes had a range of about 1000 feetcompared to about 400 feet for the RFM sensor nodes [5]. Secondly, the data bits are modulatedusing FSK (Frequency Shift Keying) making the data transfers more resilient to noise [6]. Lastly,the ChipCon radio supports Manchester encoding at the hardware level, allowing the data bits to betransmitted without the need for explicit, software-level DC balancing.Figure 3: Bit encoding of RFM radioThe error correction code for the RFM radio is
View Full Document
Unlocking...