Reduced Retransmission in Multi-Hop Wireless Networks with Realistic Physical Layer

Reduced Retransmission in Multi-Hop Wireless Networks with Realistic Physical Layer

Karthik. K

Pondicherry Engineering College, Puducherry

Tamilarasi. M

Pondicherry Engineering College, Puducherry

AbstractEnergy conservation is a challenging issue in Multi-hop wireless networks such as mobile ad hoc networks (MANETs), wireless sensor networks (WSN) and wireless mesh networks. The broadcasting algorithms which play a vital role in minimizing the energy consumption in multi-hop wireless networks generally consider the physical layer as ideal one in which the transmission and reception among neighbour nodes or base stations are successful. In reality, the wireless networks suffer from realistic physical layer due to real environment, where the reliability of the broadcasting services is reduced. This paper proposes a fuzzy logic based broadcasting algorithm in which each node in the network receives the broadcasting packet with certain probability in order to minimize the number of retransmissions so that the energy consumption will be reduced The simulation results indicate that the fuzzy logic based greedy heuristic broadcasting algorithm increases the gain cost ratio and reduce the retransmission overhead directly or indirectly while providing full network coverage.

Index TermsBroadcasting algorithm, energy consumption, gain cost ratio, multi-hop wireless networks, realistic physical layer, retransmission.

1. INTRODUCTION

   Multi-hop wireless networks such as mobile ad hoc networks (MANETs), wireless sensor networks (WSNs) and vehicular ad hoc networks (VANETs) are widely applied in environment survey, disaster relief, battlefield communication and so on. In multi-hop wireless networks broadcasting is a crucial operation. Almost all routing protocols rely on a simplistic form of broadcasting called flooding, in which each node retransmits received packet only once. This simple flooding leads to more number of retransmission in the network. Hence an enhanced flooding algorithm is required to reduce the number of retransmission in the network.

   Recently, a number of efficient broadcasting techniques have been proposed in which the retransmissions guarantee that broadcast packet is received by each node in the network.

   Many existing works assume an ideal physical layer model in which nodes receive packets successfully with probability 1 in a given transmission radius. Mineo Takai et.al,[12]observed that the realistic physical layer affected the performance of routing protocol in multi-hop networks.

   Broadcasting algorithms can be classified into five categories, namely Simple flooding, Probability based

   methods, Area based methods, neighbour knowledge based methods and Protocol chosen methods [3]. Common objective of these methods are to minimize the number of retransmission and thus minimize the energy consumption. In a simple flooding algorithm each node needs to rebroadcast all packets received for the first time but huge amount of retransmission occur therefore it leads to power loss [4]. Probability based methods, make use of the network topology information and assign a probability to a node to perform rebroadcasting [5]. In area based methods, wireless nodes assumes common transmission distances. A node will rebroadcast only if the rebroadcast will reach sufficient additional coverage area which is not applicable to broadcasting because it requires global information [10,11]. In neighbourhood knowledge methods, neighbourhood information needs to be collected in order to help making decision of rebroadcasting. In these methods, the sufficient and necessary condition for 100 percent delivery of flooding schemes is based on 1-hop neighbourhood information [6].

   Connected Dominating Set (CDS) forwarding node selection is applied in several broadcasting algorithms[7].The broadcasting algorithm used by T. Pongthawornkamol et al.[8] is not suitable for realistic physical layer. Xu et al.,[9] presented the redundant radius scheme for energy conservation. They proposed a broadcasting algorithm which needs overall network information where the transmission radius of each node is adjustable. This global information leads to more overhead and energy consumption to source node. Hence it is not suitable for energy constraint multi-hop network. The algorithm proposed by H.Xu and J.J.Garcia luna aceves [13] identifies the transmission radius to achieve a trade-off between energy efficiency and coverage. However, the algorithm cannot assure the each node receives the broadcasting packet with probability no less than a given requirement. A joint optimization between link layer and network layer addressed in [16] helps to find the good path for routing the sensed data to central node. It is suitable for unicast routing problem hence not for broadcasting. Imad S. Alshawi et al [2] presented a fuzzy logic based A-star algorithm which enhance the life time of wireless sensor node. A-star algorithm has high routing delay.

   In a realistic physical layer, the reliability of links is randomly changing according to locations of nodes, distance between the neighbour nodes, interference, path loss, noise and physical environment. Realistic environment should be considered to design an efficient broadcasting algorithm for

   broadcasting the packet. Otherwise each node fails to receive the broadcast packet. Such realistic physical layer is considered in this paper.

   Consider a unicast scenario where the receiver receives packet from a sender with a probability p which is less than 1. If p is low, retransmissions of the packet are required to attain successful reception. The probability that the receiver can successfully receive the broadcasting packet after n times of retransmissions is 1-(1-p)n. Finding the number of retransmissions to guarantee 100 percent reception for unicast scenario is crucial.

   Given a probability of reception , it is difficult to design a distributed broadcasting algorithm such that each node in the network is guaranteed to receive the broadcasting packet with probability no less than and to minimize the number of retransmissions. Several broadcasting techniques for multi-hop wireless networks have been studied frequently for the past two decades. In this paper, we propose a fuzzy logic based greedy heuristic algorithm for multi-hop wireless network with realistic physical layer where the reception probability of the node is decided by input variables such as transmission range and number of neighbours. Inputs and outputs are fuzzified in inference engine with help of rule base.

   From the above mentioned literatures we observe that a number of different parameters have been used to reduce the energy consumption of multi-hop networks. Those parameters are as follows:

   1. Retransmission: It is the one of the vital aspect of broadcasting in multi hop wireless networks [1]. Retransmission is caused due to interference and path loss. A broadcasting algorithm that uses these parameters will reduce the energy consumption of each node.

   2. Data rate: If data rate is high, it gives more overhead to each node. Due to overhead more energy will consume by node in multi-hop wireless networks.

   The rest of the paper is arranged as follows: section II describes a background of fuzzy approach and greedy heuristic algorithm. Section III proposes the greedy heuristic algorithm for efficient broadcasting. Section IV addresses the effectiveness of the proposed algorithm to minimize the number of retransmissions and energy consumption through simulations. Section V concludes the paer.

