International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

IJCNC 06

SCENARIOS OF LIFETIME EXTENSION ALGORITHMS FOR WIRELESS AD HOC NETWORKS

Amir J. Majid

College of Engineering, Ajman University, UAE

ABSTRACT


An Algorithm to extend sensor lifetime and energy is implemented for different scenarios of ad hoc and wireless sensor networks. The goal is to prolong the lifetimes of sensors, covering a number of targeted zones by creating subsets of sensors, in which each subset covers entirely the targeted zones. Probabilistic analysis is assumed in which each sensor covers one or more targets, according to their coverage failure probabilities. Case studies of different sensor subsets arrangements are considered such as load switching, variable target load demands as well as a perturbation in sensor planner locations. 

KEYWORDS


Ad hoc, case studies, failure probability, sensor lifetime, subsets, WSN.

1. INTRODUCTION


One of the most widely used wireless networks are the Wireless Sensor Network (WSN) and Ad Hoc networks, which are implemented in numerous industrial applications for sensing physical signals and data. These wireless networks are advantageous to wired networks due to monitoring and controlling area with limited human intervene, the absence of fixed infrastructure, multi-loop communication, yet they suffer from some shortcomings but mainly from the portable energy sources of supply, being limited and irreplaceable. The main limitation of such wireless networks is portable energy consumption, and hence network lifetime. Other limitations also exist, such as computing ability, sensing range, storage capabilities, yet this study deals with the prospective case of only lifetime and energy.

With the arrangement of the sensor in the groups or subsets, redundancies are eliminated by allowing them to operate at different time intervals, but with different failure probabilities. In order to control network reliability, sensor subsets with network coverage failure probability less than a preset threshold value may be considered for this study’s proposed algorithm in eliminating redundancies [1].

Ad hoc and sensor networks are modeled using the deterministic network model (DNM) [2], in which there is a transmission radius of each node where pairs of nodes are always reached to their neighbors if their physical distance is less than this radius., while the rest of pairs are disconnected. Several empirical studies [3] tackled this case. Further study suggested that nodes are always connected via some probabilistic values, therefore all nodes can be considered reaching each other with certain probability [6].

Several options of related work are presented, such as dominating, clusters and graphs, to ease analysis. Methods such as Greedy-based, Genetic and probabilistic analysis are considered. Most of these algorithms and methods are outlined in the literature [7]. Based on well-known algorithm, the ASP algorithm, many algorithms propose to organize sensors into subsets such that each set completely covers all targets, and scheduling the time to make these subsets activated so that one set is active any time instant, hence avoid redundancy. This would reduce energy waste and thus prolong lifetime. Several algorithms were implemented such as genetic, linear programming, greedy, scheduling techniques, to name a few [4] [5] [6]. However, another prominent problem in target coverage is how to improve reliability of the whole system, as due to environment, nodes may become unavailable or malfunction because of physical damage, lack of power, shadowing, fading

A number of case studies and scenarios, are introduced for a general S-T (sensor-target) coverage situation, based on the α-Reliable Maximum Sensor Coverage (α-RMSC) problem, each with a special task in a step-by-step simulation manner [8] [9] [10] [11] [12] [13] [14]. Further case studies such as variations of network load demand, switching of network load demand as well as variations in the locations of sensors covering target zones, were considered and simulated on Matlab platform [15] [16].

In In this work, proposed algorithms for different scenarios and case studies with simulations are implemented. These cases include load demand switching of the targeted areas, orientation of sensors to fulfill energy conservation requirements, life extension depending on daily load life cycle. One sensor-target network study model is used for all case studies.

2. ALGORITHM OF SENSORS LIFETIME & TARGET ZONES COVERAGE


With the assumption of sensor subsets covering targeted zones, consider a number of sensors Si covering a different number of targets Tj according to failure probabilities of sfpij, the target failure probability tfp for each target by one subset is

and thus the whole network failure coverage is

 

where cfpr is coverage failure probability of a subset of sensors covering all targeted zones which is required to be less than α; a predefined value set by user. Figure 1 demonstrates a case study of four sensors targeting three zone areas with different failure probabilities.

 


Figure 1. Two-dimensional view of four sensors targeting three zones.

Hence, we want to maximize total lifetime of the network T,

where tk is lifetime of each sensor subset which covers all targets with a certain coverage failure probability and wk is associated weight, which may be depending on external constraints. In order to calculate lifetime extension, it is assumed that a cyclic round of time slots related to each sensor subset is activated. It is noted that at any time, different subsets are energized during tile slots depending on their contributions. A subset with lower coverage failure probability would have larger time slot and be energized more. Different intuitive methods can be implemented to realize total lifetime extension, as depicted in Fig. 2

 


Figure 2. Different implementations of lifetime extension

Based on above equations, an implemented algorithm of basic case study of calculating lifetime extension is depicted in Fig. 3. Extra blocks are added for the different scenarios of case studies. In our basic system of four sensors and 3 targets, it can be seen that there exists 9 possible sensor subsets among 4 sensors which cover all three targets: {1,4}, {1,2,3}, {1,2,4}, {2,3}, {2,4},

{1,2,3,4}, {2,3,4}, {1,3,4} and {3,4}. A failure coverage probability of value 1 indicate no coverage to that target zone.


Figure 3. Flowchart of the simulation program.

From eq. (1) failure probability of sensors to targets is calculated, then the network coverage failure probability is calculated from Eq. (2). All possible subsets covering all targets successfully, are checked with a predominate value of minimum failure coverage, denoted by α, that is inputted by user, to get updated working subsets,

SS={S1, S2,… Sk}. There exist maximum 2k subsets of SSr, in which the algorithm identifies

them. Different values of α’s is chosen, with the higher α value the more subset choices. Various values of sfp for the individual sensors are selected to check their impact on network coverage failure probability, since these they are more effective than the effect of α. Figure 4 demonstrates a sample of these case studies.

The first 2 cases are: 


The next 2 cases are:


Figure 4. Lifetime extension of a 3S-2T network.

The overall result is represented in Fig. 5, as a 3D bar plot of the lifetimes verses the inputted coverage failure probabilities α’s, for different sensor-target arrangements.


Figure 5. Lifetimes extension of 3 sensors of different failure probabilities.

Figure 6 depicts the improvement in network lifetime when the adopted ad hoc algorithm is implemented on a three sensors network covering two targets. It can be seen that the lifetime can be doubled or even more depending on the predominate value α inputted by user and also on the kind of sensor-target network arrangements, ranging from one to six targets.


Figure 6. Lifetime extension for a 3 sensors covering two targeted areas

3. VARIABLE LOAD DEMANDS OF TARGETS


Figure 7 exhibits three different types of polynomials describing the cyclic daily load demand by the targeted zones. One can estimate these polynomials from the timing of the measurement made.


Figure 7. Target load polynomials for three day periods

We use this example as a case study for three different polynomials of the target demanded loads, measured at three different periods of the day. It is possible to consider more measuring points at any time slot, more accurately. In this case study we assume that a maximum utilized energy is reference unity, and hence the load demand can be only portion of this referenced value, and therefore reserved energy is spared for periods when demanded. In this way, we can preserve energy and power from this assumption. Network lifetime will be extended as a result.

The relation between sending and receiving power in a free space condition can be in general expressed as,

and for the non-free space

 

hr and ht are the heights of receiver and transmitter respectively.

Geometric constants Gr and Gt = 4π Ae /λ2 for both receiver and transmitter, Ae is effective distance aperture of the antenna,

λ is signal wavelength,

d is the covered distance by sensors L is a lost factor,

Pt is the transmitted power.

Figure 8 shows a different polynomial degree of orders 0, 1, 2, and 3 that can be concluded from the above figure. One can note that sensor energy is linearly proportional with load switching of the targets. Hence, sensor contribution to the network is proportional to cyclic switching of the target loads.

 


Figure 8. Polynomial degree order with four measuring points

In order to extend study for other scenarios, some considerations are taken into account for the above algorithm. We need to adjust the predominate network coverage failure value α according to the following intuitive formulization,

where Li(j) is considered the different time slots in which the target is demanding load. This value is rounded up to a maximum value of 1 as an imposed reference. As a result, more sensor subsets are created, that will give more chances for the lifetime to be extended.

Hence, target failure probabilities of the j targets are increased by the cyclic load demands Li (j)

expressed as follows, 

Further, the total sensors subsets lifetime T is calculated by summing of all time slots, i.e. ∑ Tj. in which Tj is portion of network lifetime preserved in interval j, expressed as: 

Hence the slotted network lifetime is increased by a factor of i/∑ Li, which is due to the fact that maximum energy is linearly proportional to target time zones i/t(j). The total lifetime is computed by adding all lifetime slots of the switching load cycle periods, according to the area under the load demands.

As a case study, the algorithm is implemented on a number of target load demands, each having a polynomial of different degree, say 1st, 2nd, 3rd or 4th order. Five maximum measuring points are used in evaluating the polynomial of the target load pattern.

4. PROLONGING NETWORK LIFETIME VIA LOCATION PERTURBATIONS


Considering location perturbations in the sensor-target network, would lead to variations in the sensor failure probabilities. We want to reallocate or adjust sensors positions in order to prolong network lifetime. This is demonstrated in Fig. 9, and estimated as below, 


Figure 9. Location perturbation in S-T network

It can be seen that the relation between d and dx is

Where y= tan-1[ (yT –yS)/(xT-xS)], and (xS,yS) and (xT,yT) are the sensor and target coordinates respectively.

Hence it is needed to correct the sensor failure probability sfp as: 

Table I, shows the result of implementing the proposed algorithm on the studied sensor network case of three sensors targeting two zones,

Table 1. Sensor location perturbations

 


The following figure demonstrates the increase of network lifetime more than 200% in relation with the perturbation in position x-y coordinates, with three sensors and two targets. It can be deduced that there was no dominant effect on the sensor failure probability (sfp), which is valid even when values of different fixed and variable sensor failure probabilities sfp were chosen.


Figure 10. Sensor-target variations in locations (3 Sensors + 2 Targets)

Figure 11 depicts locations of sensors on one side opposite to the targets position on the other, whereas Figure 12 shows the same network with the targets surrounding all sensors in a circle round pattern. It can also be noted that network lifetime increased further when 20% variations in sensors

 


Figure 11. Sensor-target variations in locations (4 sensors + 3 targets)


Figure 12. S-T variations in locations (4 sensors + 3 targets), with targets surrounded targets

5. LIFETIME EXTENSION DUE TO SWITCHING LOAD DEMAND


It can be deduced that sensor power and consequently sensors energy are linearly proportional with the switching target load in demand, and therefore any target energy in demand will be reflected linearly on the energy of the sensor. A scenario is studied in which three different load demands used by the targets (in this case three), each with two different patterns of load demand. For example, for load demand it is 50% in period 1 and 90% in period 2, etc. As a result energy is saved or preserved for further load demand, which will eventually prolong the lifetime of the sensors.


Figure 13. Switching target load demand of WSN

In this work, three different conditions are assumed, that’s the new network coverage failure probability is adjusted as,

Li(j) is for all ith targets in the jth interval t, which is rounded up unity when exceeding limit, as  we cannot get values greater than 100%. Hence target failure probabilities can be adjusted as follows, 

It is to be noted that if the above value exceeds 1, then it is adjusted to the maximum value of 1.

Thirdly, the total subset lifetime Ttotl is calculated as

before, i.e. Ttotal= ∑ Tj. Therefore one can deduce intuitively that the time slots of the period lifetime is increased with the same proportionality of i/∑ Li , because the default reference energy is equal to the number of target time slots i/t(j). As an example, a random scenario is considered with two sensors and 3 target zones with 4 switching time periods of 20%, 30%, 40% and 10% of entire time. Random sensor failure probabilities are assumed. Different load demands for the individual target zones and for each period time are considered This is depicted in Table II and III.

Table 2. 2S-3T failure probabilities


Table 3. Four load periods

 


The target load demands for these four periods are selected as shown in Fig. 14, a case in which the load is random for each target zone and in each time period, with the target load for period 1=

{30%, 50%,  100.},  period 2={30%,80%,0%}, period 3={40%,  70%, 0%}, and period 4={10%, 0%, 100%}


Figure 14. Cyclic target load demand for four periods of a 2S-3T network

The load distribution of the load target demand for this example is shown in Fig. 15, in which the energy lifetime reference is increased to 2.3256. Each load period shares the total lifetime increase. It would be advantageous to switch sensors according to the proposed algorithm, following targets load in demand over several time periods, in order to increase network energy and lifetime in which only constant changes of load were considered in this study.


Figure 15. Lifetime distribution of a 2S-3T network with 4 switching load periods

Ten simulation cases are considered for simulating the target load switching scenarios as depicted in Table IV. Two load switching periods are assumed in all cases except for case 10, in which 3 periods are considered. Different target load percentages are studied in these switching periods.

Table IV. Listing of different cases studied

Table 4. Listing of different cases studied


It can be noted that different increase in lifetime-energy, is obtained in all cases. For example, an increase of 3.2258 in energy-lifetime reference is obtained with L1=30%, L2=70%, but when these load demand figures are swapped to 70% and 30%, energy-lifetime reference was increased to 5.2632. This discrepancy is due to the two different switching time periods of 20% and 80% respectively. Thus a reduction in the predominate time period would result a larger energy reserve. In case 10, a random scenario is considered with two sensors and 3 target zones with 4 switching time periods of 20%, 30%, 40% and 10% of the entire time. Random sensor failure probabilities are assumed. Also different load demands for the individual target zones and for each period time are considered. Energy-lifetime reference is increased to 2.3256.

6. CONCLUSION


Algorithms of different scenarios of wireless sensors networks, covering a number of target zones have been implemented and simulated with different scenarios of case studies, such as numbers of sensors and targets, location perturbations, daily load demands for the individual target zones and switching load demands, in which it is found that the energy-lifetime reference is increased  to 200-300%. This paper is a summary of all results obtained from previous case studies conducted by the author.

A number of different cases of target load profiles, as well as a number of switching periods of the sensors subsets, are considered. Target load demand profiles are assumed with different polynomial degrees ranging from 0 to 4. The network lifetime is increased to 2.8574 times the lifetime when no switching is imposed. Among the different switching scenarios, one which two sensors and 3 target zones with 4 switching time periods of 20%, 30%, 40% and 10% of entire time, is considered, with random sensor failure probabilities. The lifetime is increased in all cases.

Perturbations in the S-T location of different S-T network configurations are studied such as in- line sided sensors-targets, and sensors surrounded 360o by targets. The lifetime is increased more than double fold. Maximum network is attained when only around 20% variation in sensor coordinates are made.

CONFLICTS OF INTEREST


The authors declare no conflict of interest.

REFERENCES


[1] I.F. Akyildiz, et.al., “A Survey on sensor networks”, Communication Magazine, IEEE, 40(8), pp. 102-114, 2002
[2] C.Luo, et al, “Compressive data gathering for large scale wireless sensor networks”, Proceedings of the 15th Annual International Conference on Mobile Computing and Networking, pages 145-156, ACM, 2009.
[3] M.Zunig , et, al, “Analyzing the transitional regions in low power wireless links”, Firt Annual IEEE Communication Society Conference, pages 517-526, 2004.
[4] G. Zhou, et al, “Impact of radio irregularity on wireless sensor networks”, Proceedings of 2nd International Conference on Mobile Systems, pages 125-138, ACM, 2004
[5] A. Cerpa, et al, “Temporal properties of low power sireless links:modeling and implications on multi- hop routing. Proceedingss of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 414-425, 2005.
[6] A. Cerpa, et al, “Stastical model of lossy links in wireless sensor networks”, Informational Proceedings in Sensor Networks, Fourth International Symposium, pages 81-88, 2005.
[7] Jing He, Shouling Ji, Yi Pan, Yingshu Li, Wiress Ad Hoc and Sensor Networks, Book, CRC Press, 2014.
[8] A. Majid, “Matlab Simulations of Ad Hoc Sensors Network Algorithm”, International Journal on Recent and Innovation Trends in Computing and Communication, Volume 3, Issue 1, January 2015.
[9] A. Majid, “Algorithm of Ad Hoc Sensors Lifetime and Target Zones Coverage Simulation”, International Journal of Innovative Research in Advanced Engineering, IJIRAE, Issue 4, Volume 2, April 2015.
[10] A. Majid, “Algorithms With Simulations of Network Sensors Lifetime and Target Zones Coverage”, International Knowledge Press, IKP Vol. 6, Issue 3, Journal of Mathematics and Computer Research ISSN No 2395-4205 Print, 2395-4213 On line, June 2015
[11] A. Majid, “Maximizing Ad Hoc Network Lifetime Using Coverage Perturbation Relaxation Algorithm”, WARSE International Journal of Wireless Communication and Network Technology Vol. 4, No 6, Oct-Nov 2015, ISSN 2319-6629
[12] A. Majid, “Prolonging Network Energy-Lifetime Of Load Switching WSN Systems”, Science solve,
Journal of Algorithms, Computer Network, and Security, Vol.1 No.2, March 2016
[13] A. Majid, “Algorithms of Wireless Ad Hoc Sensors in Robotics”, 3rd International Conferene on Artificial Intelligence & Robotics”, June 28-29, 2017, San Diego, USA.
[14] A. Majid, “Algorithms of Wireless Ad Hoc Sensors in Robotics”, Int. J. Robotics and Automation Engineering, IJRAE, Vol. 2018, Issue-01.
[15] Jon W. Mark, Weihua Zhuang Wireless Communications and Networking, A book, Prentice Hall
[16] Theodore S, Wireless Communications: Principles and Practice, A book, 2nd edition, Prentice Hall.

AUTHOR


Received M.Sc. degree in Electrical Systems Engineering from Surrey University, England, in 1976, and Ph.D. in Electrical Engineering from University of Loughborough, England in 1980. He has an industrial experience of 8 years in power stations, and industrial installations, and an academic experience of over 25

years in multi-national universities, with research in versatile fields of electrical engineering.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Information

This entry was posted on December 12, 2020 by .
%d bloggers like this: