\documentclass[coll,linenumbers]{imsart}

\RequirePackage[OT1]{fontenc}
%\usepackage{natbib}
\usepackage{amsthm,amsmath,natbib}
\RequirePackage[colorlinks,citecolor=blue,urlcolor=blue]{hyperref}
\RequirePackage{hypernat}
\usepackage{epsfig, amsmath, amssymb, amscd, dsfont}
\usepackage{color, graphicx}
\usepackage{amsfonts,amsthm,fancybox}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{dcolumn}
%\usepackage{textcomp}
%\usepackage{colortbl}
\usepackage{url}
% settings
\pubyear{2009}
\volume{0}
%\volumetitle{IMS Collections}
\firstpage{333}
\lastpage{346}
\doi{0008/0000.0000}
\arxiv{math.PR/0000008}

%\newcommand{\inst}[1]{\unskip${^{#1}}$}

\newcommand{\inst}[1]{\unskip${^{#1}}$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\startlocaldefs
\def\myproof#1{\noindent\hspace{2em}{\it #1:}}
\def\endmyproof{\hspace*{\fill}~\QED\par\endtrivlist\unskip}
\newcommand{\ie}{\mbox{\it i.e.}}
\newcommand{\atal}{\mbox{\it et al.}}
\newcommand{\yb}{{\bf y}}
\newcommand{\bb}{{\bf b}}
\newcommand{\sbb}{{\bf s}}
\newcommand{\xb}{{\bf x}}
\newcommand{\eb}{{\bf e}}
\newcommand{\wb}{{\bf w}}
\newcommand{\zb}{{\bf z}}
\newcommand{\kb}{{\bf k}}
\newcommand{\tb}{{\bf t}}
\newcommand{\Tb}{{\bf T}}
\newcommand{\Ib}{{\bf I}}
\newcommand{\Ab}{{\bf A}}
\newcommand{\Bb}{{\bf B}}
\newcommand{\Rb}{{\bf R}}
\newcommand{\Mb}{{\bf M}}
\newcommand{\Nb}{{\bf N}}
\newcommand{\Ub}{{\bf U}}
\newcommand{\Ac}{{\cal A}}
\newcommand{\Bc}{{\cal B}}
\newcommand{\Dc}{{\cal D}}
\newcommand{\Fc}{{\cal F}}
\newcommand{\Gc}{{\cal G}}
\newcommand{\Hc}{{\cal H}}
\newcommand{\Rc}{{\cal R}}
\newcommand{\Pc}{{\cal P}}
\newcommand{\Sc}{{\cal S}}
\newcommand{\Qc}{{\cal Q}}
\newcommand{\Tc}{{\cal T}}
\newcommand{\Nc}{{\cal N}}
\newcommand{\Vc}{{\cal V}}
\newcommand{\Wc}{{\cal W}}
\newcommand{\cC}{{\cal C}}
\newcommand{\Uc}{{\cal U}}
\newcommand{\Xc}{{\cal X}}
\newcommand{\Yc}{{\cal Y}}
\newcommand{\Ei}{{\cal E}}
\newcommand{\Ic}{{\cal I}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\bijk}{b_{ij}^{(k)}}
\newcommand{\phib}{\boldsymbol{\varphi}}
\newcommand{\deltab}{\boldsymbol{\delta}}
\newcommand{\epsilonb}{\boldsymbol{\epsilon}}
\newcommand{\psib}{\boldsymbol{\psi}}
\newcommand{\alphab}{\boldsymbol{\alpha}}
\newcommand{\betab}{\boldsymbol{\beta}}
\newcommand{\tetab}{\boldsymbol{\theta}}
\newcommand{\Deltab}{\boldsymbol{\Delta}}
\newcommand{\lk}{\left\{ }
\newcommand{\rk}{ \right\} }
\newcommand{\rond}[1]{\frac{\partial}{\partial #1}}
\newcommand{\varrond}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\argmin}{\mathop{\rm argmin}}
\newtheorem{theorem}{Theorem}
\newtheorem{defi}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{property}{Property}
\newtheorem{coro}{Corollary}
\newcommand{\lmat}{\left(} % Left matrix
\newcommand{\rmat}{\right)}% Right matrix

% Hat Bold Symbols
\newcommand{\ybh}{{\bf \hat y}}
\newcommand{\xbh}{{\bf \hat x}}
\newcommand{\Bbh}{{\bf \hat B}}
\newcommand{\Rbh}{{\bf \hat R}}


%\setlength{\headsep}{8mm} \setlength{\topmargin}{-0.75in}
%\setlength{\textheight}{9.7in} \setlength{\textwidth}{6.7in}
%\setlength{\evensidemargin}{-0.20in}
%\setlength{\oddsidemargin}{-0.20in}
\endlocaldefs
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\linespread{1.6} %double line space


\begin{document}
\date{empty}
\begin{frontmatter}
\title{The Challenges of Model Objective Selection and Estimation for Ad-hoc Network Data Sets}
%\protect\thanksref{T1}}
\runtitle{Challenges of Model Objective Selection and Estimation}
%\thankstext{T1}{Prepared with partial support of N.S.F. Grant G.P. 2593.}

\begin{aug}
\author{\fnms{Farinaz} \snm{Koushanfar}\thanksref{a1,a2}\ead[label=e1]{}}
\and 
\author {\fnms{Davood} \snm{Shamsi}\thanksref{a2}\ead[label=e2]{}}
\address[a1]{Electrical and Computer Engineering Department, Rice University, Houston, TX 77005}
\address[a2]{Computer Science Department, Rice University, Houston, TX 77005}
\runauthor{Koushanfar and Shamsi}
\contributor{Koushanfar, F.}{Rice University}
\contributor{Shamsi, D.}{Rice University}


\affiliation{Rice University}

\end{aug}
\begin{abstract}
We introduce a new methodology for determining the difficulty of
selecting the modeling objective function and estimating the parameters for
an ad-hoc network data set. The method utilizes formulation of
the underlying optimization problem instance that consists of an objective function and a set of
constraints. The method is illustrated on real distance measurement
data used for estimating the locations of wireless nodes that is the
most studied and a representative problem for ad-hoc networks
estimation. The properties of the data set that could affect the
quality of optimization are categorized. In large optimization
problems with multiple properties (characteristics) that contribute
to the solution quality, it is practically impossible to
analytically study the effect of each property. A number of metrics
for evaluating the effectiveness of the optimization on each data
set are proposed. Using the well known Plackett and Burmann fast
simulation methodology, for each metric, the impact of the
categorized properties of the data are determined for the specified
optimization. A new approach for combining the impacts resulting
from different properties on various metrics is described. We
emphasize that the method is generic and has the potential to be
more broadly applicable to other parameter estimation problems.
\end{abstract}

%\begin{keyword}[class=AMS]
%\kwd[Primary ]{62G05}
%\kwd{60K35}
%\kwd[; secondary ]{62G20}
%\end{keyword}

%\begin{keyword}
%\kwd{L\'evy processes}
%\kwd{nonparametric estimation}
%\kwd{model selection}
%\end{keyword}

\tableofcontents

\end{frontmatter}

\section{Introduction}
\label{sec:intro}
% what is the problem

\hspace{1pc} Wireless adhoc networks consist of multiple wireless nodes distributed in an implementation area. To be power efficient, the wireless nodes only directly communicate with the nodes in their short local range (neighbor nodes). Communication between the non-neighbor nodes is enabled by successive usage of (one or more) local neighbors as forwarding relays. Several problems in this domain include modeling and estimation of data sets that only contain pairwise exchanged data between the neighboring nodes.

Years of continuous research in building statistical models and parameter estimation has produced a multitude of readily available methods and tools that can be employed for the problems in ad-hoc networks \cite{book:Has01}.
One limitation of the available methods is that majority of the ad-hoc modeling and estimation problems
concern a large body of data and do not conform with typical assumptions needed to analytically declare
the known theoretical optimality criteria. In such scenarios, the quality of the modeling and estimation
methods are typically evaluated by how they perform on sets of real or simulated data. For example, some
statistics of the resulting prediction error and/or a defined criterion (e.g., Bayesian information
criterion (BIC)) is used for experimental evaluation of the method on the adhoc network measurements.
A relevant question to answer is if indeed modeling and estimation of the pertinent data set requires
introduction of a new model or an estimator, or the data could have been just as well addressed by
the other known methods.
%Aside from the theoretical properties, a useful new methodology
%is the one that can build models and estimators for difficult-to-characterize
%adhoc network data.


% why the problem is important
%The problem is both important and challenging.
Our objective is to quantify the difficulty of model selection and estimation for a given adhoc network data set. This would provide impetus for inventing newer modeling and estimation objectives and tools that can address the difficult-to-characterize data. Simultaneously, formation of new tools would depend upon finding truly challenging network data sets that need to be addressed, as opposed to building new models that have a limited practical usage. Devising sets of challenging data would also build a foundation for comparing the various modeling objective functions and estimators for the ad-hoc network data sets. The problem of finding challenging data is complicated by variations in properties of the underlying data sets collected by different sources. This includes difference in size, format, wireless ranges, hidden covariates, and the form of noise present in the collected data. Thus, it is not easy to find unique metrics that could be used for comparison of different modeling objective functions and estimation methods.

% what has been done
%Represe public databases for adhoc network data includes
%\cite{CRICKET_DATA},\cite{SAMSI}.
In statistics literature, sensitivity of estimation error or other discrepancy metrics to the underlying noise in data has been widely studied for a number of modeling methods \cite{book:SAL04}\cite{journal:BUL88}. Also, the consistency of estimators based on a number of strong assumptions on the distribution of the data has been pursued \cite{book:Leh06}. However, no generic method or tool for determining the difficulty in modeling a data set free of imposing strong assumptions -- such as normality or other closed-form distributions of noise -- is available for use in adhoc networks. Note that the runtime complexity of a problem is an orthogonal concept. The complexity measures the worst-case computational time for the algorithm used for addressing the problem. Analyzing the worst-case runtime complexity does not help in understanding the complexity of characterizing a specific data set.

% what are we doing
In adhoc network scenario, after the variable selection is done and the noise models are assumed, modeling is typically done by selecting a model form (e.g., nonlinear regression) and then estimating the model parameters on
the data set. For analyzing the modeling objective function and estimation
performance on the data, we study the pertinent optimization problem
that consists of an objective function (OF) and a number of constraints. The data set is considered as the input to the optimization problem. We introduce a number of metrics that measure the complexity of the optimization problem based on the problem OF properties and constraints. The challenge in most optimization problems is the existence of nonlinearities that make the solution space coarse, causing bumpiness and multiple local minimums. We propose a number of measures for the smoothness of the OF and constraints space that estimate the feasibility of reaching the global minimum.

To enable studying the effectiveness of the optimization on an adhoc network data set, one should characterize the properties of the pertinent data set. The properties are specific to each data set and the problem.
In this article, we focus on the problem of finding the location of nodes (localization) in an adhoc wireless network by using erroneous mutual distance measurements between a number of node pairs. However, we emphasize that our method is generic and can be used for determining the challenge in addressing many adhoc data set model objective selection and estimation that includes forming an optimization problem. The localization problem is selected for four reasons. First, it is a very well addressed problem in the literature and there are several methods that are developed for this problem \cite{conf:ERE04}\cite{conf:GOL05}\cite{journal:Pat06}\cite{conf:BIS04}\cite{NIS00}\cite{journal:Sli02}.
Second, there are a number of  publicly available data sets for the measured distance data in the networks \cite{CRICKET_DATA}\cite{UIUC_DATA}\cite{conf:Fen06B}. Third, the nonlinear
relationship between noise in measurements data and the location of
nodes makes the modeling problem extremely challenging. Fourth,
localization problem is an NP-complete problem, i.e., in the worst
case, there is no algorithm that can solve it in polynomial time
\cite{SAX79}\cite{conf:ERE04}. Lastly, location discovery is a precursor 
for a number of other problems in ad hoc networks including sleeping coordination \cite{conf:Kou06,journal:Kou07}, sensor coverage \cite{journal:Meg02}, and sensing exposure \cite{journal:Meg05}.

We characterize a number of properties of the measurement data set
that could affect the quality of location estimation. Studying the
interaction between the identified data properties and optimization
metrics requires long simulations and analysis. We use the
well-known Plackett and Burmann \cite{journal:Pla46} simulation
methodology to rapidly study the pairwise linear interactions of properties.
A new approach for combining the impacts resulting from different
properties of data on various optimization metrics is described. The
sensitivity of optimization with respect to the various parameter
ranks are presented.

% what is new
To the best of our knowledge, this is the first work that
systematically studies the impact of the adhoc network data set on the
optimization employed for finding the modeling objectives and estimations.
Most of the previous work are devoted to modeling and analysis of the worst case complexity. %We determine the degree of challenge in addressing an
%instance (input data) to the modeling problem.
The results of our analysis could be directly used for constructing
benchmarks for the problem. The proposed work aims at creating a
unified framework based on real data that can help evaluation and
comparison of desperate efforts that address the same problem.

% paper organization

The remainder of the paper is organized a follows. In the next
section, location estimation problem and our notations are formally
defined. In Section \ref{sec:metrics}, we devise a number of metrics
that are used for OF evaluation. The simulation methodology is
described in Section \ref{sec:pb}. In Section \ref{sec:combine}, we
illustrate how the results of different metrics can be combined. We
have applied the derived method on the measurements from a real
network in Section \ref{sec:result}. We conclude in Section
\ref{sec:conclusion}.


\section{Preliminaries}
\label{sec:prelim}

\hspace{1pc} In this section, we present the formal definition of the problem. We
also describe the notations that are used throughout the paper.\\

\noindent\textbf{Location estimation problem}: Given a set of $N$
nodes denoted by $V = $ \linebreak $\{v_1, v_2, \dots v_N\}$ in $\mathds{R}^d$ ($d
= 2,3$). For a given subset of node pairs denoted by $E \subset V
\times V$, mutual distance of nodes are measured, \ie, for all
$(v_i,v_j) \in E$, $l(v_i, v_j) = d(v_i, v_j) + \epsilon_{i,j}$ is
known; $ d(v_i, v_j) $ is the Euclidean distance between the nodes
$v_i$ and $v_j$; $\epsilon_{i,j}$ is the distance measurement error. 
This error is only known if the real and measured location are both available.
Moreover, there is a subset with $M(>2)$ nodes denoted by
$V_B=\{v_1,\dots v_M\}$, $V_B \subset V$ such that the nodes in
$V_B$ have their exact location information (coordinates). The nodes
in the set $V_B$ are called the {\it beacon} nodes.

\textbf{Question}: find the location of all possible nodes.

In this paper, we focus on two-dimensional networks. Extension to
three-\linebreak dimensional networks is straight forward. Coordinates of the
node $v_i$ are denoted by $(x_i,y_i)$.

The location estimation problem can be formulated as an optimization
problem. The goal is to find the coordinates of $K=N-M$ non-beacon
nodes such that the discrepancy (error) between the measured
distance data and the nodes' distances estimated from the final
coordinates is minimized. In other words,
\begin{eqnarray}
    \label{eq:optimiziation}
    &&F_L(x_{M+1}, y_{M+1}, x_{M+2}, y_{M+2}, \dots x_{N}, y_{N}) = \sum_{ ( v_i,v_j ) \in E} L(e_{v_i,v_j}) \\
    &&e_{v_i,v_j} = l(v_i,v_j) - \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \nonumber
\end{eqnarray}

Where $L:\mathds{R}\to \mathds{R}^+$ is a function that is typically
a metric (measure) of error. $F_L:\mathds{R}^{2K} \to \mathds{R}^+$
is known as objective function (OF) of the optimization problem.

Note that the OF of the location estimation problem is not
necessarily a linear or convex function. There are a number of fast
and efficient tools that are developed for linear and convex
programming. However, there is no oracle algorithm that can solve
all optimization problems. To find the minimum of a nonlinear
problem like location estimation, there are a number of heuristic
methods that may be employed. The nonlinear system solvers have a
tendency to get trapped in a local minimum and do not necessarily
lead to the global minimum. Although there are a variety of
minimization algorithms, most of them are common in one subcomponent
that starts from an initial point and follow the steepest decent to
reach the minimum. The algorithms differ in how they choose the
starting point, how they select the direction in the search space,
and how they avoid local (non-global) minima. Thus, the shape of the
OF around the global minimum is an important factor in finding the
solution.

%The true location of the nodes, $p_t$, is the global minimum of $F$. Moreover, objective function $F$ might have another local minimums. If $p_m$ is a local minimum of $F$, depth of this local minimum is defined as: $$

\noindent\textbf{Data set:} The measurement data used in this
problem consists of measured distances between a number of static
nodes in the plane. Measurements are noisy; there are multiple
measurements for each distance. The true location of the nodes is
known and will be known as the ground truth. As explained in Section
\ref{sec:intro}, we sample the data set to obtain instances with
specific properties.


\noindent\textbf{Parameters:} We will define a number of parameters
that can be extracted from the data set. The sensitivity of the
location estimation to the variations in each parameter will be
studied. 
The analysis results will be used for identifying the hard
%instances of data that are hard
instances of measurement data. Ten parameters are studied: 
%We the effect of different parameters in the location estimation
%problem and identifying the hard instances of measurement data. Ten
%parameters are studied:

\begin{itemize}
    \item $P_1$ -- {\it Number of nodes} ($N$): the total number of nodes in the network.
    \item $P_2$ -- {\it Number of beacons} ($B$): the number of beacon nodes with known locations.
    \item $P_3$ -- {\it Mean squared error} ($\overline{\epsilon^2}$): mean squared
    error of distance measurements.
    \item $P_4$ -- {\it Maximum allowed squared error}
    (MAX$_{\epsilon^2_m}$):
    the maximum squared error that can possibly exist in distance measurements.
    \item $P_5$ -- {\it Percent of large errors}
    ($PER_{\epsilon^2_0}$):
    percentage of squared distance measurement noises that are higher than a specific value $\epsilon^2_0$.
    \item $P_6$ -- {\it Mean degree} ($\overline{D}$): mean degree
    of the nodes in the network. Degree of a node $v_i$ is define as
    number of nodes that have their mutual distance to $v_i$.
    \item $P_7$ -- {\it Minimum length} (MINL): possible minimum length of the measured distances between nodes in the network.
    \item $P_8$ -- {\it Maximum length} (MAXL): possible maximum length of the measured distances between nodes in the network.
    \item $P_9$ -- {\it Mean length} ($\overline{l}$): mean length of the measured distances between nodes in the network.
    \item $P_{10}$ -- {\it Minimum degree} (MIND): possible minimum degree of the nodes in the network.
\end{itemize}

To study the effect of the parameters, we construct a variety of
network instances with different properties. The networks are
constructed by selecting subsets of an implemented network. Having
specific values for parameters, we use Integer Linear Programming
(ILP) to extract each subset such that it meets specified
conditions. To do so, we model parameter constraints as linear
equalities and inequalities. Some parameters such as the mean
squared error, $\overline{\epsilon^2}$, can be easily stated by
linear equalities and inequalities. But some parameters such as the
mean degree of the nodes, $\overline{D}$, need a mapping to be
stated in linear terms. The description of the exact procedure of
modeling by linear constraints is beyond the scop of this paper
\cite{conf:Fen06B}.

\section{Metrics}
\label{sec:metrics} \hspace{1pc} In this section, we introduce metrics for error
and OF that are used for evaluating the importance of different
parameters for location estimation. Three error metrics and four OF
metrics are presented. Thus, a total of twelve combined metrics are used
to evaluate the importance of parameters.

\subsection{Error Metrics}
\hspace{1pc} The three error metrics studied in this paper are: $L_1$, $L_2$, and
the maximum likelihood (ML). $L_1$ and $L_2$ are the common error
norms in the $L_p$ family defined as: %$L_1(e) = |e|$ and $L_2(e) = e^2$.
\begin{eqnarray} \label{eq:norm}
L_p(e_{v_n,v_m}\in E)=(\sum_{(v_n,v_m )\in E} |e_{v_n,v_m}|^p)^{1/p}
& if & 1 \leq p < \infty. \nonumber
\end{eqnarray}


To find the error metric corresponding to ML, we need to model the
noise in distance measurements. To model the noise, the probability
density function (PDF) of errors, $f_{m}$, for the distance
measurements should be approximated. Different methods are developed
to approximate PDF of noise, $f_m$ \cite{conf:Fen06B}. We have used
kernel fitting that is a simple and known PDF approximation method
\cite{book:Has01}. To have the maximum likelihood estimation for the
 nodes' locations, we find the nodes' coordinates such that they
maximize

\begin{equation}
    \prod_{ (v_n,v_m) \in E} f_m(e_{v_n,v_m}) = \mbox{exp}\{\sum_{ (v_n,v_m) \in E} \ln(f_m(e_{v_n,v_m}))\}
\end{equation}
or equivalently minimize
\begin{equation}
    \label{eq:ML}
    \sum_{ (v_n,v_m) \in E} - \ln(f_m(e_{v_n,v_m})).
\end{equation}
Note that we assume noise in distance measurements are independently
identically distributed. Using the same notations as the Equation
 \ref{eq:optimiziation} and Equation \ref{eq:ML}, for the ML estimation we consider the following
 error metric:
\begin{equation}
    L_{ML}(e_{v_n,v_m}) = -\ln(f_m(e_{v_n,v_m})).
\end{equation}


\subsection{Objective Function (OF) Metrics}

\hspace{1pc} We describe metrics that are used for evaluating OFs.
%All OFs are not same in optimizing. For example, convex OFs are easy to solve.
The metrics are introduced based on the properties of
 OF that are effective in optimization. These metrics
 are such that they assign larger values to the more
 difficult-to-optimize OFs. For example, if one selects a
 convex OF, it may be possible to utilize convex programming
 depending on the form of the constraints. In defining the OF
 metrics, we assume that there is a fixed instance of location estimation data.
 Thus, for a fixed error metric, the OF would be fixed. Metrics of OF are
 denoted by $M:\cC \to R^+$ where $\cC$ is the functional
 space that contains all OFs.

\begin{figure}[t]
\includegraphics[width=4.5in, height=3.0in]{koushanfar_objfcn.pdf}
 \caption{Metrics and objective function (OF).}
 \label{fig:objOneD}
\end{figure}

\subsubsection{Drifting of Objective Function (OF) }

\hspace{1pc} Since there is noise in distance measurements, true location of the
nodes is often not the global minimum of the OF. Location of the
OF's global minimum is a measure of the goodness of the OF. Figure
\ref{fig:objOneD} illustrates the effect of noise on the OF. For the
sake of presentation simplicity, an one-dimensional OF is shown. In
this figure, $p_c$ is the correct nodes' location. However, the
global minimum of the OF is displaced at $p_{gm}$ because of the noise. We
consider the distance between $p_c$ and its displaced location 
$p_{gm}$ as an OF metric and
denote it by \textit{drifting}.

To find the drifting distance, we start from the true locations as
the initial point. Next, the steepest descent direction of the OF is
followed until a local minimum is reached. The Euclidean distance
between the true locations and this local minimum quantifies the
drifting metric (denoted by $M_1$) for the pertinent OF.

\subsubsection{Nearest Local Minimum }

\hspace{1pc} Having a number of local minimums around the global minimum in an OF
may cause the optimization algorithm to get trapped in one of the
non-global local minimums. It is challenging to minimize such an OF
since the global minimum is hard to reach. Figure \ref{fig:objOneD}
illustrates the phenomena. The OF has multiple local minima at
points $p_{m1}$, $p_{m1}$ and so on. The steepest decent method
leads to the global minimum if and only if we start from a point
between $p_{m1}$ and $p_{m2}$. Hence, having a small distance
between $p_{m1}$ and $p_{m2}$ would complicate the selection of the
initial starting point.

We introduce a method to measure the distance of the true locations
from the local minimums around the global minimum. Because of curse
of dimensionality, it is not possible to find all the local minimums
around the global minimum. We randomly sample the OF in multiple
directions. The nearest local minimum is computed for each randomly
selected direction. We statistically find the distance to the
nearest local minimum by using multiple samples.

Assume $F: \mathds{R}^{2K} \to \mathds{R}^+$ is the OF. A random
direction in $\mathds{R}^{2K}$ is a vector in this space. Let us
denote it by $v \in \mathds{R}^{2K}$.  First, we define a new
function $h: \mathds{R}^+\to \mathds{R}^+$ such that $h(t) = F(p_c +
tv)$ where $p_c$ is a vector containing the true locations of nodes.
Second, we find the local minimum of $h$ with the smallest positive
$t$ and denote it by $t_1$. We repeat this procedure for $T$ times
and find all $t_i$'s. $T$ is the number of samples. Finally, since
it is expected that the defined metric has a larger value for more
difficult-to-optimize OF, we define the nearest local minimum metric
to be

\begin{equation}
M_2(F) = \lmat \frac{1}{T}\sum_{i=1}^T t_i \rmat^{-1}.
\end{equation}

\subsubsection{ Measuring the Slope of OF Around the Solution }

\hspace{1pc} The Slope of OF (\ie, the norm of OF's gradient) around the global
minimum is a very important parameter in the convergence rate of the
optimization algorithm. OFs with a small slope around the true
location converge to the global minimum very slowly.

Thus, measuring the slope of the OF around the global minimum can be
used to quantify the goodness of OF. Again, we measure slope of the
OF in multiple random directions around the true locations, and
statistically compute this metric. OFs with sharp slopes around the
global minimum are easier to optimize. This can be seen in Figure
\ref{fig:impval} where the right side of the global minimum,
$p_{gm}$, has a sharp slope. If the initial point of steepest
descent algorithm is between $p_{gm}$ and $p_{m2}$, it converges to
the global minimum very fast. However, on the left side of global
minimum, $p_{gm}$, there is a gradual slope. Thus, the steepest
descent algorithm would converge very slowly on the left side. We
define the true locations' slope metric as

\begin{equation}
M_3(F) = \lmat \frac{1}{T}\sum_{i=1}^T \mbox{slope in i-th random
direction}\rmat^{-1}.
\end{equation}

Note that the slope of the i-th random direction, $v_i$, is measured
at $p_{gm} + \sigma v_i$ where $\sigma$ is a small number and is a
user's defined criterion.

\subsubsection{ Depth of the Non-Global Local Minima}

\hspace{1pc} Optimization problems that have an OF with deep local minimums
around the global minimum are difficult to solve. A number of
heuristic optimization methods take advantage of the shallow local
minimums to avoid non-global local minimums, e.g., simulated
annealing \cite{journal:Kir83}. In figure \ref{fig:impval}, avoiding
the local minimum at $p_{l1}$ is much easier than local minimum at
$p_{l2}$.

We define the forth metric for quantifying the goodness of an OF on
the data, as the depth of the non-global local minimums. We randomly
select $T$ local minimums around the true locations. Assuming that
$m_i$ is the OF value at the randomly selected local minimums,
define

\begin{equation}
M_4(F) = { \lmat \frac{1}{T}\sum_{i=1}^T m_i \rmat }^{-1}.
 \end{equation}

\section{Simulation Methodology}
\label{sec:pb}

\hspace{1pc} We find the linear effect of each parameter by studying all combinations of
parameters. Assume each parameter has just two values. If we have
$k$ parameters then we have to study $2^k$ combinations that is
computationally intractable.  Instead, we use Plackett and Burman
(PB) \cite{journal:Pla46} fast simulation methodology that is a very
well known method for reducing the number of simulations. Number of
simulation in PB is proportional to the number of parameters. Although the PB method has not been used for the adhoc modeling and estimation problems, it was used for the simulations speedup in a number of other adhoc network problems \cite{Bar02}\cite{Per02}\cite{Tot05}\cite{Vad04}.


In PB design, two values are assigned to each parameter: a  normal
value and an extreme value. The normal value is the typical value of
the parameter while the extreme value is the value that is outside
the typical range of the parameter. The extreme value often makes
the problem either harder or easier to solve. A number of
experiments with normal and extreme values of parameters are
conducted.

Experiments are arranged based on a given matrix denoted by the {\it
design matrix}. Design matrix has $k$ columns ($k$ is the number of
parameters) and $s$ rows where $s$ is the number of experiments the
should be set up as follows. The elements of the design matrix are
either $0$ or $1$. We set up an experiment for each row. Values of
the parameters depend on the elements on the row: 0 indicates that
the normal value of the parameter is used and 1 indicates that the
extreme value of the parameter is used in the experiment
corresponding to the row.
%An example of a problem with 11 parameters is shown in Figure \ref{fig:pb}. The last element of each column in the %design matrix is $0$ (Run $12$). First column of the design matrix ($P_1$) is taken from \cite{}. Elements $1$ through %$11$ in $P_2$ column is a circular rotation of elements $1$ through $11$ in $P_1$ columns and so on.

%
%\begin{figure}[t]
% \centering
% \includegraphics[width=0.5\textwidth]{pb}
% \caption{PB design matrix and importance value of the parameters.}
% \label{fig:pb}
%\end{figure}


%We set up an experiment for each row. Value of the parameters is depended on elements on the row. 0 indicates that %normal value of the parameters is used and 1 indicates that the extreme value of parameter is used in the experiment. %For example, experiment correspond to the fist row of Figure \ref{fig:pb} would have normal value for $P_2$, $P_4$, %$P_5$, $P_6$, and $P_{10}$ and extreme value for $P_1$, $P_3$, $P_7$, $P_8$, $P_9$, and $P_{11}$.


%As you can see in the Table ?, second row of the design matrix is one element rotation of the first row and so on. %Last raw, all elements are 1.



Assume that we have selected an error metric, $L_i$, and an
objective function metric, $M_j$. The OF itself denoted by $F_{L_i}$
would be fixed. For each row of the design matrix, $h$, we setup an
experiment based on the elements of that row and measure the
goodness of the objective function $M_j(F_{L_i})$ and save it in
another array element denoted by $r_{i,j,h}$. The corresponding
values are summed up for computing the importance factor (IF) of
each parameter. For each parameter $P_t$, we define

\begin{equation}
    \mbox{IF}_{t,i,j} = | \sum_{h=1}^{s} \alpha_{h,t} r_{i,j,h}|
\end{equation}
where $s$ is the number of experiments (number of rows in the design
matrix), and $\alpha_{h,t}$ is $1$ if the extreme value of the
parameter $P_t$ is used in the $h$-th experiment; otherwise,
$\alpha_{h,t}$ is $-1$. The absolute value of IF is used to evaluate
the effect of each parameter. The largest value indicates the most
important parameter. For $i$-th error metric and $j$-th OF metric,
$\mbox{IF}_{t,i,j} > \mbox{IF}_{u,i,j}$ means that the parameter
$P_t$ is more important than $P_u$. Thus, for each error metric,
$L_i$, and for each objective function metric, $M_j$, we can rank
parameters based on their effect on the estimated location. This
ranking is denoted by $R_{i,j}$.
 %The last row in Figure \ref{fig:pb} is IF of parameters. The important parameters are $P_7$, $P_5$, $P_{10}$, $P_9$, $P_4$, $P_2$, $P_3$, $P_{11}$, $P_8$, and $P_1$, respectively.

%Figure \ref{fig:pb} shows a single fold design matrix.
More precise results can be obtained by using the  foldover design
matrix \cite{book:MON01}. In the foldover design
matrix, all rows of the single design are repeated after its last
row but 0s and 1s are exchanged in the repeated rows.

\section{Combining Different Ranks}
\label{sec:combine}

\hspace{1pc} In this section, we explain how to combine the rankings of the
parameters under study to obtain a global order for them. Using the
ranking method in the previous section, we would have different
rankings for various error metrics and OF metrics. Since there are
three error metrics and four objective function metrics, there would
be twelve different ranking lists for the importance of parameters;
each parameter may have a different rank in each ranking list.

%Not all rankings have the same quality.
Each rank is obtained based on a specific property of the
optimization  problem. As it is explained in Section
\ref{sec:metrics}, for each error and objective function metric, the
parameters are ranked based on the importance factor obtained from
PB-design. IFs with large discrepancies lead to a stronger ranking
compared to IFs with small discrepancies. Simply summing up the rankings 
would not necessarily determine which of the importance factors were better 
differentiating among the parameters.

For each ranking, $R_{i,j}$, and for each pair of parameters, $P_s$,
$P_t$, we find the probability that $P_s$ is more important than
$P_t$. Based on the probabilities, we construct the global ranking.


Consider a specific error metric, $L_i$, and a specific objective
function metric, $M_j$. Assume that the importance factor of the
parameter $P_t$, $\mbox{IF}_{t,i,j}$, is normally distributed
$\mathcal{N}(\lambda_{t,i,j}, \sigma^2)$. The observed value of
$\mbox{IF}_{t,i,j}$ in a specific experiment is denoted by
$if_{t,i,j}$. We normalize the importance factors to have a maximum
value $W$. The mean of IFs are assumed to be uniformly distributed
in $[0, W]$.

For each two parameters, $P_s$ and $P_t$, given the BP-design
experiment importance values  $ if_{s,i,j}$, and $if_{t,i,j}$, we
find the probability:
$Pr(\lambda_{s,i,j} \geq \lambda_{t,i,j}| IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j})$. 
The conditional
probability can be written in the Bayesian format as
\begin{eqnarray}
&&\beta_{s,t,i,j} = Pr(\lambda_{s,i,j} \geq \lambda_{t,i,j} | IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j}) =  \nonumber \\
 &&\frac{   Pr(IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j} | \lambda_{s,i,j} \geq \lambda_{t,i,j} )  Pr( \lambda_{s,i,j} \geq \lambda_{t,i,j} ) }{  Pr(IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j} ) }.
\end{eqnarray}

%$V_{t,i,j}$ and $V_{s,i,j}$ are Gaussian random variables that
%describe the IFs for the parameters $P_t$ and $P_s$ respectively.
Since there is no prior information about the distributions of
$\lambda_{s,i,j}$ and $\lambda_{t,i,j}$, we assume that $Pr(
\lambda_{s,i,j} \geq \lambda_{t,i,j} ) = \frac{1}{2}$. Furthermore,

\begin{eqnarray}
&& Pr(IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = v_{t,i,j} | \lambda_{s,i,j} \geq \lambda_{t,i,j} ) =  \nonumber \\
 && \int_{x = 0}^W \int_{y = x}^W  Pr(IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j} | \lambda_{s,i,j} = y , \lambda_{t,i,j} = x )
 \frac{dy}{W}\frac{dx}{W} = \nonumber \\
 && \frac{1}{W^2}\int_{x = 0}^W \int_{y = x}^W  \frac{1}{\sqrt{2\pi \sigma^2}} e^{\frac{(y - if_{s,i,j})^2}{2 \sigma^2}} \frac{1}{\sqrt{2\pi \sigma^2}} e^{\frac{(x - if_{t,i,j})^2}{2 \sigma^2}}
 dy \ dx.
\end{eqnarray}

Similarly, one can find
%\scriptsize{
\begin{align*}
 Pr(I&F_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j} ) \\
&=  
Pr(IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j} |\lambda_{s,i,j} \geq \lambda_{t,i,j} )  
Pr(\lambda_{s,i,j} \geq \lambda_{t,i,j}) \\
  &+  Pr(IF_{s,i,j} = if_{s,i,j} , IF_{t,i,j} = if_{t,i,j} |\lambda_{s,i,j} < \lambda_{t,i,j} )  
Pr(\lambda_{s,i,j} < \lambda_{t,i,j}) \nonumber.
\end{align*}

Now, for each parameter, $P_t$, we define the global importance
factor, $if_t$,

\begin{equation}
    if_t = \sum_{i=1}^{N_{em}} \sum_{j=1}^{N_{om}} \sum_{s = 1, s \neq  t}^{N_p} \beta_{s,t,i,j}.
\end{equation}

Parameters with a larger $if_t$ have a higher probability of being
important compared to the other parameters. We sort the parameters
based on their corresponding $if_t$ values.

\section{Evaluation Results}
\label{sec:result}

We have applied the developed method to real distance measurement
data for location estimation problem. Parameters that were described
in Section \ref{sec:prelim} are ranked using our methodology. We
illustrate how the various ranking lists differ. Then, we combine
the rankings to obtain a global ranking.



\begin{table}[t]
\tiny
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Parameter& $N_S$ & $B_S$ & $\overline{\epsilon^2_S}$ & MAX$_{\epsilon^2_m}$ & $PER_{\epsilon^2_0}$ & $\overline{D_S}$ & MINL$_S$ & MAXL$_S$ & $\overline{l_S}$ & MIND$_S$\\
\hline
Normal                            &     55 &  12 &  10 ($m^2$) &  200 ($m^2$) &  50 &  10 &  5  ($m$) &  40 ($m$) &  20 ($m$) &  4 \\
Value &   &   &  & &  &  &   &  &   & \\
Extreme                          &     80 &  3  &  50 ($m^2$) &  500 ($m^2$) &  20 &  6  &  10 ($m$) &  60 ($m$) &  30 ($m$) &  3 \\
Value &   &   &  & &  &  &   &  &   & \\
\hline
\end{tabular}
\vspace{1pc}
%\end{center}
\caption{Normal and extreme values for the parameters.}
\label{tbl:values}
\end{table}


The distance measurements data from the CENS lab \cite{CENS_LAB} is
used to evaluate the effect of each parameter. This database is
based on the real distance measurements for SH4 nodes
\cite{conf:Fen06B}. 91 nodes are located in fixed locations.
Distance measurement is done multiple times and in different days.
The distance measurements are based on the time of flight
(ToF)\cite{conf:Lan06} of the signals. In this method, the time of
flight of an acoustic signal is used to determine the distance
between two nodes. It was previously shown that the noise in the
measurements is strongly non-static \cite{conf:Fen06}. Therefore,
parametric methods based on optimizing the results according to a
fixed noise distribution do not yield good location estimations.

We have used Integer Linear Programming (ILP) to sample the database
for drawing instances with specific properties. In each experiment,
the PB-design matrix implies a specific value for each parameter.
Extreme and normal values for parameters are shown in Table
\ref{tbl:values}. The values are determined based on the real
measurements' error. In all experiments, $\epsilon^2_0$ is equal to
$20 (m^2)$.

\begin{table}
\begin{center}
\tiny
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Parameter & \multicolumn{3}{c|}{ DOF } & \multicolumn{3}{c|}{NLM} & \multicolumn{3}{c|}{SMAS} & \multicolumn{3}{c|}{DNGLM}\\
\cline{2-13}
& $L_1$ & $L_2$ & ML & $L_1$ & $L_2$ & ML & $L_1$ & $L_2$ & ML & $L_1$ & $L_2$ & ML \\
\hline
$N_S$                            & 4  & 4  & 2  & 6  & 5  & 6  & 2  & 2  & 2  & 3  & 2  & 1  \\ % number of nodes
$B_S$                            & 2  & 1  & 1  & 4  & 2  & 3  & 4  & 9  & 4  & 1  & 4  & 3  \\ % number of beacons
$\overline{\epsilon^2_S}$        & 1  & 2  & 3  & 2  & 3  & 4  & 3  & 3  & 3  & 5  & 9  & 6  \\ % MSE
MAX$_{\epsilon^2_m}$             & 6  & 8  & 7  & 9  & 10 & 10 & 6  & 4  & 5  & 7  & 7  & 8  \\ % maximum squared error
$PER_{\epsilon^2_0}$             & 7  & 9  & 10 & 10 & 8  & 5  & 7  & 8  & 7  & 9  & 10 & 9  \\ % percentage more than..
$\overline{D_S}$                 & 3  & 3  & 4  & 1  & 1  & 1  & 1  & 1  & 1  & 2  & 1  & 2  \\ % mean degree
MINL$_S$                         & 8  & 6  & 8  & 7  & 6  & 9  & 8  & 5  & 10 & 4  & 3  & 10 \\ % minimum length
MAXL$_S$                         & 10 & 10 & 9  & 5  & 9  & 8  & 10 & 10 & 8  & 10 & 5  & 4  \\ % maximum length
$\overline{l_S}$                 & 9  & 5  & 5  & 8  & 7  & 7  & 9  & 7  & 9  & 6  & 6  & 5  \\ % mean edge length
MIND$_S$                         & 5  & 7  & 6  & 3  & 4  & 2  & 5  & 6  & 6  & 8  & 8  & 7  \\ % min degree

\hline
\end{tabular}
\end{center}
\vspace{1pc}
\caption{Importance of different parameters for different objective functions and metrics.}
\label{tbl:pb1}
\end{table}

The following abbreviations are used in this section.
\begin{itemize}
 \item ML   : Maximum Likelihood
 \item DOF  : Drifting of the Objective Function ($M_1$)
 \item NLM  : Nearest Local Minimum ($M_2$)
 \item SMAS : Slope Measurement Around the Solution ($M_3$)
 \item DNGLM: Depth of Non-Global Local Minimum ($M_4$)
\end{itemize}

Table \ref{tbl:pb1} shows the result of PB-based evaluations. Each
parameter is ranked based on the specific error metric and the
specific OF metric. It can be seen that a specific parameter has
different rankings under various error metrics and OF metrics. For
example, the total number of nodes, $N_S$, is ranked 1, 2, 3, 4, 5,
and 6 in different cases. Thus, a specific parameter does not have
the same importance under various metrics. %The effect of one
%parameter depends on the error metric and the OF metric.
It can be seen that the number of nodes, $N_S$, and the number of
beacons, $B_S$, are the two important parameters in most
evaluations; $PER_{\epsilon^2_0}$ and MAXL$_S$ have overall low
rankings.


\begin{figure}[h!]
\centering
\makebox{\includegraphics[height=2.5in,width=4.0in]{koushanfar_BarPlot.pdf}}
\caption{Importance of different parameters for different objective functions and metrics.}\label{fig:impval}
\end{figure}

The comparative ranks of parameter pairs tend to vary as well.
Figure \ref{fig:impval} shows the normalized importance factor (IF)
for two cases: DOF and SMAS with $L_2$ error metric. For DOF, the
number of beacons $B_S$ is strongly more important than the mean
squared error $\overline{\epsilon^2_S}$. The mean degree of nodes,
$\overline{D_S}$, is weakly more important than the mean squared
error $\overline{\epsilon^2_S}$. The same behavior can be seen in
SMAS. From our visual inspections, the number of nodes $N_S$ and the
mean degree of nodes $\overline{D_S}$ are the most important while
others almost have the same importance factor (IF). The ranks of the
mean squared error $\overline{\epsilon^2_S}$ and maximum edge length
MAXL$_S$ are 3 and 10 respectively. However, their importance
factors are very close.

The discrepancy in the rank and comparative ranks confirms our
postulation that averaging the parameter ranks is not the best way
for combining them. Thus, we use the combining method that was
introduced in Section \ref{sec:combine}. The probability comparisons
for the values in Figure \ref{fig:impval} are shown in Tables
\ref{tbl:comp1} and \ref{tbl:comp2}. The tables compare the
importance of parameters. For example, for the DOF-$L_2$, Figure
\ref{fig:impval} states that $B_S$ is strongly more important than
$PER_{\epsilon^2_0}$. Table \ref{tbl:comp1} shows that the
probability that the mean of $B_S$ is larger than the mean of
$PER_{\epsilon^2_0}$ is $0.984$. Similarly, MAX$_{\epsilon^2_m}$ and
$PER_{\epsilon^2_0}$ have approximately the same importance. The
probability that the mean of MAX$_{\epsilon^2_m}$ is larger than the
mean of $PER_{\epsilon^2_0}$ is $0.49$. This probability value is
close to 0.5, meaning that there is not enough information to
compare the values.


Table \ref{tbl:comp2} compares the importance factors of SMAS for
the $L_2$ error metric. %Based on Figure \ref{fig:impval}, number of
%nodes, $N_S$, and the mean degree of the graph $\overline{D_S}$ are
%the most important factors in the evaluation.
Table \ref{tbl:comp2} confirms the result. The rows corresponding to
$N_S$, and $\overline{D_S}$ have values close to $1$ confirming the
high importance of the two parameters. When comparing other
parameters, the probability that one parameter is greater than the
other is about $0.5$. It confirms our previous postulation that
simple rankings are not sufficient for concluding the global
parameter ordering and the importance factors are significant as well.


\begin{table}
\begin{center}\tiny
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Parameter& $N_S$ & $B_S$ & $\overline{\epsilon^2_S}$ & MAX$_{\epsilon^2_m}$ & $PER_{\epsilon^2_0}$ & $\overline{D_S}$ & MINL$_S$ & MAXL$_S$ & $\overline{l_S}$ & MIND$_S$\\
\hline
$N_S$                           &      0 &   0.071 &   0.417 &   0.725 &   0.716 &   0.403 &   0.708 &   0.691 &   0.598 &   0.748 \\
$B_S$                           &  0.929 &       0 &   0.899 &   0.993 &   0.984 &   0.884 &   0.977 &   0.981 &   0.939 &   0.984 \\
$\overline{\epsilon^2_S}$       &  0.583 &   0.101 &       0 &   0.787 &   0.786 &   0.476 &   0.756 &   0.754 &   0.660 &   0.798 \\
MAX$_{\epsilon^2_m}$            &  0.275 &   0.007 &   0.213 &       0 &   0.490 &   0.193 &   0.464 &   0.477 &   0.354 &   0.515 \\
$PER_{\epsilon^2_0}$            &  0.284 &   0.016 &   0.214 &   0.510 &       0 &   0.202 &   0.469 &   0.499 &   0.357 &   0.528 \\
$\overline{D_S}$                &  0.597 &   0.116 &   0.524 &   0.807 &   0.798 &       0 &   0.785 &   0.795 &   0.678 &   0.821 \\
MINL$_S$                        &  0.292 &   0.023 &   0.244 &   0.536 &   0.531 &   0.215 &       0 &   0.519 &   0.392 &   0.545 \\
MAXL$_S$                        &  0.309 &   0.019 &   0.246 &   0.523 &   0.501 &   0.205 &   0.481 &       0 &   0.371 &   0.537 \\
$\overline{l_S}$                &  0.402 &   0.061 &   0.340 &   0.646 &   0.643 &   0.322 &   0.608 &   0.629 &       0 &   0.671 \\
MIND$_S$                        &  0.252 &   0.016 &   0.202 &   0.485 &   0.472 &   0.179 &   0.455 &   0.463 &   0.329 &       0 \\
\hline
\end{tabular}
\vspace{1pc}
\caption{Drifting of objective function and $L_2$ metric:
$Pr(\lambda_{i,j,s} \geq \lambda_{i,j,t} | V_{i,j,s} = v_{i,j,s} ,
V_{i,j,t} = v_{i,j,t})$ where the first column is $P_s$
and the first row is $P_t$.}
\label{tbl:comp1}
\end{center}
\end{table}




\begin{table}
\begin{center}\tiny
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Parameter& $N_S$ & $B_S$ & $\overline{\epsilon^2_S}$ & MAX$_{\epsilon^2_m}$ & $PER_{\epsilon^2_0}$ & $\overline{D_S}$ & MINL$_S$ & MAXL$_S$ & $\overline{l_S}$ & MIND$_S$\\
\hline

$N_S$                           &     0 &  0.947 &  0.947 &  0.936 &  0.944 &  0.285 &  0.939 &  0.931 &  0.937 &  0.958 \\
$B_S$                           & 0.053 &      0 &  0.493 &  0.506 &  0.504 &  0.017 &  0.501 &  0.496 &  0.500 &  0.504 \\
$\overline{\epsilon^2_S}$       & 0.053 &  0.507 &      0 &  0.509 &  0.505 &  0.018 &  0.504 &  0.516 &  0.507 &  0.511 \\
MAX$_{\epsilon^2_m}$            & 0.064 &  0.494 &  0.491 &      0 &  0.505 &  0.017 &  0.504 &  0.506 &  0.499 &  0.499 \\
$PER_{\epsilon^2_0}$            & 0.056 &  0.496 &  0.495 &  0.495 &      0 &  0.017 &  0.492 &  0.496 &  0.502 &  0.500 \\
$\overline{D_S}$                & 0.715 &  0.983 &  0.982 &  0.983 &  0.983 &      0 &  0.975 &  0.984 &  0.974 &  0.980 \\
MINL$_S$                        & 0.061 &  0.499 &  0.496 &  0.496 &  0.508 &  0.025 &      0 &  0.506 &  0.501 &  0.488 \\
MAXL$_S$                        & 0.069 &  0.504 &  0.484 &  0.494 &  0.504 &  0.016 &  0.494 &      0 &  0.502 &  0.494 \\
$\overline{l_S}$                & 0.063 &  0.500 &  0.493 &  0.501 &  0.498 &  0.026 &  0.499 &  0.498 &      0 &  0.505 \\
MIND$_S$                        & 0.042 &  0.496 &  0.489 &  0.501 &  0.500 &  0.020 &  0.512 &  0.506 &  0.495 &      0 \\
\hline
\end{tabular}
\end{center}
\vspace{1pc}
\caption{SMAS and $L_2$ metric: $Pr(\lambda_{i,j,s}  \geq
\lambda_{i,j,t} | V_{i,j,s} = v_{i,j,s} , V_{i,j,t} = v_{i,j,t})$
where the first column is $P_s$  and the first row is $P_t$.}
\label{tbl:comp2}
\end{table}

\begin{table}[t]
\begin{center}\tiny
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Parameter& $N_S$ & $B_S$ & $\overline{\epsilon^2_S}$ & MAX$_{\epsilon^2_m}$ & $PER_{\epsilon^2_0}$ & $\overline{D_S}$ & MINL$_S$ & MAXL$_S$ & $\overline{l_S}$ & MIND$_S$\\
\hline
Rank                           &     2 &  3 &  4 &  8 &  10 &  1 &  6 &  9 &  7 &  5 \\
\hline
\end{tabular}
\end{center}
\vspace{1pc}
\caption{Global ranks.} \label{tbl:frank}
\end{table}


The global ranking based on the introduced combining method in
Section \ref{sec:combine} is shown in Table \ref{tbl:frank}. The
table indicates that the mean degree of nodes $\overline{D_S}$ is
the most important parameter. This result is consistent with Table
\ref{tbl:pb1} where the mean degree of nodes $\overline{D_S}$ is the
most important parameter in the seven scenarios.

The global ranking results could be used to improve the goodness of
location estimations in ad-hoc networks. To deploy a network or on
an already deployed network, one could exploit the results by
considering the analyzed effect of each parameter on the estimated
location's accuracy. Based on the constraints of the problem, the
best parameters for improving the estimated locations could be
determined. For example, when there are limitations for the mean
degree of the graph, one can increase the number of nodes in the
network to increase the accuracy of the estimated location. Note
that, changing one parameter typically only improves the accuracy up
to a certain point; further changing the parameter would not yield
an improvement in the estimation accuracy.


\section{Conclusion}
\label{sec:conclusion}

\hspace{1pc} We introduce a systematic methodology for determining the challenge
of modeling a pertinent adhoc network data set. The complex modeling problem is studied as an instance of a nonlinear optimization problem that
consists of an objective function (OF) and a set of constraints. The
data set is the optimization input and the estimated model is the
output. We characterize the input by a set of its characteristic
parameters. We define four new metrics that can be used to evaluate
the goodness of an input for being optimized by a specific OF. The
introduced metrics are: (1) drifting of the OF, (2) distance to the
nearest local minimum, (3) the slope of the OF around the solution,
and (4) the depth of the non-global local minima. We employ Plackett
and Burmann simulation methodology to systematically evaluate the linear
impact of various input parameters under each metric. Finally, we
present a method for combining the effect of parameters under different metrics to determine the global impact of each parameter. We utilize the new methodology for estimating the locations of the nodes in an ad-hoc network where the distance measurement data is available. Three common forms of OF are considered: $L_1$, $L_2$ and $L_\infty$. Our evaluations show that the mean degree on the nodes and the number of nodes in the network are the two most important parameters for estimating the locations.

\section*{Acknowledgement}
This work is partly supported by the National Science Foundation (NSF)
CAREER Award under grant number 0644289.

%\bibliographystyle{plain}
%\bibliography{davoodbib}
\begin{thebibliography}{0}
\bibitem{Bar02}
\textsc{Barrett, C., Marathe, A., Marathe, M. V.} and \textsc{Drozda, M.} (2002). Characterizing the interaction between routing and MAC protocols in ad-hoc networks. \textit{MobiHoc}, 92-–103.

\bibitem{conf:BIS04}
\textsc{Biswas, P.} and \textsc{Ye, Y.} (2004). Semidefinite programming for ad hoc wireless sensor network localization. \textit{Information Processing in Sensor Networks (IPSN)}, 2673–-2684.

\bibitem{journal:BUL88}
\textsc{Bullard, C.} and \textsc{Sebald, A.} (1988). Monte carlo sensitivity analysis of input-output models. \textit{The Review of Economics and Statistics}, \textbf{22.4}, 708–-712.

\bibitem{CENS_LAB}
\textit{CENS: Center for Embedded Networked Sensing at UCLA}. \url{http://research.cens.ucla.edu/}.

\bibitem{CRICKET_DATA}
\textit{The Cricket indoor location system at MIT}. \url{http://cricket.csail.mit.edu}.

\bibitem{conf:ERE04}
\textsc{Eren, T., Goldenberg, D., Whiteley, W., Yang, Y. R., Morse, A., Anderson, B.} and \textsc{Belhumeur, P.} (2004). Rigidity, computation, and randomization in network localization. \textit{INFOCOM}, 2673–-2684.

\bibitem{conf:Fen06}
\textsc{Feng, J., Girod, L.} and \textsc{Potkonjak, M.} (2006). Consistency-based on-line localization in sensor networks. \textit{Distributed Computing in Sensor Systems (DCOSS)}, 529-–545.

\bibitem{conf:Fen06B}
\textsc{Feng, J., Girod, L.} and \textsc{Potkonjak, M.} (2006). Location discovery using data-driven statistical error modeling. \textit{INFOCOM}, 1–-14.

\bibitem{conf:GOL05}
\textsc{Goldenberg, D., Krishnamurthy, A., Maness, W., Yang, Y., Young, A., Morse, A.} and \textsc{Savvides, A.} (2006). Network localization in partially localizable networks. \textit{INFOCOM}, 313-–326.

\bibitem{book:Has01}
\textsc{Hastie, T., Tibshirani, R.} and \textsc{Friedman, J.} (2001). \textit{The Elements of Statistical Learning: Data Mining, Inference, and Prediction}. Springer-Verlag, Germany.

\bibitem{journal:Kir83}
\textsc{Kirkpatrick, S., Gelatt, C. D. Jr.} and \textsc{Vecchi, M.P.} (1983). Optimization by simulated annealing. \textit{Science}, \textbf{220.4598}, 671-–680.

\bibitem{journal:Kou07}
\textsc{Koushanfar, F., Davare, A., Nguyen, D., Sangiovanni-Vincentelli, A.} and \textsc{Potkonjak, M.} (2007). Techniques for maintaining connectivity in wireless ad-hoc
networks under energy constraints. \textit{ACM Trans. on Embedded Computing Systems}, \textbf{6.3}, 16--37.

\bibitem{conf:Kou06}
\textsc{Koushanfar, F., Taft, N.} and \textsc{Potkonjak, M.} (2006). Sleeping coordination for comprehensive sensing using isotonic regression and domatic partitions. \textit{INFOCOM}, 1-–13.

\bibitem{book:Leh06}
\textsc{Lehmann, E.} (2006). \textit{Nonparametrics: Statistical Methods Based on Ranks}. Springer-Verlag, Germany.

\bibitem{journal:Meg02}
\textsc{Megerian, S., Koushanfar, F., Qu, G., Veltri, G.} and \textsc{Potkonjak, M.} (2002). Exposure in wireless sensor networks: Theory and practical solutions. \textit{ACM Journal
of Wireless Networks}, \textbf{8.5}, 443–454.

\bibitem{journal:Meg05}
\textsc{Megerian, S., Koushanfar, F., Potkonjak, M.} and \textsc{Srivastava, M.} (2005). Worst- and best-case coverage in sensor networks. \textit{IEEE Transactions on Mobile
Computing}, \textbf{4.1}, 84-–92.

\bibitem{conf:Lan06}
\textsc{Lanzisera, S., Lin, D.} and \textsc{Pister, K.} (2006). Rf time of flight ranging for wireless sensor network localization. \textit{WISES}, 1–-12.

\bibitem{book:MON01}
\textsc{Montgomery, D.} (2001). \textit{Design and Analysis of Experiments}, 5th ed. Wiley, New York.

\bibitem{journal:Pat06}
\textsc{Patwari, N., Ash, J., Kyperountas, S., Hero, A. III, Moses, R.} and \textsc{Correal, R.} (2005). Locating the nodes: cooperative localization in wireless sensor networks. \textit{IEEE Signal Processing Magazine}, \textbf{22.4}, 54-–69.

\bibitem{NIS00}
\textsc{Priyantha, N., Chakraborty, A.} and \textsc{Balakrishnan, H.} (2000). The cricket location-support system. \textit{MOBICOM}, 32--43.

\bibitem{UIUC_DATA}
\textit{OSL: Open Systems Laboratory at UIUC}. 
\url{http://www-osl.cs.uiuc.edu/research?action=topic\&topic=Sensor+Networks}.

\bibitem{Per02}
\textsc{Perkins, D., Hughes, H.} and \textsc{Owen, C.} (2002). Factors affecting the performance of ad hoc networks. \textit{ICC}, 2048–-2052.

\bibitem{journal:Pla46}
\textsc{Plackett, R.L.} and \textsc{Burman, J.P.} (1946). The design of optimum multifactorial experiments. \textit{Biometrika}, \textbf{33.4},  305-–325.

\bibitem{book:SAL04}
\textsc{Saltelli, A., Tarantola, S., Campolongo, F.} and \textsc{Ratto, M.} (2004). \textit{Sensitivity Analysis in Practice: A Guide to Assessing Scientific Models}. Wiley, England.

\bibitem{SAX79}
\textsc{Saxe, J.} (1979) Embeddability of weighted graphs in k-space is strongly np-hard. \textit{Allerton Conf. in Communications, Control, and Computing}, 480-–489.

\bibitem{journal:Sli02}
\textsc{Slijepcevic, S., Megerian, S.} and \textsc{Potkonjak, M.} (2002). Location errors in wireless embedded sensor networks: sources, models, and effects on applications. \textit{Mobile Computing and Communications Review}, \textbf{6.3}, 67–-78.

\bibitem{Tot05}
\textsc{Totaro, M.} and \textsc{Perkins, D.} (2005). Using statistical design of experiments for analyzing mobile ad hoc networks. \textit{MSWiM}, 159-–168.

\bibitem{Vad04}
\textsc{Vadde, K.} and \textsc{Syrotiuk, V.} (2004). Factor interaction on service delivery in mobile ad hoc networks. \textit{IEEE Journal on Selected Areas in Communications (JSAC)}, \textbf{22.7}, 1335–1346.

\end{thebibliography}


\end{document}