2. FUZZY APPROACH AND GREEDY HEURISTIC ALGORITHM

   1. Fuzzy Approach

      Fuzzy logic was first introduced by Lofti-Zadeh in 1965. Its application extended to control systems and NP-hard problems. It has the advantage of easy implementation and robustness.

      Fuzzy logic examine the information using fuzzy sets, each of which is represented by a linguistic term such as small, medium, and large. Fuzzy sets allow an object to be a partial member of a set. Then that object fuzzified through membership function. This membership functions represents a

      degree of belongingness for each object to a fuzzy set, and provides a mapping of objects to a continuous membership value in the interval [0…1]. When a membership value is equal to 1, it means that input value belongs to the respective set,

      with high degree, while small membership values equal to 0, indicate that input does not suit input very well.

      Fig.1. Typical structure of fuzzy approach

      In fuzzy systems, the energetic behaviour of a system is characterized by a set of linguistic fuzzy rules based on the information of human experts. These rules of the general form IF antecedent(s) THEN consequent(s), where antecedents and consequents are propositions containing linguistic variables. Antecedents and consequents contain linguistic variables. Antecedents of a fuzzy rule form a combination of fuzzy sets and logic operations. Thus, fuzzy sets and fuzzy rules together form rule-based inference system. Rule base is the important function of a fuzzy system which can be provided by human experts or from numerical data.

   2. Greedy heuristic algorithm

   The basic view of greedy algorithm is as follows: assume that each node in the network keeps 1-hop information including locations of 1-hop neighbours and quality of links. Each node, say i, determines the number of retransmission i so as to maximize the gain cost ratio which is defined as follows

   = (i )

   i

   (1)

   Where i is the number of retransmissions by node i and (i) is a subset of v(i) such that the packet received by the nodes in this set with probability no less than where node i

   retransmits the packet i times. Above ratio indicates that if

   number of retransmission is minimum then gain cost ratio is maximum. Each node in the network uses the minimal number of retransmission to guarantee that the neighbours which

   receive the packet with probability no less than .

   Remaining nodes that is V(i)- (i)nodes receive the packet

   with probability no less than . Therefore nodes in (i)are required to form a Connected Component Dominating Set (CCDS). It is defined as Given graph G=(V,E), a set C V is

   called a CCDS of G if and only if for any v in V belongs to C such that there is a path between v and c in G. This CCDS technique is one of deciding factor for broadcasting in the following algorithm.

   Consider the graph G=(V,E) as the multi-hop network formed by node i with set of neighbours V(i). Each node has knowledge of its neighbour node. Suppose two nodes i and ,j are neighbour nodes then ij is the number of retransmission

   from node i to j with probability higher than .Then node i

   calculate all gain cost ratioi where maximal value ofi * is

   chosen. By choosing maximum value, a set of nodes C will be formed based on ij . Then node i is required to verify if C is a CCDS of Gi If C belongs to G node i will proceed to broadcasting packet for ij*. If not i will eliminate all ij which is smaller than ij* and generate another set of i . Since the current ij* cannot guarantee to form a CCDS set therefore less coverage in the network by node i.

   In other words, source node i broadcast the common packet to neighbour nodes which are in the CCDS receives the broadcast packet. Now these nodes are act as new source node and again broadcast the packet to network. If old source node receives same packet with probability no less than then it stops the retransmission, while the neighbour nodes which are receives the broadcast packet will now act as source node and retransmit the packet again. Once the each node of the network has probability of reception is no less than than the retransmission of the nodes in overall network will terminate. Therefore retransmission count is reduced by proposed algorithm. At the system initial stage, each node gets its 1-hop neighbours information through BEACON messages. If 1-hop information is obtained then greedy algorithm can applied to broadcast packet in to the network. In wireless network, link quality may change occasionally. To handle this problem, nodes are requisite to exchange BEACON message to keep inform the 1-hop neighbours periodically. In addition to the link quality, the information of network diameter also required at each node. Once the broadcasting operation end, the node can estimate according to the maximum hop count among all received broadcasting packets.

3. FUZZY LOGIC BASED BROADCASTING ALGORITHM The proposed method assumes that all multi-hop nodes are

   randomly distributed in the area and every multi-hop node is assumed to know its own position and position of its neighbour nodes; all multi-hop nodes have the same maximum transmission range and each node has a certain amount of traffic pending in nodes queue.

   The main objective of this paper is to design a broadcasting algorithm that reduce the number of retransmission as well as increase the coverage percentage. To attain this, we make use of both the fuzzy approach and greedy heuristic algorithm.

   In the proposed broadcasting algorithm, the reception probability of each node is decided by fuzzy logic. The goal of the fuzzy part is to determine the reception probability of each node. Fig. 2 shows the fuzzy approach with two input variables R(n) and N(n) and an output , with universal of

   Fig. 2. Fuzzy structure with two inputs (transmission range and neighbouring nodes) and one output (reception probability)

   Fig. 3. Membership graph for the inputs (transmission range and neighbouring nodes) and the output (reception probability)

   discourse [40…80], [0…20] and [0…1], respectively. The proposed method uses triangular membership with five linguistic term for each input and an output variable, as shown in Fig. 3.

   In fuzzy approach, the fuzzified values are processed by the inference engine, which consists of a rule base and various methods to inference the rules. Here the rule base is a series of IF-THEN rules that link the input fuzzy variables and output variable using linguistic variables each of which is illustrated by fuzzy set and fuzzy implication factor AND.

   number of retransmissions. Each broadcasting packet is entrenched with an ID number which different from each other. Neighbour nodes broadcast the packet once they receive it, based on the algorithm

   1000

   900

   1866110153105314

   22 6 148 45

   77 1637

   159

   76

   97

   25

   63 142

   93

   26

   192

   141

   168

   81591

   123 170

   107

   193

   101885 88 15

   118

   800

   3 115 74

   34 70

   89

   187

   9846144

   64

   109

   41324

   82

   75

   700

   152 68

   164

   155 79

   102 57

   600

   17711229

   3836

   111156

   56

   8

   195

   177 31 183

   1130

   115134

   9

   500 99175 55

   147

   162 180

   90 48

   52

   3 53

   189

   73

   10

   4 154

   95

   400

   2570

   116

   23

   11637

   1323290

   300

   166

   140

   51872

   78 38

   182

   115311

   40 12172 105	100	47	183498
   174 146 31049	128		191717

   67

   198

   59 179

   5

   188

   126

   2

   137

   122

   12

   3292 35

   184

   54

   42141594

   17 14

   181

   29 49178 19 66

   200

   91111626510161

   91635

   69176

   157

   80

   28 120

   138

   169

   201073

   110 199

   36

   1824

   158

   100

   190 136

   41 106

   71 65

   119

   0

   101

   133

   143

   103

   19681

   104

   125

   61

   91461

   0 100 200 300 400 500 600 700 800 900 1000

   TABLE I

   IF-THEN RULES

   Table I shows the IF-THEN rules used in the proposed broadcasting algorithm, with a total number of 52=25 for t he rule base. If Transmission range is very low and number of neighbours is very low THEN number of retransmission is very low. Fuzzy inputs and outputs are processed by inference engine using rule base. At the end, the Defuzzification finds a single crisp output value from the fuzzy output. That output value represents the reception probability. Centre-of-gravity method is used for defuzzification which is given by

   Fig.4.Randomly generated multi-hop wireless network topology

   B. Simulation results

   In our simulation, we set the transmission range R=65 for 1000×1000 grind network. Fig.5 shows the total number of retransmission in the network for different algorithm. Greedy heuristic algorithm performs with more number of retransmission compare to fuzzy logic based greedy algorithm, since the node reception probability for greedy algorithm is fixed as 0.9, where in proposed greedy algorithm the reception probability is fixed by FIS(Fuzzy Inference System).Reception probability for each node gets vary. Some of the nodes in the networks do not need 0.9 reception probability. It means that some of the nodes in the network have less interference and path loss. Depend upon transmission range and number of neighbours, reception probability gets change. Using these

   parameters, the proposed algorithm reduces 10%

   = =1

   (2)

   retransmission compared to greedy algorithm.

   =1

   Where Ui is the output of rule base and ci is the centre of the output membership function.

4. PERFORMANCE EVALUATION

   A. Simulation setting

   We use Matlab as our simulation tool which generates a random multi-hop wireless network with number of nodes ranging from 100 to 500 which are distributed over a 1000mX1000m euclidean area. Source node is chosen indiscriminately among these nodes in the network. A network topology is illustrated in Fig.4.

   In the multi-hop network the location of nodes are randomly generated and the distance between two nodes are random. We set reception probability from the output of fuzzy logic. Reception probability gets vary depend on the transmission range and number of neighbour nodes.

   In our simulation, we run the algorithm for ten times to collect the sampling. Based on the algorithm, for each iteration the chosen source broadcasts a packet from 1 time to maximum

   650

   					Greedy Greedy and fuzzy

   600

   Total Number of Retransmission

   550

   500

   450

   400

   350

   300

   250

   200

   150

   100 150 200 250 300 350 400 450 500

   Number of nodes

   Fig. 5 Number of retransmission vs number of nodes

   					greedy and fuzzy greedy

   1

   0.9

   0.8

   coverage percentage

   0.7

   0.6

   0.5

   0.4

   0.3

   0.2

   0.1

   0

   100 150 200 250 300 350 400 450 500

   number of nodes

   Fig.6 Coverage percentage vs number of nodes

   							greedy and fuzzy greedy

   1

   0.9

   0.8

   coverage percentage

   0.7

   0.6

   0.5

   0.4

   0.3

   0.2

   0.1

   0

   50 52 54 56 58 60 62 64 66 68 70

   Transmission range

   Fig.7 Coverage percentage vs transmission range

   Fig.6 shows the coverage percentage vs number of nodes. Coverage percentage of proposed fuzzy based greedy heuristic algorithm has more coverage compared to greedy heuristic algorithm. The reason for less coverage is due to reception probability 0.9. Certain nodes in the network cant get data packet from neighbours therefore such nodes never attain the reception probability and do not forward the data. Fig.7 shows coverage percentage vs transmission range exposes that the proposed fuzzy logic based greedy heuristic algorithm has more coverage compare to greedy heuristic algorithm. If transmission range goes below 50, neighbouring nodes cant receive the data packet. If it is beyond 70 interference occurs. Hence coverage percentage is high between 50 to 70.

5. CONCLUSIONS

We presented the realistic communication problem in multi-hop wireless networks that forms the groundwork for numerous developments in broadcasting protocol. Greedy heuristic algorithm is a working method. In order to reduce retransmission further, we introduced fuzzy logic technique.

Fuzzy logic technique applied in Greedy heuristic algorithm brought out a goodperformance in terms of number of retransmissions in the network. Hence QoS such as reliability, energy efficiency and throughput are guaranteed.

REFERENCES

1. Gary K.W. Wong, Hai Liu, Xiaowen Chu, Yiu-Wing Leung and Chun Xie, Efficient broadcasting in multi-hop wireless networks with a realistic physical layer, Elsevier Ad hoc Networks Journal,vol.11, no.4, pp. 13051318, June 2013.

2. Imad s. Alshawi, Lianshan Yan and Wei Pan, Lifetime enhancement in wireless sensor networks using fuzzy approach and A-star algorithm, IEEE Sensors Journal,vol.12, no.10, pp. 3010-3018, Oct 2012.

3. B. Williams and T. Camp, Comparison of broadcasting techniques for mobile ad hoc networks, : Proceedings of ACM MobiHoc02, pp 194 – 205 , June 2002.

4. C. Ho, K. Obraczka, G. Tsudik and K. Viswanath, Flooding for reliable multicast in multi-hop ad hoc networks, Proceedings of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communication, , pp. 6471, June1999.

5. S. Ni, Y. Tseng, Y. Chen and J. Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of ACM/IEEE MOBICOM, pp. 151162, Dec1999.

6. H. Liu, X. Jia, P.J. Wan, X. Liu and F. Yao, A distributed and efficient flooding scheme using 1-hop information in mobile ad hoc networks, IEEE Transactions on Parallel and Distributed Systems ,vol 18 no.5,pp 658671,May 2007.

7. R. Misra and C. Mandal, Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks, IEEE Transactions on Parallel and Distributed Systems vol.21 no.3 ,pp 292 302, March 2010.

8. T. Pongthawornkamol, K. Nahrstedt and G. Wang, A hybrid probabilistic/deterministic approach for adjustable broadcast reliability in mobile wireless ad hoc networks, Proceedings of IEEE ICC , pp. 1

   6, June 2009.

9. H. Xu and J.J. Garcia-Luna-Aceves,Efficient broadcast in wireless ad hoc networks with a realistic physical layer, Proceedings of IEEE GLOBECOM, vol. 30, no.12pp.1-5, Dec.2008.

10. K. Sreenath, F.L. Lewis and D.O. Popa, Simultaneous adaptive localization of a wireless sensor network, ACM SIGMOBILE Mobile Computing and Communications Review vold.11, no.2, 2007.

11. I. Stojmenovic, M. Seddigh and J. Zunic, Internal node based broadcasting algorithms in wireless networks, in: Proceedings of ACM Hawaii International Conference on System Sciences, January2001.

12. M. Takai, J. Martin and R. Bagrodia, Effects of wireless physical layer modeling in mobile ad hoc networks, in: Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing, Long Beach, California, USA, pp. 8794,October 2001,.

13. H. Xu and J.J. Garcia-Luna-Aceves, Efficient broadcast for wireless ad hoc networks with a realistic physical layer, Elsevier Ad Hoc Networks Journal ,vol.8, no.2 ,pp. 165180 ,2010.

14. Y. Yi, M. Gerla and T.J. Kwon, Efficient flooding in ad hoc networks: a comparative performance study, in: Proceedings of IEEE ICC03, Alaska, USA, pp.1115, May 2003.

15. V. Rajendran and K. Obraczka, J.J. Garcia-Luna-Aceves, Energy- efficient, collision-free medium access control for wireless sensor networks, in: Proceedings of 1st ACM International Conference on Embedded Networked Sensor Systems, Los Angeles, 2003, pp. 181192.

16. Q. Cao, T. He, L. Fang, T. Abdelzaher, J. Stankovic and S. Son,

Efficiency centric communication model for wireless sensor networks, in: Proceedings of IEEE INFOCOM 2006.