\documentclass[11pt,twoside]{article}\makeatletter \IfFileExists{xcolor.sty}% {\RequirePackage{xcolor}}% {\RequirePackage{color}} \usepackage{colortbl} \usepackage{wrapfig} \usepackage{ifxetex} \ifxetex \usepackage{fontspec} \usepackage{xunicode} \catcode`⃥=\active \def⃥{\textbackslash} \catcode`❴=\active \def❴{\{} \catcode`❵=\active \def❵{\}} \def\textJapanese{\fontspec{Noto Sans CJK JP}} \def\textChinese{\fontspec{Noto Sans CJK SC}} \def\textKorean{\fontspec{Noto Sans CJK KR}} \setmonofont{DejaVu Sans Mono} \else \IfFileExists{utf8x.def}% {\usepackage[utf8x]{inputenc} \PrerenderUnicode{–} }% {\usepackage[utf8]{inputenc}} \usepackage[english]{babel} \usepackage[T1]{fontenc} \usepackage{float} \usepackage[]{ucs} \uc@dclc{8421}{default}{\textbackslash } \uc@dclc{10100}{default}{\{} \uc@dclc{10101}{default}{\}} \uc@dclc{8491}{default}{\AA{}} \uc@dclc{8239}{default}{\,} \uc@dclc{20154}{default}{ } \uc@dclc{10148}{default}{>} \def\textschwa{\rotatebox{-90}{e}} \def\textJapanese{} \def\textChinese{} \IfFileExists{tipa.sty}{\usepackage{tipa}}{} \fi \def\exampleFont{\ttfamily\small} \DeclareTextSymbol{\textpi}{OML}{25} \usepackage{relsize} \RequirePackage{array} \def\@testpach{\@chclass \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else \ifnum \@lastchclass=7 5 \else \ifnum \@lastchclass=8 \tw@ \else \ifnum \@lastchclass=9 \thr@@ \else \z@ \ifnum \@lastchclass = 10 \else \edef\@nextchar{\expandafter\string\@nextchar}% \@chnum \if \@nextchar c\z@ \else \if \@nextchar l\@ne \else \if \@nextchar r\tw@ \else \z@ \@chclass \if\@nextchar |\@ne \else \if \@nextchar !6 \else \if \@nextchar @7 \else \if \@nextchar (8 \else \if \@nextchar )9 \else 10 \@chnum \if \@nextchar m\thr@@\else \if \@nextchar p4 \else \if \@nextchar b5 \else \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi \fi} \gdef\arraybackslash{\let\\=\@arraycr} \def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}} \def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}} \def\abbr{} \def\corr{} \def\expan{} \def\gap{} \def\orig{} \def\reg{} \def\ref{} \def\sic{} \def\persName{}\def\name{} \def\placeName{} \def\orgName{} \def\textcal#1{{\fontspec{Lucida Calligraphy}#1}} \def\textgothic#1{{\fontspec{Lucida Blackletter}#1}} \def\textlarge#1{{\large #1}} \def\textoverbar#1{\ensuremath{\overline{#1}}} \def\textquoted#1{‘#1’} \def\textsmall#1{{\small #1}} \def\textsubscript#1{\@textsubscript{\selectfont#1}} \def\textxi{\ensuremath{\xi}} \def\titlem{\itshape} \newenvironment{biblfree}{}{\ifvmode\par\fi } \newenvironment{bibl}{}{} \newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par } \newenvironment{citbibl}{}{\ifvmode\par\fi } \newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi } \newenvironment{docDate}{}{\ifvmode\par\fi } \newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi } \newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par } \newenvironment{msHead}{\vskip 6pt}{\par} \newenvironment{msItem}{\vskip 6pt}{\par} \newenvironment{rubric}{}{} \newenvironment{titlePart}{}{\par } \newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}} \newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}} \newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}} \newcolumntype{P}[1]{){\arraybackslash}p{#1}} \newcolumntype{B}[1]{){\arraybackslash}b{#1}} \newcolumntype{M}[1]{){\arraybackslash}m{#1}} \definecolor{label}{gray}{0.75} \def\unusedattribute#1{\sout{\textcolor{label}{#1}}} \DeclareRobustCommand*{\xref}{\hyper@normalise\xref@} \def\xref@#1#2{\hyper@linkurl{#2}{#1}} \begingroup \catcode`\_=\active \gdef_#1{\ensuremath{\sb{\mathrm{#1}}}} \endgroup \mathcode`\_=\string"8000 \catcode`\_=12\relax \usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry} \usepackage{framed} \definecolor{shadecolor}{gray}{0.95} \usepackage{longtable} \usepackage[normalem]{ulem} \usepackage{fancyvrb} \usepackage{fancyhdr} \usepackage{graphicx} \usepackage{marginnote} \renewcommand{\@cite}[1]{#1} \renewcommand*{\marginfont}{\itshape\footnotesize} \def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif} \pagestyle{fancy} \usepackage[pdftitle={Path-Constrained Data Gathering Scheme}, pdfauthor={}]{hyperref} \hyperbaseurl{} \paperwidth210mm \paperheight297mm \def\@pnumwidth{1.55em} \def\@tocrmarg {2.55em} \def\@dotsep{4.5} \setcounter{tocdepth}{3} \clubpenalty=8000 \emergencystretch 3em \hbadness=4000 \hyphenpenalty=400 \pretolerance=750 \tolerance=2000 \vbadness=4000 \widowpenalty=10000 \renewcommand\section{\@startsection {section}{1}{\z@}% {-1.75ex \@plus -0.5ex \@minus -.2ex}% {0.5ex \@plus .2ex}% {\reset@font\Large\bfseries}} \renewcommand\subsection{\@startsection{subsection}{2}{\z@}% {-1.75ex\@plus -0.5ex \@minus- .2ex}% {0.5ex \@plus .2ex}% {\reset@font\Large}} \renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% {-1.5ex\@plus -0.35ex \@minus -.2ex}% {0.5ex \@plus .2ex}% {\reset@font\large}} \renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% {-1ex \@plus-0.35ex \@minus -0.2ex}% {0.5ex \@plus .2ex}% {\reset@font\normalsize}} \renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}% {1.5ex \@plus1ex \@minus .2ex}% {-1em}% {\reset@font\normalsize\bfseries}} \def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt} \@tempdima 1.5em \begingroup \parindent \z@ \rightskip \@pnumwidth \parfillskip -\@pnumwidth \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par \endgroup} \def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}} \def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}} \def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}} \def\l@subparagraph{\@dottedtocline{5}{10em}{5em}} \@ifundefined{c@section}{\newcounter{section}}{} \@ifundefined{c@chapter}{\newcounter{chapter}}{} \newif\if@mainmatter \@mainmattertrue \def\chaptername{Chapter} \def\frontmatter{% \pagenumbering{roman} \def\thechapter{\@roman\c@chapter} \def\theHchapter{\roman{chapter}} \def\thesection{\@roman\c@section} \def\theHsection{\roman{section}} \def\@chapapp{}% } \def\mainmatter{% \cleardoublepage \def\thechapter{\@arabic\c@chapter} \setcounter{chapter}{0} \setcounter{section}{0} \pagenumbering{arabic} \setcounter{secnumdepth}{6} \def\@chapapp{\chaptername}% \def\theHchapter{\arabic{chapter}} \def\thesection{\@arabic\c@section} \def\theHsection{\arabic{section}} } \def\backmatter{% \cleardoublepage \setcounter{chapter}{0} \setcounter{section}{0} \setcounter{secnumdepth}{2} \def\@chapapp{\appendixname}% \def\thechapter{\@Alph\c@chapter} \def\theHchapter{\Alph{chapter}} \appendix } \newenvironment{bibitemlist}[1]{% \list{\@biblabel{\@arabic\c@enumiv}}% {\settowidth\labelwidth{\@biblabel{#1}}% \leftmargin\labelwidth \advance\leftmargin\labelsep \@openbib@code \usecounter{enumiv}% \let\p@enumiv\@empty \renewcommand\theenumiv{\@arabic\c@enumiv}% }% \sloppy \clubpenalty4000 \@clubpenalty \clubpenalty \widowpenalty4000% \sfcode`\.\@m}% {\def\@noitemerr {\@latex@warning{Empty `bibitemlist' environment}}% \endlist} \def\tableofcontents{\section*{\contentsname}\@starttoc{toc}} \parskip0pt \parindent1em \def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}} \newenvironment{reflist}{% \begin{raggedright}\begin{list}{} {% \setlength{\topsep}{0pt}% \setlength{\rightmargin}{0.25in}% \setlength{\itemsep}{0pt}% \setlength{\itemindent}{0pt}% \setlength{\parskip}{0pt}% \setlength{\parsep}{2pt}% \def\makelabel##1{\itshape ##1}}% } {\end{list}\end{raggedright}} \newenvironment{sansreflist}{% \begin{raggedright}\begin{list}{} {% \setlength{\topsep}{0pt}% \setlength{\rightmargin}{0.25in}% \setlength{\itemindent}{0pt}% \setlength{\parskip}{0pt}% \setlength{\itemsep}{0pt}% \setlength{\parsep}{2pt}% \def\makelabel##1{\upshape ##1}}% } {\end{list}\end{raggedright}} \newenvironment{specHead}[2]% {\vspace{20pt}\hrule\vspace{10pt}% \phantomsection\label{#1}\markright{#2}% \pdfbookmark[2]{#2}{#1}% \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}% }{} \def\TheFullDate{2013-01-15 (revised: 15 January 2013)} \def\TheID{\makeatother } \def\TheDate{2013-01-15} \title{Path-Constrained Data Gathering Scheme} \author{}\makeatletter \makeatletter \newcommand*{\cleartoleftpage}{% \clearpage \if@twoside \ifodd\c@page \hbox{}\newpage \if@twocolumn \hbox{}\newpage \fi \fi \fi } \makeatother \makeatletter \thispagestyle{empty} \markright{\@title}\markboth{\@title}{\@author} \renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@ \belowdisplayskip \abovedisplayskip \abovedisplayshortskip \z@ plus2\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def\@listi{\leftmargin\leftmargini \topsep 2\p@ plus1\p@ minus1\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep 1pt} } \makeatother \fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm} \fancyhf{} \setlength{\headheight}{14pt} \fancyhead[LE]{\bfseries\leftmark} \fancyhead[RO]{\bfseries\rightmark} \fancyfoot[RO]{} \fancyfoot[CO]{\thepage} \fancyfoot[LO]{\TheID} \fancyfoot[LE]{} \fancyfoot[CE]{\thepage} \fancyfoot[RE]{\TheID} \hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true} \fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}} \date{} \usepackage{authblk} \providecommand{\keywords}[1] { \footnotesize \textbf{\textit{Index terms---}} #1 } \usepackage{graphicx,xcolor} \definecolor{GJBlue}{HTML}{273B81} \definecolor{GJLightBlue}{HTML}{0A9DD9} \definecolor{GJMediumGrey}{HTML}{6D6E70} \definecolor{GJLightGrey}{HTML}{929497} \renewenvironment{abstract}{% \setlength{\parindent}{0pt}\raggedright \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}} \vskip16pt \textcolor{GJBlue}{\large\bfseries\abstractname\space} }{% \vskip8pt \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}} \vskip16pt } \usepackage[absolute,overlay]{textpos} \makeatother \usepackage{lineno} \linenumbers \begin{document} \author[1]{Khaled Almiani} \author[2]{Mohammed A. Abuhelaleh} \author[3]{Bassam A. Alqaralleh} \affil[1]{ Al-hussein Bin Talal University} \renewcommand\Authands{ and } \date{\small \em Received: 11 December 2012 Accepted: 4 January 2013 Published: 15 January 2013} \maketitle \begin{abstract} Several studies in recent years have considered the use of mobile elements for data gathering in wireless sensor networks, so as to reduce the need for multi-hop forwarding among the sensor nodes and thereby prolong the network lifetime. Since, typically, practical constraints preclude a mobile element from visiting all nodes in the sensor network, the solution must involve a combination of a mobile element visiting a subset of the nodes (cache points), while other nodes communicate their data to the cache points wirelessly. This leads to the optimization problem of minimizing the communication distance of the sensor nodes, while keeping the tour length of the mobile element below a given constraint. In this paper, we investigate the problem of designing the mobile elements tours such that the length of each tour is below a per-determined length and the number of hops between the tours and the nodes not included in the tour is minimized. To address this problem, we present an algorithmic solution that consider the distribution of the nodes during the process of building the tours. We compare the resulting performance of our algorithm with the best known comparable schemes in the literature. \end{abstract} \keywords{} \begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) \textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark} \end{textblock*} \begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) \textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}} \end{textblock*} \let\tabcellsep& \section[{Introduction}]{Introduction}\par any typical applications of wireless sensor networks (WSNs) involve the collection of data obtained by sensor nodes at a pre-defined sink. This is normally achieved by wireless transmission of the data, possibly over several hops (especially in applications where the sensors are deployed in a hostile or hard-to-access environment). In many cases, the wireless communication results in a major energy expenditure that limits the operational lifetime of the network. Even worse, in multi-hop scenarios, the depletion of the sensors' energy sources (such as batteries) is non-uniform, as nodes that are close to the sink are required to forward all the data traffic and are likely to be the first to run out of energy. Once these sensors fail, other nodes can no longer reach the sink, and the network ceases to operate even though ample energy remains at nodes further away from the sink. This common problem occurs largely independently of the communication protocols used in the network.\par In general, the use of Mobile Elements (MEs) \hyperref[b0]{[1]}, \hyperref[b1]{[2]}, \hyperref[b2]{[3]} can significantly increases the lifetime of the network. Mobile element roams in the network and collects data from sensors via short range communication, the energy cost of which is considerably lower. Thus, the lifetime of the network increases by avoiding multi-hop communication. The main drawback for this approach is the increased latency of the data collection. Typically, the speed of mobile element can be about 0:1-2 m/s \hyperref[b3]{[4]}, \hyperref[b4]{[5]}, resulting in substantial traveling time for the ME and, correspondingly, delay in gathering the sensors' data. In practice, often the ME tour length is bounded by a predetermined time deadline, either due to timeliness constraints on the sensor data or a limit on the amount of energy available to the ME itself. A possible solution is to employ more than one ME; however, this solution is often impractical due to the high cost of MEs, and may not in fact help at all if some sensors are beyond reach due to ME battery limitations in the first place.\par To address this problem, several proposals presented a hybrid approach, which combines multihop forwarding with the use of mobile elements. In this approach, mobile element visits subset of the nodes termed as caching points. These caching points stores the data of the nodes that are not included in the tour of the mobile element. Once a mobile element become within the transmission range of a caching point, the caching point transmit its data to the mobile element. By adopting such an approach, the mobile element gather the data of the entire without the need of visiting each node physically. In this direction, we investigate the problem of designing the tours for the mobile elements and the data forwarding trees, with the objective of minimizing the distance between nodes not included in the tour and the tour itself. We propose a heuristicbased solution that creates its solution by partition the network into clusters. The in each cluster a tour will be constructed to satisfy the objective. The results show that our scheme significantly outperforms the best comparable scheme in the literature.\par The rest of the paper is organized as follows. Section 2 presents the related work in this research area. Section 3 presents the Problem definition. In Section 4, we present the details of our algorithmic solution. Section 5 presents the evaluation. Finally, Section 6 concludes the paper. \section[{II.}]{II.} \section[{Related Work}]{Related Work}\par There have been many proposals in recent literature that studied using mobile element(s) to prolong the lifetime of the network. Based on the categorization given in \hyperref[b2]{[3]}, we review three major approaches. In a typical flat-topology network, the nodes around the sink are likely to be the first to die due to having to forward the data traffic from all other sensors. Based on this observation, several proposals \hyperref[b5]{[6]}, \hyperref[b6]{[7]} have investigated using mobile sink(s) to reduce the energy consumption in the network. By varying the path to the sink(s), the residual energy in the nodes becomes more evenly balanced throughout the network, leading to a higher network's lifetime. However, in order to be effective, this technique requires the sink location (and routes thereto) to change regularly, which places a potentially prohibitive overhead on the nodes due to the frequent re-computation of the routes. Zhao et al \hyperref[b8]{[8]}, \hyperref[b9]{[9]} investigated the problem of maximizing the overall network utility. Accordingly, they presented two distributed algorithms for data gathering where the mobile sink stays at each anchor point (gathering point) for a period of sojourn time and collects data from nearby sensors via multi-hop communications. They considered the cases where the sojourn time is fixed as well as variable.\par In the second approach, mobile elements travel across the network and gather each sensors data via single-hop, short-range communication. In this scenario, the problem of computing the ME tours is exactly the Traveling Salesman Problem (TSP) \hyperref[b10]{[10]}, with the possibility of adding additional constraints to capture the limitations of the nodes buffer size. In \hyperref[b11]{[11]}, \hyperref[b12]{[12]}, \hyperref[b13]{[13]}, \hyperref[b14]{[14]}, \hyperref[b15]{[15]} several heuristics have been proposed to that effect, so that each sensor is visited before its buffer is full. Although this approach substantially reduces the energy consumption by avoiding multi-hop communications, it incurs a high delay when the network area is large, because of the requirement that the MEs physically visit all sensor nodes.\par Finally, the third approach is a hybrid that combines multihop forwarding with data collection by mobile elements. Our work falls into this category. Some earlier works, e.g. \hyperref[b16]{[16]}, \hyperref[b17]{[17]}, \hyperref[b19]{[18]}, assumed the mobile route to be predetermined and were mainly concerned with the timing of transmissions, aiming to minimize the need for in-network caching by timing the transmissions to coincide with the passing of the tour. In \hyperref[b20]{[19]}, \hyperref[b22]{[20]}, the minimum-energy Rendezvous Planning Problem (RPP) is introduced. This problem deals with determining the set of rendezvous points constructing the ME tour. In RPP, the goal is to minimize the Euclidean distance between the source nodes and the tour. Path finding algorithms based on maxflow computations have been considered by \hyperref[b24]{[21]}. In that work, the authors use a standard maxflow formulation to represent the sensor network. However the problem they consider is finding a path through anywhere in the network area, which does not need to move from a sensor location to another sensor location.\par Xu et al \hyperref[b25]{[22]} also proposed a tour finding algorithm in which nodes away from the caching points send their data to the caching points using multi-hop communication. The main concept of their algorithm is to find a tour that satisfies the transit constraint such that the depth of the routing trees connected to this tour are bounded by pre-determined variable h. this algorithm starts by setting the value of h to 1 and increasing it gradually, until such a tour is found. By bounding the depth of the routing tress, the algorithm aims to reduce the energy consumption due to multi-hop forwarding. However, important factors in determining the lifetime of the network such as structure of routing tress, the energy level of the nodes, and the distribution of the caching points were not mainly considered in this algorithm. Liang et al \hyperref[b26]{[23]} investigated similar problem where the depth of the routing trees were bounded by pre-determined variable. The problem presented in this work shares some similarities with the Vehicle Routing Problem (VRP) \hyperref[b27]{[24]}. Given a fleet of vehicles assigned to a depot, VRP deals with determining the fleet routes to deliver goods from a depot to customers while minimizing the vehicles' total travel cost. \section[{III.}]{III.} \section[{Problem Definition}]{Problem Definition}\par We are given an undirected graph G = (V, E), where V is the set of vertices representing the locations of the sensors in the network, and E is the set of edges that represents the communication network topology, i.e. (v i , v j ) ? E if and only if v i and v j are within each others communication range. In addition, we are given k, that represents the number of tours need to be constructed. The complete graph G' = (V, E'), where E' = V × V, represents the possible movements of the mobile elements. Each edge (v i , v j ) ? E' has a length r ij , which represents the time needed by a mobile element to travel between sensor v i and v j . The data of all sensors must be uploaded to a mobile element periodically at least once in L time units, where L is determined from the application requirements and the sensors buffer size. In other words, we assume that each mobile element conducts its tour periodically, with L being a constraint on the maximum tour length. In this paper, for simplicity, we assume that the mobile element travels at constant speed, and that, therefore, the travelling times between sensors (r ij ) correspond directly to their respective Euclidean distances; however, this assumption is not essential to our algorithms and can be easily dropped if necessary.\par In our problem, we seek to find the k tours, where the length of the tour is bounded by L, such that the number of hops between any node and its caching point is minimized.\par IV. \section[{TOURS AND FORWARDING TREES}]{TOURS AND FORWARDING TREES}\par The goal of our algorithm is to find the tours for the given k mobile elements such that distance between the nodes not included in the tours and the tours are Year minimized. In this direction, we first partition the network into k partitions. The underling goal for the partitioning processes is to minimize the distance between nodes belong to the same cluster. By adopting such a process, we aim to minimize the distance between the nodes and the tours in each cluster. Once the clusters are constructed, the tour building step works to create a tour in each cluster with the aim of minimizing the total distance of the routing trees. \section[{a) Clustering Step}]{a) Clustering Step}\par The clustering step attempts to find a given number of clusters such that the sum of hop-distances among nodes belonging to the same cluster is minimized. The clustering process start by selecting a node randomly as a cluster centroid. Once a centroid node is identified it will be added to list termed R. Then, the process works by identifying k-1 cluster centroids, where in each iteration, a node is identify as centroid if it has the maximum total hop-distance to all nodes stored in R. Once all k clusters are identified, each node not chosen Figure {\ref 1} : The clustering step a centroid will be assign to its nearest cluster centroid. By adopting such a mechanism, we aim to direct the partitioning to group the nodes into clusters based on their distribution. Figure {\ref 1} outlines the process of this step. \section[{b) Caching point identification step}]{b) Caching point identification step}\par Now, in each cluster subset of nodes will be selected as caching points. These caching points will store the other nodes data and will be used to construct the mobile element tour. In each cluster, this process works by first identifying the center node. The center node is defined as the node that has the minimum total hop-distance to all other nodes in the cluster. Then, it works to constructs Minimum Spanning Tree (MST) rooted at the cluster center node. Once this MST is constructed the process proceeds to traverse the constructed tree using BST mechanism. This traversing stops once the total distance of the visited edges reach (L. 2/3). As we will see in the tours constructing step, this condition depends on the employed TSP algorithm. The last step in this process is to identify the visited nodes in the traversing mechanism as caching points. \section[{c) Constructing the tour}]{c) Constructing the tour}\par The tour construction phase uses the nodes identified as caching points in the previous step and can be based on any TSP algorithm or heuristic. We use the Christofides approximation algorithm here, as it is known algorithm with 2/3 approximation factor. \section[{V.}]{V.} \section[{Experimental Evaluation}]{Experimental Evaluation}\par To evaluate the presented algorithm's performance, we conducted an extensive set of experiments using the J-sim simulator \hyperref[b28]{[25]}. We used the following parameters:\par (1) The area of the network is 250,000m 2 .\par (2) The tour length constraint L is set to 0:05 ? s ? T L , where s = 1 m/s is the speed of the mobile element, and T L is the total length of the edges in the minimum spanning tree that connects all nodes, for 500 nodes in the network. (3) The starting value of M is chosen to be 0:5 ? T H , where T H is the number of hops between the farthest nodes in the network. ( {\ref 4}) The radio parameters are set according to the MICAz data sheet \hyperref[b29]{[26]}, namely: the radio bandwidth is 250 Kbps, the transmission power is 21 mW, the receiving power is 15 mW, and the initial battery power is 10 Joules. For simplicity, we only account for the radio receiving and transmitting energy. We are particularly interested in investigating the performance of the presented algorithm in terms of the lifetime of the network and the total distance of the routing trees. We consider the following deployment scenarios: 1. Uniform density deployment: in this scenario, we assume that the nodes are uniformly deployed in a square area of 500×500m 2 . 2. Variable density deployment: in this scenario, we divide the network into a 10×10 grid of squares, Select the node with the maximum distance as new centroid 6\par Add the select node to R 7 Until k centroid is selected 8 assign each node to its nearest centroid 9 identify each centroid and the nodes assigned to it as a cluster where each square is 50×50m 2 . We randomly choose 30 of the squares, and in each one of those we fix the node density to be x times the density in the remaining squares. x is a density parameter, which in most experiments (unless mentioned otherwise) is set to x = 5.\par We compare our algorithm to a modified version of the FFT algorithm \hyperref[b30]{[27]}, we refer to this version as V-FFT. In the original FFT algorithm, a new node is added to the tour based on benefit function. The benefit value of each node depends on the distance between this node and the currently constructed tour as well as the number of nodes it covers. The number of nodes that are covered by any tour node is controlled by the parameter h ? 1. This parameter refers to the maximum number of hops allowed between any two nodes: a tour node can cover any node at most h hops away. Initially, h = 1 and in each round the value of h is incremented by one until a tour that satisfies the transit constraint is determined. In the modified version of the FFT algorithm (V-FFT), we h to be 0:5 the maximum distance between any two nodes inside any cluster obtained by our heuristic. Then, we start by constructing the first tour. Each selected caching point and the neighbor of this caching points, will be removed from consideration at later stage. This tour will be extended, based on the given cost function, until the constructing tour cannot be extended without violating the transit constraint. Once such a tour is obtained, a new tour will be constructed using the same mechanism.\par We evaluate the impact of the number of nodes on the lifetime of the network and the total size of the routing trees each algorithm obtains. Figure \hyperref[fig_2]{2}, Figure {\ref 3}, Figure {\ref 5} and Figure {\ref 5} show the results for deployment scenarios. In the uniform deployment scenario, we can see that increasing the number of nodes increases the gap between the algorithm performances. In this deployment scenario, since we deal with uniformly deployment scenario, the locality of each cluster obtained by the proposed algorithm is expected to be the same. Such behavior results in creating a relatively linear relationship between network lifetime and the number of node. This can be noticed in the results of the routing trees size experiments. In the V-FFT algorithm, the benefit function takes into account the number of nodes covered by the considered nodes as well as the distance between this node and the current constructed tour. And considering the number of covered-nodes as well as the stochastic behavior of such benefit function are the factor behind the seen performance.\par In the variable deployment scenario, we can see that increasing the number of nodes results in slightly reducing the gap between the algorithms performances. To understand this behavior, let us discuss the main mechanism behind each algorithm performance. In the proposed algorithm, the obtained clusters is expected to be centralized at the dense grids. This is expected to significantly reduce the lifetime of the network, since in each cluster the tour will be saturated with nodes very closed to each other. This become more obvious while increasing the number of tours. In the V-FFT algorithm, as we mentioned, the benefit function take into consideration the number of neighboring nodes covered by a node as well as the distance between the node and the current constructed tour. In this deployment scenario, considering the number of neighboring nodes during the construction of the tours is expected to improve the V-FFT performance, since it will avoid adding caching node that is very closed to the current constructed tour. These can mainly describe the seen performance. \section[{VI.}]{VI.} \section[{Conclusions}]{Conclusions}\par In this paper, we consider the problem of designing the mobile elements tours such that total size of the routing trees is minimized. In this work, we present an algorithmic solution that create its solution by partitioning the network, then in each clusters, a tour will be constructed based on the distribution of the nodes.\par An interesting open problem would be to consider application scenarios where the data gathering latency requirements vary in the network. For example, some areas in the network need to send data more frequently than others. In this case the tour length constraints would be different for different areas. \begin{figure}[htbp] \noindent\textbf{}\includegraphics[]{image-2.png} \caption{\label{fig_1}©}\end{figure} \begin{figure}[htbp] \noindent\textbf{2}\includegraphics[]{image-3.png} \caption{\label{fig_2}2 E}\end{figure} \begin{figure}[htbp] \noindent\textbf{2}\includegraphics[]{image-4.png} \caption{\label{fig_3}Figure 2 :}\end{figure} \begin{figure}[htbp] \noindent\textbf{345}\includegraphics[]{image-5.png} \caption{\label{fig_4}Figure 3 :Figure 4 :Figure 5 :}\end{figure} \footnote{EPath-Constrained Data Gathering Scheme} \footnote{© 2013 Global Journals Inc. (US)} \footnote{EPath-Constrained Data Gathering Scheme} \footnote{EPath-Constrained Data Gathering Scheme} \backmatter \subsection[{Data Collection in Wireless Sensor Networks with}]{Data Collection in Wireless Sensor Networks with}\par Dynamic Deadlines," in Real-Time Systems Symposium, 2004. Proceedings. 25th IEEE International. IEEE Press, 2004, pp. 296-305. \begin{bibitemlist}{1} \bibitem[]{b7}\label{b7} \textit{}, \xref{http://dx.doi.org/10.1109/HICSS.2005.259}{10.1109/HICSS.2005.259}. \url{http://doi.ieeecomputersociety.org/10.1109/HICSS.2005.259} \bibitem[Available]{b18}\label{b18} \url{http://www.comp.nus.edu.sg/?tayyc/6282/forPresentation/SensorNet.pdf} \textit{Available}, \bibitem[Available]{b21}\label{b21} \url{http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4492781} \textit{Available}, \bibitem[Available]{b23}\label{b23} \url{http://portal.acm.org/citation.cfm?id=1374650} \textit{Available}, \bibitem[Somasundara et al. ()]{b16}\label{b16} ‘Controllably mobile infrastructure for low energy embedded networks’. A Somasundara , A Kansal , D Jea , D Estrin , M Srivastava . \textit{IEEE Transactions on Mobile Computing} 2006. 5 (8) p. . \bibitem[Ma and Yang (2008)]{b15}\label{b15} ‘Data gathering in wireless sensor networks with mobile collectors’. M Ma , Y Yang . \url{http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4536269} \textit{2008 IEEE International Symposium on Parallel and Distributed Processing}, Apr. 2008. p. . \bibitem[Shah et al. ()]{b17}\label{b17} ‘Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks’. R Shah , S Roy , S Jain , W Brunette . \textit{Proceedings of the First IEEE Workshop on Sensor Network Protocols and Applications}, (the First IEEE Workshop on Sensor Network Protocols and Applications) 2003. p. . \bibitem[Efficient data gathering with mobile collectors and space-division multiple access technique in wireless sensor networks IEEE Transactions on Computers ()]{b9}\label{b9} ‘Efficient data gathering with mobile collectors and space-division multiple access technique in wireless sensor networks’. \textit{IEEE Transactions on Computers} 2011. 60 (3) p. . \bibitem[Gandham et al. ()]{b5}\label{b5} ‘Energy efficient schemes for wireless sensor networks with multiple mobile base stations’. S Gandham , M Dawande , R Prakash , S Venkatesan . \textit{Proceedings of IEEE Globecom}, (IEEE Globecom) 2003. IEEE. 1 p. . \bibitem[Wang et al. ()]{b6}\label{b6} ‘Exploiting sink mobility for maximizing sensor networks lifetime’. Z Wang , S Basagni , E Melachrinoudis , C Petrioli . \textit{Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS)}, (the 38th Annual Hawaii International Conference on System Sciences (HICSS)) 2005. 9 p. . \bibitem[Hou et al. ()]{b28}\label{b28} \textit{J-Sim: A Simulation and emulation environment for wireless sensor networks}, J Hou , L Kung , N Li , H Zhang , W Chen , H Tyan , H Lim . 2006. IEEE Wireless Communications Magazine. 13 p. . \bibitem[Lamarca et al. ()]{b1}\label{b1} \textit{Making sensor networks practical with robots}, A Lamarca , W Brunette , D Koizumi , M Lease , S Sigurdsson , K Sikorski , D Fox , G Borriello . \url{http://www.springerlink.com/index/9BUYG5K8BEW05CRX.pdf} 2002. p. . (Lecture notes in computer science) \bibitem[Hill and Culler ()]{b29}\label{b29} ‘Mica: A wireless platform for deeply embedded networks’. J Hill , D Culler . \textit{IEEE micro} 2002. 22 (6) p. . \bibitem[Somasundara et al.]{b12}\label{b12} \textit{Mobile Element Scheduling for Efficient}, A Somasundara , A Ramamoorthy , B Srivastava . \bibitem[Somasundara et al. ()]{b11}\label{b11} ‘Mobile element scheduling with dynamic deadlines’. A Somasundara , A Ramamoorthy , M Srivastava . \url{http://www.ece.iastate.edu/?adityar/adidocs/04116703.pdf} \textit{IEEE transactions on Mobile Computing} 2007. 6 (4) p. . \bibitem[Ekici et al. ()]{b2}\label{b2} ‘Mobility-based communication in wireless sensor networks’. E Ekici , Y Gu , D Bozdag . \textit{IEEE Communications Magazine} 2006. 44 (7) p. . \bibitem[Jea et al. ()]{b19}\label{b19} ‘Multiple controlled mobile elements (data mules) for data collection in sensor networks’. D Jea , A Somasundara , M Srivastava . \url{http://www.springerlink.com/index/4617cluarmakkx5x.pdf} Lecture Notes in Computer Science 2005. 3560 p. . \bibitem[Xu et al. ()]{b25}\label{b25} ‘Network Lifetime Maximization in Delay-Tolerant Sensor Networks With a Mobile Sink’. Z Xu , W Liang , Y Xu . \textit{Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems}, (the 8th IEEE International Conference on Distributed Computing in Sensor Systems) 2012. p. . \bibitem[Xu et al. ()]{b30}\label{b30} ‘Network Lifetime Maximization in Delay-Tolerant Sensor Networks With a Mobile Sink’. Z Xu , W Liang , Y Xu . \textit{Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems}, (the 8th IEEE International Conference on Distributed Computing in Sensor Systems) 2012. p. . \bibitem[Liang and Luo]{b26}\label{b26} ‘Network Lifetime Maximization in Sensor Networks with Multiple Mobile Sinks’. W Liang , J Luo . \textit{Proceedings of the 36 th IEEE Conference on Local Computer Networks (LCN)}, (the 36 th IEEE Conference on Local Computer Networks (LCN)) \bibitem[Pon et al. ()]{b4}\label{b4} ‘Networked infomechanical systems: a mobile embedded networked sensor platform’. R Pon , M Batalin , J Gordon , A Kansal , D Liu , M Rahimi , L Shirachi , Y Yu , M Hansen , W Kaiser , Others . \url{http://portal.acm.org/citation.cfm?id=1147685.1147746} \textit{Proceedings of the 4th international symposium on Information processing in sensor networks}, (the 4th international symposium on Information processing in sensor networks) 2005. IEEE Press. p. . \bibitem[Zhao and Yang ()]{b8}\label{b8} ‘Optimization-Based Distributed Algorithms for Mobile Data Gathering in Wireless Sensor Networks’. M Zhao , Y Yang . \textit{IEEE Transactions on Mobile Computing} 2012. 11 (10) p. . \bibitem[Gu et al. ()]{b13}\label{b13} ‘Partitioning based mobile element scheduling in wireless sensor networks’. Y Gu , D Bozdag , E Ekici , F Ozguner , C Lee . \textit{Sensor and Ad Hoc Communications and Networks, 2005. IEEE SECON 2005. 2005 Second Annual IEEE Communications Society Conference on}, 2005. p. . \bibitem[Almi'ani et al. ()]{b14}\label{b14} ‘Periodic Mobile Multi-Gateway Scheduling’. K Almi'ani , S Selvadurai , A Viglas . \textit{Proceedings of the Ninth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)}, (the Ninth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)) 2008. IEEE. p. . \bibitem[Xing et al. ()]{b22}\label{b22} ‘Rendezvous design algorithms for wireless sensor networks with a mobile base station’. G Xing , T Wang , W Jia , M Li . \textit{Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc)}, (the 9th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc)New York, NY, USA) 2008. ACM. p. . \bibitem[Xing et al. (2008)]{b20}\label{b20} ‘Rendezvous planning in wireless sensor networks with mobile elements’. G Xing , T Wang , Z Xie , W Jia . \textit{IEEE Transactions on Mobile Computing} Dec. 2008. 7 (12) p. . \bibitem[Dantu et al. ()]{b3}\label{b3} ‘Robomote: enabling mobility in sensor networks’. K Dantu , M Rahimi , H Shah , S Babel , A Dhariwal , G Sukhatme . \url{http://portal.acm.org/citation.cfm?id=1147685.1147751} \textit{Proceedings of the 4th international symposium on Information processing in sensor networks (IPSN)}, (the 4th international symposium on Information processing in sensor networks (IPSN)) 2005. IEEE Press. p. . \bibitem[Butler ()]{b0}\label{b0} ‘Robotics and Microelectronics: Mobile Robots as Gateways into Wireless Sensor Networks’. J Butler . \textit{Technology@Intel Magazine} 2003. \bibitem[Ma and Yang (2007)]{b24}\label{b24} ‘SenCar: An Energy-Efficient Data Gathering Mechanism for Large-Scale Multihop Sensor Networks’. M Ma , Y Yang . \url{http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4302733} \textit{IEEE Transactions on Parallel and Distributed Systems} Oct. 2007. 18 (10) p. . \bibitem[Toth and Vigo ()]{b27}\label{b27} ‘The Vehicle Routing Problem’. P Toth , D Vigo . \textit{Society for Industrial \& Applied Mathematics (SIAM)}, 2001. \bibitem[Christofides ()]{b10}\label{b10} \textit{Worst-case analysis of a new heuristic for the traveling salesman problem}, N Christofides . 1976. \end{bibitemlist} \end{document}