\hyphenation{op-tical net-works semi-conduc-tor}
-
\usepackage{etoolbox}
\usepackage{float}
\usepackage{epsfig}
\DeclareGraphicsExtensions{.ps}
\DeclareGraphicsRule{.ps}{pdf}{.pdf}{`ps2pdf -dEPSCrop -dNOSAFER #1 \noexpand\OutputFile}
-
\begin{document}
%
% paper title
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
\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}
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
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}
simultaneously. Our protocol works in rounds fashion as shown in
figure~\ref{fig1}.
-
-
\begin{figure}[ht!]
\centering
\includegraphics[width=85mm]{FirstModel.eps} % 70mm
%\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}
\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}
\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);
guarantee that the maximum number of points are covered during each
round.
-
\section{Simulation results}
\label{exp}
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:
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
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
\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}
