RBNS Encoded Energy Efficient Routing Protocol for Wireless Sensor Network

Published Online April 2014 in MECS

Wireless Sensor Networks [2] can contain hundreds or thousands of sensing nodes. It is desirable to make these nodes as cheap and energy-efficient as possible and rely on their large numbers to obtain high quality results. Network protocols must be designed to achieve fault tolerance in the presence of individual node failure while minimizing energy consumption. In addition, since the limited wireless channel bandwidth must be shared among all the sensors in the network, routing

• II.    Redundant Binary Number System (RBNS) - An Introduction

• 2.1    Conventional Method of Communication

The rapid expansion of wireless services such as cellular voice, PCS (Personal Communications Services), mobile data and wireless LANs in recent years is an indication that significant value is  placed  on accessibility and portability as  key  features  of telecommunication. Wireless devices have maximum utility when they can be used “anywhere at any time”. One of the greatest limitations to that goal, however, is finite power supplies. Since batteries provide limited power, a general constraint of wireless communication is the short continuous operation time of mobile terminals. Therefore, power management is one of the most challenging problems in wireless communication, and recent research has addressed this topic. Studies show that the significant consumers of power in a typical laptop are the microprocessor (CPU), liquid crystal display (LCD), hard disk, system memory (DRAM), keyboard/ mouse, CDROM drive, floppy drive, I/O subsystem, and the wireless network interface card. A typical example from a Toshiba 410 CDT mobile computer demonstrates that nearly 36% of power consumed is by the display, 21% by the CPU/memory, 18% by the wireless interface, and 18% by the hard drive. Consequently, energy conservation has been largely considered in the hardware design of the mobile terminal and in components such as CPU, disks, displays, etc. Significant additional power savings may result by incorporating low-power strategies into the design of network protocols used for data communication.

Conventional communication methods are based on using energy for transmitting both 0s and 1s. Example, if e b be the energy required transmitting a bit; transmitting 286 would require 9 e b units of energy.

Energy-based Transmission Strategies [3] (EbTs)

• •    Spend Energy for Every Bit Transmitted

• •    Let e b = Energy required to Transmit a Bit

• •    Example : To transmit (286) 10 = (100011110) 2

Zhu and Sivakumar (2005) had also proposed an energy efficient Communication scheme and named it as through Silence (CtS) [3]. Traditional approaches to energy efficient communication have been through optimization of hardware and MAC protocols [6], intelligent routing and data aggregation techniques. CtS and VarBaTac were the first work to use silence for communicating information. But CtS suffers from exponential communication time in number of bits while the hardware complexity is extremely high in the VarBaTac scheme. Both schemes utilize silence to communicate both 0s and 1s. For example, to transmit a 16 bit message, CtS would require 2^16 time slots. Furthermore, both suffer from synchronization problem between transmitter and receiver. Moreover neither of the schemes talks of the BER or SNR with an actual implementation scenario. The following example demonstrates the communication of information using only Silent Time Slots.

Example 1: To Communicate (11101) 2 = (29) 10

requires 29 time slots

Example 2: To Communicate (01111100) 2 = (124) 10 requires 124 time slots

• •    Exponential Communication Time

  – Max. Possible value of n -bit data = 2 ⁿ - 1

Chen et. al. (2006) proposed another energy aware communication technology which was an extension of the existing CtS technique. This technique used higher Radix Encoding than CtS. The following example demonstrates the communication of information using the above mentioned scheme.

Example 1: (11101) 2 = (29) 10 = (1D) 16

• •    (1 + 13 + 2 * 2) = 18 time slots in Radix 16

Example 2: (01111100) 2 = (124) 10 = (7C) 16

• •    (7 + 12 + 2 * 2) = 23 time slots in Radix 16

• 2.2    Present Approach

In this scheme the Hardware Complexity increases with Higher Radix Communication Time Larger than n for n -bit Data.

Wireless networking has witnessed an explosion of interest from consumers in recent years for its applications in mobile and personal communications. As wireless networks become an integral component of the modern communication infrastructure, energy efficiency will be an important design consideration due to the limited battery life of mobile terminals. Power conservation techniques are commonly used in the hardware design of such systems. Since the network interface is a significant consumer of power, considerable research has been devoted to low-power design of the entire network protocol stack of wireless networks in an effort to enhance energy efficiency.

With the increasing use of wireless sensor networks (WSN) [5] in diverse applications where data to be communicated can range from few bytes of raw data to multimedia, the need for designing energy-efficient communication has attained paramount importance to increase the operational lifetime of such WSN [5]. Related to this issue, it is important to understand the distribution of runs of 1’s and 0’s in the data to be transmitted, so that suitable communication techniques can be designed. Such knowledge would also help in analyzing and comparing the performances of different energy-efficient communication techniques for a specific WSN application. RBNS [3][4] is one of the special type of energy efficient communication technique. This technique is described as follows. RBNS uses three symbols for communication namely -1, 0 and 1. It considers the positional weights same as Binary number system. In this type of communication system let us represent -1 by 1 ˊ . The communication of data using RBNS is described as follows:

Example 1: (7) 10 ≡ (111) 2 ≡ (1001 ˊ )

Example 2: (30) 10 ≡ (11110) 2 ≡ (10001 ˊ 0)

The Recoding Scheme in RBNS is described as follows:

– Consider a Run of ‘ k’ 1s, k > 1

– Let ‘ i’ be the Starting Bit Position of the Run (i >= 0)

– Let ‘ v’ be Value of the Run

Therefore, v = 2i + 2i + 1+ 2i + 2 + … + 2i + k – 1                    (1)

That is,v = 2 ^{k + I} – 2 ⁱ

Equation 1 implies that a run of k 1 ˊ s is replaced by

– 1 ˊ in Bit Position ‘i’

– (k – 1) intermediate 0’s

– 1 in Bit Position (k + i )

Further two reduction rules are used to reduce the communication of number of bits using RBNS.

• •    Reduction Rule 1 (RR1)

  – Recode Runs of 1’s of Length > 1 in Binary String to RBNS as above

• •    Reduction Rule 2 (RR2)

  – Replace Every 1 ˊ 1 in Resulting RBNS String by 01 ˊ

The strategy is to transmit resulting RBNS data using Silent Zero Communication Strategy and is described as follows:

– For each 0 in String, Switch off Radio (Sleep Mode)

– If 1 or 1 ˊ encountered, Switch on Radio and Transmit Corresponding Symbol.

• •    Reduction Rule 1 : Energy Savings of ( k – 2) e_b per

Run of Length k , k > 1

• •    Additional Savings Generated by Reduction Rule 2

• •    Transmitting (286) 10 = (100011110) 2 = (10010001 ˊ

0) RBNS requires 3 e b instead of 9 e b Units of Energy

Following examples demonstrates the advantage of RBNS scheme for data transmission through a communication channel.

Example 1

– Transmitting (124) 10 = (01111100) 2 = (100001 ˊ 00) RBN requires 2 e b instead of 8 e b Units of Energy

Example 2

– Transmitting (222) 10 = (11011110) 2 → (101 ˊ 10001

ˊ 0)RBN → (1001 ˊ 0001 ˊ 0)RBN   requires 3eb instead of 8eb Units of Energy.

• 2.3    Theoretical Analysis of RBNS Scheme

We have derived a recurrence relation for expressing N k , the total number of occurrences of runs of 1’s (or 0’s) of length k ,

– Let n = Binary String Length

– Denote a run of Length ‘ k ’ by R k

• •    y k = 0R k , 0 ≤ k ≤ n, y 0 = singleton 0

  – Find Total Number of Occurrences of R k ’s in All Possible 2 ⁿ Strings

• •    N n ^ik,k = Exactly i k number of y k ’s, each of size ( k + 1)

• •    N_n-k = Number of Runs of 1’s of Length ( n – k ), 0 ≤ k ≤ n

• 2.4    Solution to Recurrence Relation

N n - k = 2 N n - k + 1 + 2 ^{k - 2}, k ≥ 2

N n = 1, N n - 1 = 2

⇒ N n - k = ( k + 3)2 ^{k - 2}, k ≥ 2

Our method of finding this recurrence relation unveils the interdependencies among the total number of runs of different lengths which have hitherto been unexplored.

N _{n - k} = (k + 3)2^{k - 2}, k ≥ 2

• •    Applying Reduction Rules 1 and 2

  – Total Number of 1s and 1 ˊ s = ( n + 2)2 ^{n - 2}

• •    Total Number of Runs of Ones of All Possible ( n – k ) Lengths

n - 2

S = ∑ ( k + 3)2 ^{k - 2} + 3

k = 0

= n • 2 ^{n - 3}

• •    Number of 1s and 1 ˊ s after Applying Reduction Rule 1 is 2S + Number of Singleton 1s:

2 S + ( n + 2)2 ^{n - 3} = (3 n + 2)2 ^{n - 3}

• •    Fraction of Energy Savings After Applying Reduction Rules 1 and 2

  γ _e = 1 -

  
  

  = 1 -

  
  

( n + 2) • 2 ^{n - 2} n • 2 ⁿ n + 2

4 n

It results to, 7 e ≈ 69% for n = 8

e → 75% as n →∞

The analytical result shows that the RBNS system can significantly save the transmission energy for large runs of 1’s or 0’s in the string.

• III.    Application of RBNS on WSN Routing

In our work we have applied RBNS transmission system into existing LEACH [5] algorithm to propose an energy efficient routing for wireless sensor network.

Figure 1 shows different routing protocols for WSN.

Routing protocols in WSN

Network structure

Protocol operation

___*____

Flat Networks Routing

___t____

Hierarchical

Network's

Routing

Location based

Routing

negotiation based

Routing

Multi-path based Routing

Query based Routing

QoS based Routing

Coherent based Routing

Fig. 1: Routing protocols in WSNs: A taxonomy

• 3.1    Drawbacks of Existing LEACH

Existing LEACH protocol [1][7] for Wireless Sensor Network has the following drawbacks:

• >    LEACH protocol offers no guarantee on the placement of cluster head nodes.

• >    LEACH Centralized (LEACH -C) [7] a protocol that uses a centralized clustering algorithm and the same steady-state protocol as LEACH.

• >    During the set-up phase of LEACH-C, each node sends information about its current location and energy level to the BS.

• >    The clusters are formed such that total sum of squared distances between all the non- cluster head nodes and the closest cluster head is minimized.

• 3.2    Introduction of RBNS concept in the existing LEACH Algorithm:

• 3.2.1    First Order Radio Model

Fig. 2: First order radio model

The RBNS concept and the advantage of the RBNS encoding system has been described in the earlier sections. Next the existing RBNS encoding technique is applied in the existing LEACH algorithm for WSN. Before we discuss the implementation, we must see the radio model [10], which is used by LEACH protocol. And then we apply the aggregated energy savings in the bit levels.

Currently, there is a great deal of research in the area of low-energy radios. Different assumptions about the radio characteristics, including energy dissipation in transmit and receive modes, will change the advantages of different protocols. In our work, we assume a simple model [11][12] where the radio dissipates E elec =50 nJ/bit to run the transmitter or receiver circuitry and εamp=100pJ/bit/m² for the transmit amplifier to achieve an acceptable E b /N o . These parameters are slightly better than the current state-of-the-art in radio design. We also assume an r² energy loss due to channel transmission. Thus, to transmit a k-bit message a distance d using our radio model, the radio expends:

E Tx (k,d) = E Tx-elec (k) + E Tx-amp (k,d)

E Tx (k,d) = E elec * k + ε amp * k * d²

And to receive this message the radio expands:

E Rx (k) = E Rx-elec (k)

E Rx(k) = E elec * k

For these parameter values, receiving a message is not a low cost operation; the protocols should thus try to minimize not only the transmit distances but also the number of transmit and receive operations for each message. We make the assumption that the radio channel is symmetric such that the energy required to transmit a message from node A to node B is the same as the energy required to transmit a message from node B to node A for a given SNR. For our experiments, we also assume that all sensors are sensing the environment at a fixed rate and thus always have data to send to the end-user. For future versions of our protocol, we will implement an “event-driven” simulation, where sensors only transmit data if some event occurs in the environment.

Table 1: Energy details

Operation	Energy Dissipated
Transmitter Electronics (ETx elec) Transmitter Electronics (ERx elec) (ETx elec= ERx elec= E elec	50 nJ/bit
Transmiy Amplifier (Eamp)	100 pj/bit/m2

• 3.2.2    Introduction of RBNS encoding

Now, we have to introduce RBNS in this radio device [13] and have to compute the energy saves during the transmission. From previous issues we have seen how energy is saved by RBNS by reducing the number of 1s in a data string. Now, from the research and previous project works, we have concluded that no. of possible 1 in a string is = N2^N. After applying reduction Rule 1 and 2 the number of possible 1 and 1 ˊ s become less and from recurrence relation we have concluded that, Possible no of 1 and 1 ˊ are (N+2)2^N-2.

If we compare this number of 1 in the above two data strings, it is clear that we can save some energy if we introduce this in the LEACH protocol. Now we have to compare, how much energy we can save by this RBNS technique. The equation becomes:

γ _e = 1 -

( n + 2) • 2 ^{n - 2} n • 2 ⁿ

= 1 -

n + 2

4 n

γ e ≈ 69% for n = 8 ,

γ e ≈ 75% as n →∞

So we can conclude that γ e RBNS n →∞ is nearly 75%. Hence we can say that, in the 1^st order radio model E Tx and E Rx can save up to 75% energy.

• 3.3    Results, Energy Comparison and Proposed Implementation

The simulation of LEACH algorithm and modified LEACH algorithm with RBNS encoding have been carried out in MATLAB environment. The proposed work shows how energy is preserved and average lifetime of the network is increased after RBNS encoding scheme is applied over the existing LEACH algorithm. The assumptions made regarding the simulated environment are described in Table 2.

Table 2: Simulation Parameters used

Total Number of Nodes (n)	100
Initial Energy E o	0.5 J
ET x	50*0.000000001 J
ER x	50*0.000000001 J
Ef s	10*0.000000000001 J
ε Amp	0.0013*0.000000000001 J
EDA	5*0.000000001 J
Maximum number of rounds (rmax)	1250

Figure 3 shows the snapshot of execution of existing LEACH algorithm in the simulated environment. Table 3 demonstrates the statistics of the number of dead nodes, alive nodes and the time when the first dead node has been found in the system, after 1250 round of execution of the LEACH algorithm. Figure 4 shows the snapshot of execution of LEACH algorithm with RBNS encoding in the simulated environment. Table 4 summarises the statistics of the number of dead nodes, alive nodes and the time when the first dead node has been found in the system, after 1250 round of execution of the proposed algorithm. From the statistics it can be observed that in the case of LEACH algorithm the first node dies after 851 rounds where as in the second case the first node dies after 987 rounds. In the first case the total number of dead nodes after 1250 rounds is 71 where as in the second case it is only 6 after the same number of rounds. Figure 5 shows that the number of alive nodes with number of rounds in case of existing LEACH algorithm and proposed algorithm, where as Table 5 describes the performance comparisons of the two schemes. From the result it can be stated that our proposed scheme out performs the existing LEACH algorithm in terms of number of alive nodes over number of rounds. This is because in our proposed scheme using RBNS encoding the energy recruitment of the nodes for transmission and receive of packets is reduced extensively. Clearly from figure 5, it can be concluded that using RBNS in a WSN routing protocol can increase the lifetime of the network significantly and thus can save energy.

Fig. 3: System snapshot after 1250 rounds with dead and alive nodes

Table 3: Statistics of the system without RBNS

STATISTICS
first_dead	851
Dead nodes	71
Alive nodes	29
Packets to Base Station	21
Packets to CH	98

Fig. 4: Snapshot of the system after 1250 rounds dead and alive nodes (Leach with RBNS encoding)

Table 4: Statistics with RBNS

STATISTICS
first_dead	987
Dead nodes	6
Alive nodes	94
Packets to Base Station	20
Packets to CH	99

From Figure 5, we can observe the red lines showing number of alive nodes for LEACH algorithm without RBNS encoding and blue lines showing number of alive nodes in case of RBNS encoded LEACH algorithm. Clearly from the above figure, we can conclude that incorporating RBNS in a routing protocol like LEACH increases the lifetime of the nodes and thus saves the energy.

Table 5: comparative study of LEACH algorithm and RBNS encoded Leach algorithm

Parameters	Without RBNS	Using RBNS
first_dead	851	987
Dead nodes	71	6
Alive nodes	29	94
Packets to Base Station	21	20
Packets to CH	98	99

• 3.4    Proposed Implementation

In this section we present our proposed hybrid modulation scheme that utilizes ASK and FSK to implement the RBNS algorithm. Typically, in FSK we have a carrier freq. fc and two frequencies to represent the 2 binary symbols 0 and 1. For RBNS, we have implemented the hybrid modulation [14][15][16] Scheme Using FSK and ASK. The idea is as follows:

o Carrier Frequency fc o In Binary FSK, 0 and 1 Represented by fc , fc + Df o Map Frequencies fc and (fc + Df) to Symbols 1 and 1

ˊ o For Symbol 0 , Put Radio in Active State o Radio Switched to Transmit State for Other Symbols o Receiver Uses Non-Coherent Detection

• IV.    Conclusion

The work carried out for this paper, investigates energy efficient clustering algorithms related to WSNs. A hierarchical clustering algorithm based on RBNS has been proposed. This increases Network life of WSNs. Secondly, quality of service for IEEE 802.15.4 networks has been investigated for star and mesh topology using routing. The results show that encoding RBNS with LEACH algorithm can considerably save the network energy.