DOC PREVIEW
MTU CS 6461 - Analysis of dynamic sensor networks

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Analysis of dynamic sensor networks:power law then what?(Invited Paper)´Eric Fleury, Jean-Loup GuillaumeCITI / ARES – INRIAINSA de LyonF-69621 Villeurbanne FRANCEC´eline RobardetLIRIS / CNRS UMR 5205INSA de LyonF-69621 Villeurbanne FRANCEAntoine ScherrerCITI / COMPSYS – INRIAINSA de LyonF-69621 Villeurbanne FRANCEAbstract—Recent studies on wireless sensor networks (WSN)have shown that the duration of contacts and inter-contacts arepower law distributed. While this is a strong property of thesenetworks, we will show that this is not sufficient to describeproperly the dynamics of sensor networks. We will present somecoupled arguments from data mining, random processes andgraph theory to describe more accurately the dynamics withthe use of a random model to show the limits of an approachlimited to power law contact durations.I. INTRODUCTIONMobile devices equipped with wireless capabilities, whichenable new communication services, have encountered a fan-tastic growth in the last few years. Advances and miniaturiza-tion of micro-electronic devices have pushed the developmentof new fields of applications for wireless networks. Theincreasing popularity of a wide range of wireless devicesallows new paradigms and application classes.Scientific research has massed worldwide around these newchallenges presented by multi hop wireless networks. A broadspectrum of topics is under investigation. It covers researchin pure ad hoc networks, in hybrid wireless ad hoc networks,in wireless sensor networks (WSN), in SISes (spontaneousinformation systems) and in DTNs (delay-tolerant networks).A common characteristic of this large range of wirelessnetworks is that intermittent connectivity is the norm due toenvironmental dynamics and the intentional duty cycling ofwireless nodes. However, despite several years of intensiveresearch, a gap remains in terms of experimental aspects of insitu dynamic networks.In such ambient context where nodes will be spread aroundin the environment and/or on each user, it becomes possibleto route data on such network based on pairwise contactsbetween devices/users. Communication services based on suchnetwork, called also Delay Tolerant Networks (DTN), willdeeply rely on the mobility and on the characteristics of theunderlying networks. It appears crucial to better understandthe intrinsic characteristics of such dynamic radio networks;to be able to analyze and model interactions between individ-uals/devices, in order to propose secure methods and protocolssuitable for this context.Recently, Chaintrau et al. provide data traces of pairwisecontacts collected during the Infocom 2005 conference. Fromthis experimental approach their analysis shows long taileddistribution for the inter contact time (time between twotransfer opportunities for the same pair of devices) and theyclaim that “inter contact time distribution can be comparedto the one of power law”. As stated in [1], one can mark thepopularity of power law in 1999. Several papers [2]–[5] appearin leading journals (Nature, Science) and report independentlythat the distribution of degrees in “real” graph (WWW, InternetTopology) seems to follow a power law: the frequency ofnodes/web pages with connectivity k falls off as k−α.If we agree on the fact that studying the dynamics andevolution of large-scale dynamic networks is a fundamentaland difficult, but promising problem, one may have somedoubts about the generality of scale free networks and that“[...] nature has some universal organizational principles thatmight finally allow us to formulate a general theory of complexsystems” [6]. More precisely, finding a power law for somenetwork characteristic distribution is not so surprising andwhat do power law distribution really signify? One shouldkeep in mind that high variability does not necessarily implypower law. Moreover, characterizing a power law behavior isdone by inferring a fitting curve on a log-log plot. It appearsthat various kind of data can be approximated by drawingstraight lines on such log-log scale plots.The main purpose of this paper is to demonstrate that theso called power-law argument is not the ultimate one and thatit is worthy to study and analyze dynamic networks underseveral points of view in order to extract their characteristicsand behaviors. As stated above, power-law are “quite” easyto generate, that’s why we can find them “everywhere” andfinding such scale free networks does not imply any deepor fundamental knowledge on the intrinsic structure of thenetwork. A main contribution of this paper is that in orderto extract knowledge on dynamic networks, we introduce andpresent some coupled arguments from data mining, randomprocesses and graph theory to describe more accurately thedynamics with the use of a random model. We show thelimits of an approach limited to a power-law contact duration.We also emphasis the need of addressing interdisciplinaryissues since dynamic networks are becoming a central pointof interest, not only for engineers, computer scientists butalso for other domains, such as sociology, epidemiology, andstatistical physics. While far from complete, our results stayconsistent with two complementary goals: a crucial need ofreal data gathered from in situ test beds and fostering thedevelopment of precise tools in order to analyze data to enabletheoretical models to validate the ongoing research conductedin the various domains that touch on dynamic networks.The remainder of this article is organized as follows. Sec-tion II presents the three main approaches that we used inthis article: data mining, random processes and graph theoryand provides the basic background, including mathematicaldefinitions. Sections III and IV are dedicated to networkdynamics. In section III we study the evolution of the net-work by presenting the inter contact approach but we alsoapply basic metrics from graph theory and random process.Then, in section IV we introduce more complex metricsbased on Maximal Connected Subgraph (MCS) and on theirevolutions. This analysis is based on graph theory tools andon a data mining approach that reveals to be very efficientfor this kind of computation and analysis. In the section Vwe introduce a very simple random dynamical model fordynamic networks having a power law in their inter contactsequence. This models highlights the diversity of propertiesthat are needed to characterize dynamic networks. Our modelprovides insight into existing


View Full Document

MTU CS 6461 - Analysis of dynamic sensor networks

Documents in this Course
Tapestry

Tapestry

13 pages

Load more
Download Analysis of dynamic sensor networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Analysis of dynamic sensor networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Analysis of dynamic sensor networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?