X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/UIC2013.git/blobdiff_plain/8ab0f8781a3c93346920e6762d19e6ba7175f910..HEAD:/bare_conf.tex diff --git a/bare_conf.tex b/bare_conf.tex index 206d113..bbe85c3 100644 --- a/bare_conf.tex +++ b/bare_conf.tex @@ -11,7 +11,6 @@ \hyphenation{op-tical net-works semi-conduc-tor} - \usepackage{etoolbox} \usepackage{float} \usepackage{epsfig} @@ -40,7 +39,6 @@ \DeclareGraphicsExtensions{.ps} \DeclareGraphicsRule{.ps}{pdf}{.pdf}{`ps2pdf -dEPSCrop -dNOSAFER #1 \noexpand\OutputFile} - \begin{document} % % paper title @@ -69,7 +67,7 @@ subregions using a divide-and-conquer method and then the scheduling of sensor node activity is planned for each subregion. The proposed scheduling considers rounds during which a small number of nodes, remaining active for sensing, is selected to ensure coverage. Each -round consists of four phases: (i)~Information Exchange, (ii)~Leader +round consists in four phases: (i)~Information Exchange, (ii)~Leader Election, (iii)~Decision, and (iv)~Sensing. The decision process is carried out by a leader node, which solves an integer program. Simulation results show that the proposed approach can prolong the @@ -86,40 +84,67 @@ Optimization, Scheduling. \section{Introduction} -\indent The fast developments in the low-cost sensor devices and -wireless communications have allowed the emergence the WSNs. 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 wireless communications, cooperate together to monitor the area of interest, -and the measured data can be reported to a monitoring center called sink -for analysis it~\cite{Sudip03}. There are several applications used the -WSN including health, home, environmental, military, and industrial -applications~\cite{Akyildiz02}. The coverage problem is one of the -fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously -the area of interest. Thelimited energy of sensors represents the main challenge in the WSNs -design~\cite{Sudip03}, where it is difficult to replace and/or recharge their batteries because the the area of interest nature (such -as hostile environments) and the cost. So, it is necessary that a WSN -deployed with high density because spatial redundancy can then be -exploited to increase the lifetime of the network. However, turn on -all the sensor nodes, which monitor the same region at the same time -leads to decrease the lifetime of the network. To extend the lifetime -of the network, the main idea is to take advantage of the overlapping -sensing regions of some sensor nodes to save energy by turning off -some of them during the sensing phase~\cite{Misra05}. WSNs require -energy-efficient solutions to improve the network lifetime that is -constrained by the limited power of each sensor node ~\cite{Akyildiz02}. In this paper, we concentrate on the area -coverage problem, with the objective of maximizing the network -lifetime by using an adaptive scheduling. The area of interest is -divided into subregions and an activity scheduling for sensor nodes is -planned for each subregion. In fact, the nodes in a subregion can be -seen as a cluster where each node sends sensing data to the cluster head or the sink node. Furthermore, the activities in a -subregion/cluster can continue even if another cluster stops due to -too many node failures. Our scheduling scheme considers rounds, where -a round starts with a discovery phase to exchange information between -sensors of the subregion, in order to choose in a suitable manner a -sensor node to carry out a coverage strategy. This coverage strategy -involves the solving of an integer program, which provides the -activation of the sensors for the sensing phase of the current round. +%\indent The fast developments in the low-cost sensor devices and +%wireless communications have allowed the emergence the WSNs. 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 wireless +%communications, cooperate together to monitor the area of interest, +%and the measured data can be reported to a monitoring center called +%sink for analysis it~\cite{Sudip03}. There are several applications +%used the WSN including health, home, environmental, military, and +%industrial applications~\cite{Akyildiz02}. The coverage problem is one +%of the fundamental challenges in WSNs~\cite{Nayak04} that consists in +%monitoring efficiently and continuously the area of +%interest. Thelimited energy of sensors represents the main challenge +%in the WSNs design~\cite{Sudip03}, where it is difficult to replace +%and/or recharge their batteries because the the area of interest +%nature (such as hostile environments) and the cost. So, it is +%necessary that a WSN deployed with high density because spatial +%redundancy can then be exploited to increase the lifetime of the +%network. However, turn on all the sensor nodes, which monitor the same +%region at the same time leads to decrease the lifetime of the network. + +Recent years have witnessed significant advances in wireless +communications and embedded micro-sensing MEMS technologies which have +led to the emergence of Wireless Sensor Networks (WSNs) as one of the +most promising technologies \cite{Akyildiz02}. In fact, they present +huge potential in several domains ranging from health care +applications to military applications. A sensor network is composed of +a large number of tiny sensing devices deployed in a region of +interest. Each device has processing and wireless communication +capabilities, which enable it to sense its environment, to compute, to +store information and to deliver report messages to a base station +\cite{Sudip03}. One of the main design issues in WSNs is to prolong +the network lifetime, while achieving acceptable quality of service +for applications. Indeed, sensors nodes have limited resources in +terms of memory, energy and computational power. + +Since sensor nodes have limited battery life and since it is impossible to +replace batteries, especially in remote and hostile environments, it +is desirable that a WSN should be deployed with high density because +spatial redundancy can then be exploited to increase the lifetime of +the network. In such a high density network, if all sensor nodes were +to be activated at the same time, the lifetime would be reduced. To +extend the lifetime of the network, the main idea is to take advantage +of the overlapping sensing regions of some sensor nodes to save energy +by turning off some of them during the sensing phase~\cite{Misra05}. +Obviously, the deactivation of nodes is only relevant if the coverage +of the monitored area is not affected. In this paper, we concentrate +on the area coverage problem \cite{Nayak04}, with the objective of +maximizing the network lifetime by using an adaptive scheduling. The +area of interest is divided into subregions and an activity scheduling +for sensor nodes is planned for each subregion. In fact, the nodes in +a subregion can be seen as a cluster where each node sends sensing +data to the cluster head or the sink node. Furthermore, the +activities in a subregion/cluster can continue even if another cluster +stops due to too many node failures. Our scheduling scheme considers +rounds, where a round starts with a discovery phase to exchange +information between sensors of the subregion, in order to choose in a +suitable manner a sensor node to carry out a coverage strategy. This +coverage strategy involves the solving of an integer program, which +provides the activation of the sensors for the sensing phase of the +current round. The remainder of the paper is organized as follows. The next section % Section~\ref{rw} @@ -139,44 +164,41 @@ the coverage lifetime maximization problem, where the objective is to optimally schedule sensors' activities in order to extend WSNs lifetime. -In \cite{chin2007}, the author 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 1-hop neighbor -information, and each sensor decides its status (active or sleep) -based on the perimeter coverage model proposed in +In \cite{chin2007}, the author 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 1-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}. More recently, Shibo et al. \cite{Shibo} 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. -% TO BE CONTINUED Distributed Energy- Efficient - -The works presented in \cite{Bang, Zhixin, Zhang} focuses on a Coverage-Aware, Distributed Energy- Efficient and distributed clustering methods respectively, which aims to extend the network lifetime, while the coverage is ensured. - -S. Misra et al. \cite{Misra} proposed a localized algorithm for -coverage in sensor networks. The algorithm conserve the energy while -ensuring the network coverage by activating the subset of sensors, -with the minimum overlap area.The proposed method preserves the -network connectivity by formation of the network backbone. - -J. A. Torkestani \cite{Torkestani} proposed a learning automata-based -energy-efficient coverage protocol named as LAEEC to construct the -degree-constrained connected dominating set (DCDS) in WSNs. He shows -that the correct choice of the degree-constraint of DCDS balances the -network load on the active nodes and leads to enhance the coverage and -network lifetime. +Greedy Algorithm (DTGA) to solve it. They take in particular advantage +from both temporal and spatial correlations between data sensed by +different sensors. + +The works presented in \cite{Bang, Zhixin, Zhang} focus on the +definition of coverage-aware, distributed energy-efficient and +distributed clustering methods respectively. They aim to extend the +network lifetime while ensuring the coverage. S. Misra et al. +\cite{Misra05} proposed a localized algorithm which conserves energy and +coverage by activating the subset of sensors with the minimum +overlapping area. It preserves the network connectivity thanks to the +formation of the network backbone. J.~A.~Torkestani \cite{Torkestani} +designed a Learning Automata-based Energy-Efficient Coverage protocol +(LAEEC) to construct a Degree-constrained Connected Dominating Set +(DCDS) in WSNs. He showed that the correct choice of the +degree-constraint of DCDS balances the network load on the active +nodes and leads to enhance the coverage and network lifetime. The main contribution of our approach addresses three main questions -to build a scheduling strategy: +to build a scheduling strategy.\\ %\begin{itemize} %\item -{\bf How must the phases for information exchange, decision and - sensing be planned over time?} Our algorithm divides the time line - into a number of rounds. Each round contains 4 phases: Information - Exchange, Leader Election, Decision, and Sensing. +{\indent \bf How must the phases for information exchange, decision + and sensing be planned over time?} Our algorithm divides the timeline into rounds. Each round contains 4 phases: Information Exchange, +Leader Election, Decision, and Sensing. %\item {\bf What are the rules to decide which node has to be turned on @@ -187,15 +209,13 @@ to build a scheduling strategy: objectives. %\item -{\bf Which node should make such a decision?} The leader should make such a decision. Our - work does not consider only one leader to compute and to broadcast - the scheduling decision to all the sensors. When the network size - increases, the network is divided into many subregions and the - decision is made by a leader in each subregion. +{\bf Which node should make such a decision?} A leader node should +make such a decision. Our work does not consider only one leader to +compute and to broadcast the scheduling decision to all the sensors. +When the network size increases, the network is divided into many +subregions and the decision is made by a leader in each subregion. %\end{itemize} - - \section{Activity scheduling} \label{pd} @@ -212,8 +232,6 @@ then our coverage protocol will be implemented in each subregion simultaneously. Our protocol works in rounds fashion as shown in figure~\ref{fig1}. - - \begin{figure}[ht!] \centering \includegraphics[width=85mm]{FirstModel.eps} % 70mm @@ -357,7 +375,7 @@ $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $. %\includegraphics[scale=0.10]{fig26.pdf}\\~ ~ ~(e) %\includegraphics[scale=0.10]{fig27.pdf}\\~ ~ ~(f) %\end{multicols} -\caption{Wireless sensor node represented by 13 primary points} +\caption{Sensor node represented by 13 primary points} \label{fig2} \end{figure} @@ -420,7 +438,7 @@ U_{p} = \left \{ \label{eq14} \end{equation} -\noindent Our coverage optimization problem can then be formulated as follows +\noindent Our coverage optimization problem can then be formulated as follows\\ \begin{equation} \label{eq:ip2r} \left \{ \begin{array}{ll} @@ -436,9 +454,6 @@ X_{j} \in \{0,1\}, &\forall j \in J \end{array} \right. \end{equation} - - - \begin{itemize} \item $X_{j}$ : indicates whether or not the sensor $j$ is actively sensing in the round (1 if yes and 0 if not); @@ -459,7 +474,6 @@ weights $w_\theta$ and $w_U$ must be properly chosen so as to guarantee that the maximum number of points are covered during each round. - \section{Simulation results} \label{exp} @@ -566,7 +580,7 @@ that even if a network is disconnected in one subregion, the other one usually continues the optimization process, and this extends the lifetime of the network. -\subsection{The impact of the number of rounds on the energy saving ratio} +\subsection{Impact of the number of rounds on the energy saving ratio} In this experiment, we consider a performance metric linked to energy. This metric, called Energy Saving Ratio (ESR), is defined by: @@ -673,7 +687,7 @@ nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required. \begin{table}[ht] -\caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS} +\caption{EXECUTION TIME(S) VS. NUMBER OF SENSORS} % title of Table \centering @@ -711,12 +725,12 @@ Sensors number & Strategy~2 & Strategy~1 & Simple heuristic \\ [0.5ex] Finally, we have defined the network lifetime as the time until all nodes have been drained of their energy or each sensor network -monitoring an area has become disconnected. In figure~\ref{fig8}, the +monitoring an area has become disconnected. In figure~\ref{fig8}, the network lifetime for different network sizes and for both strategy -with two leaders and the simple heuristic is illustrated. - We do not consider anymore the centralized strategy with one - leader, because, as shown above, this strategy results in execution - times that quickly become unsuitable for a sensor network. +with two leaders and the simple heuristic is illustrated. We do not +consider anymore the centralized strategy with one leader, because, as +shown above, this strategy results in execution times that quickly +become unsuitable for a sensor network. \begin{figure}[h!] %\centering @@ -728,50 +742,48 @@ with two leaders and the simple heuristic is illustrated. \end{figure} As highlighted by figure~\ref{fig8}, the network lifetime obviously -increases when the size of the network increases, with our approach -that leads to the larger lifetime improvement. By choosing the best -suited nodes, for each round, to cover the region of interest and by +increases when the size of the network increases, with our approach +that leads to the larger lifetime improvement. By choosing the best +suited nodes, for each round, to cover the region of interest and by letting the other ones sleep in order to be used later in next rounds, -our strategy efficiently prolonges the network lifetime. Comparison shows that -the larger the sensor number is, the more our strategies outperform -the simple heuristic. Strategy~2, which uses two leaders, is the best -one because it is robust to network disconnection in one subregion. It -also means that distributing the algorithm in each node and -subdividing the sensing field into many subregions, which are managed -independently and simultaneously, is the most relevant way to maximize -the lifetime of a network. - -\section{Conclusion and future works} +our strategy efficiently prolonges the network lifetime. Comparison +shows that the larger the sensor number is, the more our strategies +outperform the simple heuristic. Strategy~2, which uses two leaders, +is the best one because it is robust to network disconnection in one +subregion. It also means that distributing the algorithm in each node +and subdividing the sensing field into many subregions, which are +managed independently and simultaneously, is the most relevant way to +maximize the lifetime of a network. + +\section{Conclusion and future work} \label{sec:conclusion} -In this paper, we have addressed the problem of the coverage and the lifetime -optimization in WSNs. To cope with this problem, the field of sensing -is divided into smaller subregions using the concept of +In this paper, we have addressed the problem of the coverage and the +lifetime optimization in WSNs. To cope with this problem, the field of +sensing is divided into smaller subregions using the concept of divide-and-conquer method, and then a multi-rounds coverage protocol will optimize coverage and lifetime performances in each subregion. -The simulations show the relevance of the proposed -protocol in terms of lifetime, coverage ratio, active sensors ratio, -energy saving, energy consumption, execution time, and the number of -stopped simulation runs due to network disconnection. Indeed, when -dealing with large and dense wireless sensor networks, a distributed -approach like the one we propose allows to reduce the difficulty of a -single global optimization problem by partitioning it in many smaller -problems, one per subregion, that can be solved more easily. - -In future work, we plan to study and propose a coverage protocol, which -computes all active sensor schedules in one time, using -optimization methods such as swarms optimization or evolutionary -algorithms. +The proposed protocol 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 representative active nodes. Results from simulations show +the relevance of the proposed protocol in terms of lifetime, coverage +ratio, active sensors ratio, energy saving, energy consumption, +execution time, and the number of stopped simulation runs due to +network disconnection. Indeed, when dealing with large and dense +wireless sensor networks, a distributed approach like the one we +propose allows to reduce the difficulty of a single global +optimization problem by partitioning it in many smaller problems, one +per subregion, that can be solved more easily. In future work, we +plan to study a coverage protocol which computes all active sensor +schedules in only one step for many rounds, using optimization methods +such as swarms optimization or evolutionary algorithms. % use section* for acknowledgement %\section*{Acknowledgment} - - - \bibliographystyle{IEEEtran} \bibliography{bare_conf} - \end{document}