Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimization Methods for the Localization of Distributed Wireless Sensor Networks
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Optimeringsmetoder för lokalisering av distribuerade trådlösa sensornätverk (Swedish)
Abstract [en]

The research topic of this master’s thesis is the localization of Wireless Sensor Networks (WSNs) which encounter signal ambiguities. These sensors are applied for the exploration of inaccessible environments, e.g. underground water systems. Within this context, sensors equipped with transceivers are employed in the environment of interest and measure the distance to each other by transmitting range impulses which are used to reconstruct their absolute positions. Thereby, each sensor transmits in a particular way, such that multiple range measurements which are received by a sensor can be distinguished. Since an accurate localization requires a great amount of sensors and the different transmission schemes are limited in practice, multiple sensors have to use the same scheme which is assigned to the sensors in a known way before they are deployed. Due to the non-unique schemes, it is not certain from which transmitter the signals, which are received by a sensor, originate. The aim of this thesis is to resolve these ambiguities in order to perform a localization of the sensors.

In order to capture the behavior of the WSN, a system model is developed which describes the movement of its entities and their measurements. A range measurement received by a sensor can have originated from different sensors, namely those whose transmit schemes match the range signal. These constraints restrict the possibilities of resolving the ambiguities which is translated into an independent set problem.

For a single time instant, the objective of resolving ambiguities is formulated as an optimization problem which aims at minimizing the probability of erroneously matching the non-unique range measurements to originating sensors. The resulting problem is known as minimum weighted independent set problem which is equivalent to binary linear programming and NP-hard in general. In order to efficiently obtain the optimum, an algorithm is developed which exploits the structure of the graph and results in a significant  reduction of complexity. The applied method relies on performing a clique-width tree decomposition.

As the sensor move over time, it is required to connect the localization outcomes of the different time instants whilst taking their movement model into account. A scheme is proposed which incorporates the outcomes of previous time instants as a priori knowledge. This routine requires the evaluation of probabilities given by sums with a great number of addends which is due to the range measurement ambiguities. These sums are crucial for the computational complexity of the method. Applying the introduced clique-width tree decomposition enables computing these sums efficiently, which algebraically translates to a sophisticated factorization.

 

Abstract [sv]

Ämnet för detta examensarbete är lokaliseringen av Wireless Sensor Networks (WSNs) som drabbas av signaltvetydigheter vilka tillämpas for utforskandet av otillgängliga miljöer, till exempel under-jordiska vattensystem. I denna kontext är sensorer utrustade med transceivers placerade i miljon av intresse och de mäter avståendet till varandra genom att sända avståndsimpulser, vilka används till att rekonstruera sensorernas absoluta position. På så vis kan flera avståndsmätningar som har mottagits av en sensor särskiljas eftersom varje sensor sänder på ett speciellt sätt.

Eftersom en korrekt lokalisering kräveren stor mängd sensorer och de olika sändningsschemana är begränsade i praktiken måste många sensorer använda samma schema, vilka är tilldelade till sensorerna i förväg på ett känt sätt innan de används. På grund av icke-unika scheman är det osäkert från vilken sändare signalerna kommer ifrån när de tas emot av en sensor. Syftet med detta examensarbete är att systematiskt lösa dessa tvetydigheter för att utföra lokalisering av sensorerna.

För att fånga beteendet av Wireless Sensor Network har en systemmodell utvecklats som beskriver rörelsen av enheterna och utbredningen av signalerna. En avståndsmätning mottagen av en sensor kan ha kommit från olika sensorer, nämligen dem vilkas sändningsscheman matchar avståndsimpulsen. Dessa villkor begränsar möjligheterna att lösa tvetydigheterna och de tolkas som en oberoende mängd problem i en graf.

För ett enstaka tidsögonblick är målet att lösa tvetydigheterna formulerat som ett optimaliseringsproblem som siktar mot att minimera sannolikheten att felaktigt matcha de icke-unika avståndsmätningarna från ursprungssensorerna. Det resulterande problemet är känt som ett minimal viktat oberoende mängdproblem vilket är ekvivalent med binär linjär programmering och NP-fullständighet.

För att erhålla optimum har en algoritm utvecklas som använder grafens struktur och resulterar i en signifikant reduktion av komplexiteten. Den tillämpade metoden använder sig av clique-width decomposition av grafen.

Eftersom sensorerna rör sig över tiden, måste lokaliseringsresultaten från de olika tidsögonblicken förknippas med sensorernas rörelsemodell. Ett schema föreslås som använder resultaten från tidigare tidsögonblick som a-priori kunskap. Denna rutin kräver beräkningar av sannolikheter givna av summor med ett stort antal termer på grund av mätningstvetydigheterna. Dessa summor är centrala för metodens beräkningskomplexitet. Tillämpandet av clique-width decomposition på grafen tillåter att effektivt beräkna dessa summor, vilket algebraiskt kan översättas till en sofistikerad faktorisering.

Place, publisher, year, edition, pages
2015.
Series
TRITA-MAT-E, 2015:73
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-175433OAI: oai:DiVA.org:kth-175433DiVA: diva2:868506
External cooperation
RWTH Aachen University, Institute for Communication Technologies and Embedded Systems (ICE)
Subject / course
Systems Engineering
Educational program
Master of Science in Engineering - Electrical Engineering
Supervisors
Examiners
Available from: 2015-11-11 Created: 2015-10-14 Last updated: 2016-01-30Bibliographically approved

Open Access in DiVA

No full text

By organisation
Optimization and Systems Theory
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 180 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf