From: Michel Salomon Date: Wed, 16 Jul 2014 11:45:59 +0000 (+0200) Subject: Modifications made by Ali OK X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/JournalMultiPeriods.git/commitdiff_plain/5233a5d1825cb9b7d339cd22c7e752f17bb24572 Modifications made by Ali OK --- diff --git a/article.bib b/article.bib index d61f374..60609ba 100755 --- a/article.bib +++ b/article.bib @@ -122,6 +122,7 @@ sensor networks", journal = {Ad Hoc {\&} Sensor Wireless Networks}, volume = {1}, number = {1-2}, + pages = {89--124}, year = {2005}, } @@ -338,11 +339,12 @@ ISSN={1536-1276}, } @ARTICLE{pujari2011high, - title={High-Energy-First (HEF) Heuristic for Energy-Efficient Target Coverage Problem.}, - author={Pujari, Arun K}, + title={High-{E}nergy-{F}irst ({HEF}) Heuristic for Energy-Efficient Target Coverage Problem}, + author={Manjun and Pujari, Arun K}, journal={International Journal of Ad Hoc, Sensor \& Ubiquitous Computing}, volume={2}, number={1}, + pages={45--58}, year={2011} } @@ -501,6 +503,7 @@ ISSN={1536-1276}, title={A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints}, author={Casta{\~n}o, Fabian and Rossi, Andr{\'e} and Sevaux, Marc and Velasco, Nubia}, journal={Computers \& Operations Research}, + pages={--}, year={2013}, publisher={Elsevier} } diff --git a/article.tex b/article.tex index a4752b1..c729d58 100644 --- a/article.tex +++ b/article.tex @@ -117,24 +117,24 @@ Optimization, Scheduling, Distributed Computation. \indent The fast developments of low-cost sensor devices and wireless communications have allowed the emergence of WSNs. A WSN includes a large number -of small, limited-power sensors that can sense, process and transmit data over a -wireless communication. They communicate with each other by using multi-hop +of small, limited-power sensors that can sense, process, and transmit data over +a wireless communication. They communicate with each other by using multi-hop wireless communications and cooperate together to monitor the area of interest, so that each measured data can be reported to a monitoring center called sink -for further analysis~\cite{Sudip03}. There are several fields of application +for further analysis~\cite{Sudip03}. There are several fields of application covering a wide spectrum for a WSN, including health, home, environmental, military, and industrial applications~\cite{Akyildiz02}. On the one hand sensor nodes run on batteries with limited capacities, and it is -often costly or simply impossible to replace and/or recharge batteries, +often costly or simply impossible to replace and/or recharge batteries, especially in remote and hostile environments. Obviously, to achieve a long life -of the network it is important to conserve battery power. Therefore, lifetime +of the network it is important to conserve battery power. Therefore, lifetime optimization is one of the most critical issues in wireless sensor networks. On -the other hand we must guarantee coverage over the area of interest. To fulfill -these two objectives, the main idea is to take advantage of overlapping sensing +the other hand we must guarantee coverage over the area of interest. To fulfill +these two objectives, the main idea is to take advantage of overlapping sensing regions to turn-off redundant sensor nodes and thus save energy. In this paper, -we concentrate on the area coverage problem, with the objective of maximizing -the network lifetime by using an optimized multirounds scheduling. +we concentrate on the area coverage problem, with the objective of maximizing +the network lifetime by using an optimized multiround scheduling. % One of the major scientific research challenges in WSNs, which are addressed by a large number of literature during the last few years is to design energy efficient approaches for coverage and connectivity in WSNs~\cite{conti2014mobile}. The coverage problem is one of the %fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously @@ -177,15 +177,15 @@ algorithms in WSNs according to several design choices: \item The homogeneous or heterogeneous nature of the nodes, in terms of sensing or communication capabilities. \item The node deployment method, which may be random or deterministic. -\item Additional requirements for energy-efficient coverage and connected - coverage. +\item Additional requirements for energy-efficient and connected coverage. \end{itemize} The choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets) can be added to the above list. % The independency in the cover set (i.e. whether the cover sets are disjoint or non-disjoint) \cite{zorbas2010solving} is another design choice that can be added to the above list. -\subsection{Centralized Approaches} +\subsection{Centralized approaches} + The major approach is to divide/organize the sensors into a suitable number of set covers where each set completely covers an interest region and to activate these set covers successively. The centralized algorithms always provide nearly @@ -199,23 +199,20 @@ suffer from the scalability problem, making them less competitive as the network size increases. The first algorithms proposed in the literature consider that the cover sets are -disjoint: a sensor node appears in exactly one of the generated cover sets~\cite{abrams2004set,cardei2005improving,Slijepcevic01powerefficient}. - - -In the case of non-disjoint algorithms \cite{pujari2011high}, sensors may +disjoint: a sensor node appears in exactly one of the generated cover +sets~\cite{abrams2004set,cardei2005improving,Slijepcevic01powerefficient}. In +the case of non-disjoint algorithms \cite{pujari2011high}, sensors may participate in more than one cover set. In some cases, this may prolong the lifetime of the network in comparison to the disjoint cover set algorithms, but designing algorithms for non-disjoint cover sets generally induces a higher order of complexity. Moreover, in case of a sensor's failure, non-disjoint -scheduling policies are less resilient and less reliable because a sensor may be -involved in more than one cover sets. For instance, the proposed work in ~\cite{cardei2005energy, berman04} - +scheduling policies are less resilient and reliable because a sensor may be +involved in more than one cover sets. +%For instance, the proposed work in ~\cite{cardei2005energy, berman04} - - -In~\cite{yang2014maximum}, the authors have proposed a linear programming +In~\cite{yang2014maximum}, the authors have considered a linear programming approach for selecting the minimum number of working sensor nodes, in order to -as to preserve a maximum coverage and extend lifetime of the network. Cheng et +preserve a maximum coverage and extend lifetime of the network. Cheng et al.~\cite{cheng2014energy} have defined a heuristic algorithm called Cover Sets Balance (CSB), which choose a set of active nodes using the tuple (data coverage range, residual energy). Then, they have introduced a new Correlated Node Set @@ -225,10 +222,6 @@ algorithm to minimize the number of active nodes so as to prolong the network lifetime. Various centralized methods based on column generation approaches have also been proposed~\cite{castano2013column,rossi2012exact,deschinkel2012column}. - - - - \subsection{Distributed approaches} %{\bf Distributed approaches} In distributed and localized coverage algorithms, the required computation to @@ -238,28 +231,28 @@ processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers. -Some distributed algorithms have been developed -in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed, prasad2007distributed,Misra} -to perform the scheduling so as to preserve coverage. Distributed algorithms -typically operate in rounds for a predetermined duration. At the beginning of -each round, a sensor exchanges information with its neighbors and makes a -decision to either remain turned on or to go to sleep for the round. This -decision is basically made on simple greedy criteria like the largest uncovered -area \cite{Berman05efficientenergy} or maximum uncovered targets -\cite{lu2003coverage}. The authors in \cite{yardibi2010distributed} have developed a Distributed -Adaptive Sleep Scheduling Algorithm (DASSA) for WSNs with partial coverage. -DASSA does not require location information of sensors while maintaining -connectivity and satisfying a user defined coverage target. In DASSA, nodes use -the residual energy levels and feedback from the sink for scheduling the -activity of their neighbors. This feedback mechanism reduces the randomness in -scheduling that would otherwise occur due to the absence of location -information. In \cite{ChinhVu}, the author have proposed a novel distributed -heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), -which ensures that the energy consumption among the sensors is balanced and the -lifetime maximized while the coverage requirement is maintained. This heuristic -works in rounds, requires only one-hop neighbor information, and each sensor -decides its status (active or sleep) based on the perimeter coverage model -proposed in \cite{Huang:2003:CPW:941350.941367}. +Many distributed algorithms have been developed to perform the scheduling so as +to preserve coverage, see for example +\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed, + prasad2007distributed,Misra}. Distributed algorithms typically operate in +rounds for a predetermined duration. At the beginning of each round, a sensor +exchanges information with its neighbors and makes a decision to either remain +turned on or to go to sleep for the round. This decision is basically made on +simple greedy criteria like the largest uncovered area +\cite{Berman05efficientenergy} or maximum uncovered targets +\cite{lu2003coverage}. The Distributed Adaptive Sleep Scheduling Algorithm +(DASSA) \cite{yardibi2010distributed} does not require location information of +sensors while maintaining connectivity and satisfying a user defined coverage +target. In DASSA, nodes use the residual energy levels and feedback from the +sink for scheduling the activity of their neighbors. This feedback mechanism +reduces the randomness in scheduling that would otherwise occur due to the +absence of location information. In \cite{ChinhVu}, the author have designed a +novel distributed heuristic, called Distributed Energy-efficient Scheduling for +k-coverage (DESK), which ensures that the energy consumption among the sensors +is balanced and the lifetime maximized while the coverage requirement is +maintained. This heuristic works in rounds, requires only one-hop neighbor +information, and each sensor decides its status (active or sleep) based on the +perimeter coverage model from~\cite{Huang:2003:CPW:941350.941367}. %Our Work, which is presented in~\cite{idrees2014coverage} proposed a coverage optimization protocol to improve the lifetime in %heterogeneous energy wireless sensor networks. @@ -267,23 +260,23 @@ proposed in \cite{Huang:2003:CPW:941350.941367}. The works presented in \cite{Bang, Zhixin, Zhang} focuses on coverage-aware, distributed energy-efficient, and distributed clustering methods respectively, -which aims to extend the network lifetime, while the coverage is ensured. More recently, Shibo et al. \cite{Shibo} have expressed the coverage -problem as a minimum weight submodular set cover problem and proposed a -Distributed Truncated Greedy Algorithm (DTGA) to solve it. They take advantage -from both temporal and spatial correlations between data sensed by different -sensors, and leverage prediction, to improve the lifetime. In -\cite{xu2001geography}, Xu et al. have proposed an algorithm, called -Geographical Adaptive Fidelity (GAF), which uses geographic location information -to divide the area of interest into fixed square grids. Within each grid, it -keeps only one node staying awake to take the responsibility of sensing and -communication. +which aims to extend the network lifetime, while the coverage is ensured. More +recently, Shibo et al. \cite{Shibo} have expressed the coverage problem as a +minimum weight submodular set cover problem and proposed a Distributed Truncated +Greedy Algorithm (DTGA) to solve it. They take advantage from both temporal and +spatial correlations between data sensed by different sensors, and leverage +prediction, to improve the lifetime. In \cite{xu2001geography}, Xu et al. have +described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses +geographic location information to divide the area of interest into fixed square +grids. Within each grid, it keeps only one node staying awake to take the +responsibility of sensing and communication. Some other approaches (outside the scope of our work) do not consider a synchronized and predetermined period of time where the sensors are active or not. Indeed, each sensor maintains its own timer and its wake-up time is randomized \cite{Ye03} or regulated \cite{cardei2005maximum} over time. -The MuDiLCO protocol (for Multiround Distributed Lifetime Coverage Optimization +The MuDiLCO protocol (for Multiround Distributed Lifetime Coverage Optimization protocol) presented in this paper is an extension of the approach introduced in~\cite{idrees2014coverage}. In~\cite{idrees2014coverage}, the protocol is deployed over only two subregions. Simulation results have shown that it was @@ -291,11 +284,8 @@ more interesting to divide the area into several subregions, given the computation complexity. Compared to our previous paper, in this one we study the possibility of dividing the sensing phase into multiple rounds and we also add an improved model of energy consumption to assess the efficiency of our -approach. - - - - +approach. In fact, in this paper we make a multiround optimization, while it was +a single round optimization in our previous work. \iffalse @@ -377,8 +367,6 @@ algorithm to minimize the number of active nodes so as to prolong the network lifetime. Various centralized methods based on column generation approaches have also been proposed~\cite{castano2013column,rossi2012exact,deschinkel2012column}. - - \subsection{Distributed approaches} %{\bf Distributed approaches} In distributed and localized coverage algorithms, the required computation to @@ -388,28 +376,29 @@ processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers. -Some distributed algorithms have been developed -in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02, yardibi2010distributed} -to perform the scheduling so as to preserve coverage. Distributed algorithms -typically operate in rounds for a predetermined duration. At the beginning of -each round, a sensor exchanges information with its neighbors and makes a -decision to either remain turned on or to go to sleep for the round. This -decision is basically made on simple greedy criteria like the largest uncovered -area \cite{Berman05efficientenergy} or maximum uncovered targets -\cite{lu2003coverage}. In \cite{Tian02}, the scheduling scheme is divided into -rounds, where each round has a self-scheduling phase followed by a sensing -phase. Each sensor broadcasts a message containing the node~ID and the node -location to its neighbors at the beginning of each round. A sensor determines -its status by a rule named off-duty eligible rule, which tells him to turn off -if its sensing area is covered by its neighbors. A back-off scheme is introduced -to let each sensor delay the decision process with a random period of time, in -order to avoid simultaneous conflicting decisions between nodes and lack of -coverage on any area. In \cite{prasad2007distributed} a model for capturing the -dependencies between different cover sets is defined and it proposes localized -heuristic based on this dependency. The algorithm consists of two phases, an -initial setup phase during which each sensor computes and prioritizes the covers -and a sensing phase during which each sensor first decides its on/off status, -and then remains on or off for the rest of the duration. +Many distributed algorithms have been developed to perform the scheduling so as +to preserve coverage, see for example +\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02,yardibi2010distributed}. +Distributed algorithms typically operate in rounds for a predetermined +duration. At the beginning of each round, a sensor exchanges information with +its neighbors and makes a decision to either remain turned on or to go to sleep +for the round. This decision is basically made on simple greedy criteria like +the largest uncovered area \cite{Berman05efficientenergy} or maximum uncovered +targets \cite{lu2003coverage}. In \cite{Tian02}, the scheduling scheme is +divided into rounds, where each round has a self-scheduling phase followed by a +sensing phase. Each sensor broadcasts a message containing the node~ID and the +node location to its neighbors at the beginning of each round. A sensor +determines its status by a rule named off-duty eligible rule, which tells him to +turn off if its sensing area is covered by its neighbors. A back-off scheme is +introduced to let each sensor delay the decision process with a random period of +time, in order to avoid simultaneous conflicting decisions between nodes and +lack of coverage on any area. In \cite{prasad2007distributed} a model for +capturing the dependencies between different cover sets is defined and it +proposes localized heuristic based on this dependency. The algorithm consists of +two phases, an initial setup phase during which each sensor computes and +prioritizes the covers and a sensing phase during which each sensor first +decides its on/off status, and then remains on or off for the rest of the +duration. The authors in \cite{yardibi2010distributed} have developed a Distributed Adaptive Sleep Scheduling Algorithm (DASSA) for WSNs with partial coverage. @@ -526,7 +515,7 @@ range is said to be covered by this sensor. We also assume that the communication range satisfies $R_c \geq 2R_s$. In fact, Zhang and Zhou~\cite{Zhang05} proved that if the transmission range fulfills the previous hypothesis, a complete coverage of a convex area implies connectivity among the -working nodes in the active mode. +active nodes. Instead of working with a continuous coverage area, we make it discrete by considering for each sensor a set of points called primary points. Consequently, @@ -556,8 +545,10 @@ implemented in each subregion in a distributed way. As can be seen in Figure~\ref{fig2}, our protocol works in periods fashion, where each is divided into 4 phases: Information~Exchange, Leader~Election, Decision, and Sensing. Each sensing phase may be itself divided into $T$ rounds -and for each round a set of sensors (said a cover set) is responsible for the -sensing task. A multiround optimization process executed in each period after information exchange and leader election in order to produce a $T$ cover sets of sensors to take the mission of sensing for $T$ rounds. +and for each round a set of sensors (a cover set) is responsible for the sensing +task. In this way a multiround optimization process is performed during each +period after Information~Exchange and Leader~Election phases, in order to +produce $T$ cover sets that will take the mission of sensing for $T$ rounds. \begin{figure}[ht!] \centering \includegraphics[width=100mm]{Modelgeneral.pdf} % 70mm \caption{The MuDiLCO protocol scheme executed on each node} @@ -865,10 +856,10 @@ Sensing time for one round & 60 Minutes \\ $E_{R}$ & 36 Joules\\ $R_s$ & 5~m \\ %\hline -$w_{\Theta}$ & 1 \\ +$W_{\Theta}$ & 1 \\ % [1ex] adds vertical space %\hline -$w_{U}$ & $|P^2|$ +$W_{U}$ & $|P|^2$ %inserts single line \end{tabular} \label{table3} @@ -894,7 +885,7 @@ reduces the advantage of the optimization. In fact, there is a balance between the benefit from the optimization and the execution time needed to solve it. Therefore, we have set the number of subregions to 16 rather than 32. -\subsection{Energy Model} +\subsection{Energy model} We use an energy consumption model proposed by~\cite{ChinhVu} and based on \cite{raghunathan2002energy} with slight modifications. The energy consumption @@ -1052,7 +1043,6 @@ network in round $t$. \end{enumerate} - \section{Results and analysis} \subsection{Coverage ratio} @@ -1076,7 +1066,7 @@ the area of interest for a larger number of rounds. It also means that MuDiLCO-T saves more energy, with less dead nodes, at most for several rounds, and thus should extend the network lifetime. -\begin{figure}[t!] +\begin{figure}[ht!] \centering \includegraphics[scale=0.5] {R1/CR.pdf} \caption{Average coverage ratio for 150 deployed nodes} @@ -1097,7 +1087,7 @@ Obviously, in that case DESK and GAF have less active nodes, since they have activated many nodes at the beginning. Anyway, MuDiLCO-T activates the available nodes in a more efficient manner. -\begin{figure}[t!] +\begin{figure}[ht!] \centering \includegraphics[scale=0.5]{R1/ASR.pdf} \caption{Active sensors ratio for 150 deployed nodes} @@ -1120,14 +1110,14 @@ still connected. %%% The optimization effectively continues as long as a network in a subregion is still connected. A VOIR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{figure}[t!] +\begin{figure}[ht!] \centering \includegraphics[scale=0.5]{R1/SR.pdf} \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes } \label{fig6} \end{figure} -\subsection{Energy Consumption} \label{subsec:EC} +\subsection{Energy consumption} \label{subsec:EC} We measure the energy consumed by the sensors during the communication, listening, computation, active, and sleep status for different network densities @@ -1174,7 +1164,7 @@ optimization resolution, this time is multiplied by 2944.2 $\left( \frac{35330}{2} \times \frac{1}{6} \right)$ and reported on Figure~\ref{fig77} for different network sizes. -\begin{figure}[t!] +\begin{figure}[ht!] \centering \includegraphics[scale=0.5]{R1/T.pdf} \caption{Execution Time (in seconds)} @@ -1194,7 +1184,7 @@ optimization problem. %While MuDiLCO-1, 3, and 5 solves the optimization process with suitable execution times to be used on wireless sensor network because it distributed on larger number of small subregions as well as it is used acceptable number of round(s) T. We think that in distributed fashion the solving of the optimization problem to produce T rounds in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required. -\subsection{Network Lifetime} +\subsection{Network lifetime} The next two figures, Figures~\ref{fig8}(a) and \ref{fig8}(b), illustrate the network lifetime for different network sizes, respectively for $Lifetime_{95}$ @@ -1205,7 +1195,7 @@ deactivated and thus save energy. Compared to the other approaches, our MuDiLCO-T protocol maximizes the lifetime of the network. In particular the gain in lifetime for a coverage over 95\% is greater than 38\% when switching from GAF to MuDiLCO-3. The slight decrease that can bee observed for MuDiLCO-7 -in case of $Lifetime_{95}$ with large wireless sensor networks result from the +in case of $Lifetime_{95}$ with large wireless sensor networks results from the difficulty of the optimization problem to be solved by the integer program. This point was already noticed in subsection \ref{subsec:EC} devoted to the energy consumption, since network lifetime and energy consumption are directly @@ -1231,18 +1221,18 @@ linked. %We see that our MuDiLCO-7 protocol results in execution times that quickly become unsuitable for a sensor network as well as the energy consumption seems to be huge because it used a larger number of rounds T during performing the optimization decision in the subregions, which is led to decrease the network lifetime. On the other side, our MuDiLCO-1, 3, and 5 protocol seems to be more efficient in comparison with other approaches because they are prolonged the lifetime of the network more than DESK and GAF. -\section{Conclusion and Future Works} +\section{Conclusion and future works} \label{sec:conclusion} -In this paper, we have addressed the problem of the coverage and the lifetime -optimization in wireless sensor networks. This is a key issue as sensor nodes -have limited resources in terms of memory, energy, and computational power. To -cope with this problem, the field of sensing is divided into smaller subregions -using the concept of divide-and-conquer method, and then we propose a protocol -which optimizes coverage and lifetime performances in each subregion. Our -protocol, called MuDiLCO (Multiround Distributed Lifetime Coverage -Optimization) combines two efficient techniques: network leader election and -sensor activity scheduling. +We have addressed the problem of the coverage and the lifetime optimization in +wireless sensor networks. This is a key issue as sensor nodes have limited +resources in terms of memory, energy, and computational power. To cope with this +problem, the field of sensing is divided into smaller subregions using the +concept of divide-and-conquer method, and then we propose a protocol which +optimizes coverage and lifetime performances in each subregion. Our protocol, +called MuDiLCO (Multiround Distributed Lifetime Coverage Optimization) combines +two efficient techniques: network leader election and sensor activity +scheduling. %, where the challenges %include how to select the most efficient leader in each subregion and %the best cover sets %of active nodes that will optimize the network lifetime