Transcript Applications in Medical Care

ISMICT 07
Overview of Wireless Sensor Networks
Applications in Medical Care
The Second International Symposium on Medical Information
and Communication Technology
Presenter: Professor Carlos Pomalaza-Ráez
December 11, 2007
Topics
Overview of Medical Applications
Sensor Node Architecture
IEEE 802.15.4
B
1
3
1
1
F
1
2
2
0
1
4
Routing
Coverage
A
6
E
1
1
1
9
1
0
1
6
C
9
8
5
7
Localization
4 1 3
8
11
75
1
D2
Stage Model of the Medical Practice
 New and better medical devices
are continuously introduced to
detect vital signals and present
them in a suitable format for
healthcare givers
 The interpretation can be
regarded as a data compression
and data conformity process
 The physicians make a treatment
prescription based on the
patient’s medical history and
current clinical reports by
consulting the evidence-based
database, pharmaceutical
handbook and other resources
Y. Shieh, et al., “Mobile Healthcare: Opportunities and Challenges,” Proceedings of Sixth International
Conference on the Management of Mobile Business, July 9-11, 2007, Toronto, Ontario, Canada
Healthcare Wireless Network Expansion
 Each day more and more
equipment is going “wireless”
from pulse-oximeters to more
complex patient vital signs
monitors and ventilators
 Environments must scale from
a few clients to 100’s on a
single subnet
 External factors such as
nearby TV and radio stations
can affect overall
performance.
 Interoperability profiles and
standards are required to
ensure plug-and-play
operation in heterogeneous
environments
E. Sloane, et al., “Safety First! Safe and Successful Digital Network Wireless Medical Device
Systems,” 2006 HIMSS Annual Conference February, San Diego
IP Convergence
 Integration of data, voice, image , video on a single traffic network based on the Internet protocol
 Eliminates the maintenance of a parallel voice network
 Decreases considerably the expenses on phone calls and fax transmissions
 Interoperability of networks, applications and devices used in information technology
 Allows the reuse of the existing data-processing infrastructure
Wireless
phone
WiMax
PDA
Bedside PC
PACS
Server
Telephone IP
PC
Laptop
GSM
Wi-Fi
W-Fi
Access point
Camera Video
Application
servers
Biomedical
equipment
Scanner
RFID « Tag »
RFID reader
Mobile Devices






Facilitates the mobility of doctors, practitioners and caregivers
Allows access to patient information at any moment, everywhere and on real time
Improves automatic data gathering through barcode or RFID reading
Allows the immediate sharing of patient information and results
Improves the internal communication within the caregiver team and with the support staff
Helps to reduce paper
Wired network
Cellular
phones
Laptop
Hospital
systems
PACS
Radiology
Lab
Pharmacy
Etc.
Patient
record
Computer on
wheels
PDA
(Personnel digital assistant)
Tablet PC
Wireless router
(Wi-Fi)
Room Topology
Medical information collected
by sensors on the patient’s
body (WPAN) is displayed on a
bedside monitor
This information is also
transmitted to another hospital
location for remote monitoring,
e.g., a nurses’ station)
In case of emergency, when
the patient is moved from
his/her room to the intensive
care unit, these
communications need to be
maintained
D. Cypher, et al., “Prevailing over Wires in Healthcare Environments: Benefits and Challenges,”
IEEE Communications Magazine, pp. 56-63, April 2006
Radio frequency identification
 Facilitates the management of assets (wheel chairs, scanners, ambulatory equipment, etc)
 Improves patient localization and helps caregivers to provide services without delays
 Enhances the process of drug administration (identification, distribution, localization, returns and disposal)
 Facilitates the automatic data capture and the follow-up of blood and biological samples
Mobile reader
Pharmaceutical
product
management
Access
point
RFID
Server
Wallmounted
reader
Medical and chirurgical
equipment tracking
Bracelet
Fixed reader
Patient Identification
and tracking
Equipment localization
and tracking
Telemedicine




Utilization of different assets independent of their geographical location
Multidisciplinary collaboration
Facilitates the dissemination of medical knowledge to practicing doctors and medical students
Allows doctors in remote and rural areas to consult with specialists in urban areas
Specialist
Researcher
Patient
Doctor
Remote monitoring
 Reduce the number of patients transferred to urban hospitals
 Allows tele-consultation and tele-diagnosis including the option of obtaining opinions of distant experts
 Facilitates the patient remote monitoring with instantaneous data transmission for analyses and follow-ups
 Allows remote handling of medical equipment (tele-surgery) and direct action of the expert on the patient
 Improves coordination of first-responders workers during in the event of catastrophes or emergency cases
Mobile monitoring
platform
Data capture
Mobile device
GSM
GPRS
WiMax
Internet
Real-time patient
monitoring
Wireless Body Area Network
E. Jovanov, et al., “A wireless body area network of intelligent motion sensors for computer
assisted physical rehabilitation,” Journal of NeuroEngineering and Rehabilitation, 2005, 2:6
Wireless Body Area Network
The personal server can be implemented on an Internet-enabled PDA or
a 3G mobile phone, or a regular laptop of desktop computer. It can
communicate with remote upper-level services in a hierarchical type
architecture. Its tasks include:
 Initialization, configuration, and synchronization of WBAN nodes
 Control and monitor operation of WBAN nodes
 Collection of sensor readings from physiological sensors
 Processing and integration of data from the sensors
 Secure communication with remote healthcare provider
Wearable Monitoring Systems
Fabric electrodes have been used
to monitor EKG and respiratory
activity
M. Pacelli, et al., “Sensing Fabrics for Monitoring Physiological and Biomechanical Variables:
E-textile solutions,” 3rd IEEE-EMBS International Summer School and Symposium on Medical
Devices and Biosensors, Boston, Sept.4-6, 2006
Biomedical Measurements
S. Arnon, et al., “A Comparative Study of Wireless Communication Network Configurations for
Medical Applications,” IEEE Wireless Communications, pp. 56-61, February 2003
Wireless Technologies
Clinical Data vs Wireless Technologies
Biomedical Data
Type
Typical File Size
EKG recording
Electrical signal
100 kB
Electronic Stethoscope
Audio
100 kB
X-Ray
Still image
1 MB
30s of ultrasound image
Moving image
10 MB
Technology
Data Rate
Frequency Spectrum
GSM
9.6 kbps
900/1800/1900 MHz
GPRS
171.2 kbps
900/1800/1900 MHz
EDGE
384 kbps
900/1800/1900 MHz
3G/UMTS
2 Mbps
1885 MHz – 2200 Mhz
M. Fadlee, et al., “Bluetooth Telemedicine Processor for Multichannel Biomedical Signal
Transmission via Mobile Cellular Networks,” IEEE Transactions on Information Technology in
Biomedicine, pp. 35-43, March 2005
Framework for Medical Image Analysis
The remote medical image repositories communicate through different types of
network connections with the central computing site that coordinates the distributed
analysis.
V, Megalooikonomou, et al., “Medical Data Fusion for Telemedicine,” IEEE Engineering in
Medicine and Biology Magazine, pp. 36-42, September/October 2007
DICOM
The Digital Imaging and Communications in Medicine (DICOM) standard is created
by the National Electrical Manufacturers Association (NEMA) to aid the distribution
and viewing of medical images. DICOM is the most common standard for receiving
scans from a hospital.
A single DICOM file contains both a
header (which stores information about
the patient’s name, the type of scan,
image dimensions, etc), and all of the
image data
DICOM images can be compressed
both by the common lossy JPEG
compression scheme as well as a
lossless JPEG scheme
A single 500-slice MRI can produce a
68 MB image file
Transmission of DICOM Images
The time values represent the total time, i.e. computing time (compression
algorithm on each side of the communication link) plus the transmission time
H. Lufei, et al., “Communication Optimization for Image Transmission in Computer-Assisted Surgery,”
Proceedings of 2004 Congress of Neurological Surgeons, October 16-21, San Francisco, California
Activity Sensors
 They can be useful in monitoring patients
undergoing physical rehabilitation such
as after a stroke
 The Pluto custom wearable designed at
Harvard incorporates the TI MSP430
microprocessor and ChipCon CC 2420
radio
 Pluto can run continuously for almost 5
hours on a rechargeable 120 mAh lithium
battery
 It has a Mini-B USB connector for
programming and to recharge the battery
 The software runs under TinyOS
V. Shnayder, et al., “Sensor Networks for Medical Care,” Technical Report TR-08-05, Division
of Engineering and Applied Sciences, Harvard University, 2005.
Pulse Oximeter
 Non-invasive technology used to measure the heart rate (HR) and
blood oxygen saturation (SpO2)
 The technology used is to project infrared and near-infrared light
through blood vessels near the skin
 By detecting the amount of light absorbed by hemoglobin in the
blood at two different wavelengths the level of oxygen can be
measured
 The heart rate can also be measured since blood vessels contract
and expand with the patient’s pulse which affects the pattern of light
absorbed over time
 Computation of HR and SpO2 from the light transmission waveforms
can be performed using standard DSP algorithms
Pulse Oximeter
 Smiths Micro Power Oximeter Board
 Length: 39 mm
Width: 20 mm
Height: 5.6 mm
 6.6 mA at 3.3 V, typical power:22 mW
 Pulse range: 30-254 bpm
SpO2: 0 to 99%
 Data is transmitted from the oximeter
board at a rate of 60 packets per
second (5 bytes per packet)
 Minolta Pulsox-2
 Size: W69xH60xD28 mm
 Weight: approx. 70g (with 2 AAA
batteries)
Electrocardiograph (EKG)
 The most common type of EKG involves the connection of several
leads to a patient’s chest, arms, and leg via adhesive foam pads.
The device records a short sampling, e.g. 30 seconds, of the heart’s
electric activity between different pairs of electrodes
 When there is need to detect intermittent cardiac conditions a
continuous EKG measurement is used. This involve the use of a
two- or three-electrode EKG to evaluate the patient’s cardiac activity
for an extended period
 The EKG signal is small (~ 1mV peak-to-peak). Before the signal is
digitized it has to be amplified (gain > 1000) using low noise
amplifiers and filtered to remove noise
Electrocardiograph
 The P wave is associated with the contractions of the atria (the two
chambers in the heart that receive blood from outside)
 The QRS is a series of waves associated with ventricular contractions
(the ventricles are the two major pumping chambers in the heart)
 The T and U waves follow the ventricular contractions
Electrocardiograph
 IMEC has recently developed a wireless,
flexible, stretchable EKG patch for
continuous cardiac monitoring
 Placed on the arm or on the leg the same
system can be used to monitor muscle
activity (EMG)
 The patch includes a microprocessor, a 2.4
GHz radio link and a miniaturized
rechargeable lithium-ion battery
 The total size is 60x20 mm2
 Data is sampled between 250 and 1000 Hz
an continuously transmitted
 The battery has a capacity of 175 mAh
which provides for continuous monitoring
from one day to several days
EKG Signals
 Various sampling rates and
quantization levels are used
when EKG signals are
digitized
 In practice sampling
frequencies between 128 Hz
and 256 Hz are used
 The higher sampling rates and
bit rates, e.g. 16 bits, are used
to characterize EKG in
sufficient detail
Interoperability
There is need for intercommunication among medical devices and clinical
information systems. This has been accomplished with a number of medical
products. Infusion pumps and ventilators commonly have RS-232 ports, and these
devices can communicate with many physiological monitoring instruments.
Products to link medical equipment
and personal communication
devices exist as well
However, virtually all of these are
specialized applications—custom
interfaces unique to the two
devices being linked
To address the medical device
plug-and-play interoperability
problem, a single communications
standard is needed.
IEEE 1073.3.5 Project
 Transport standards associated with wireless data transport from IEEE
1073 point-of-care medical devices (POC) using personal area (WPAN),
local area (WLAN), wide area (WWAN), and other networks
 It will make specific recommendations on the use of WPAN, WLAN, and
WWAN wireless networks to facilitate medical data transport in various
healthcare settings
 Specifically, technology protocols will be recommended to facilitate plugand-play compatibility between (POC) medical devices and wireless
networks to an end server or attending healthcare professional
 Medical data may range from non-critical to critical parameters, and
expected quality of service (i.e., data throughput, latency, fidelity,
network coverage) and acceptable performance parameters
MEDICAL INFORMATION BUS (MIB)
 MIB is published by the IEEE as the IEEE 1073 standard and follows
the ISO OSI seven-layer communications model
 MIB is the name for a series of standards of connectivity between critical
care bedside medical devices and hospital computer equipment
 Examples of these devices are: ventilators, pulse oximeters, patient
monitors
 The heart of the MIB is the interface between the bedside
communications controller (BCC) and one or more device
communication controller (DCC)
 A medical device can function as both as BCC and DCC, i.e. a bedside
monitor can be a BCC connected to a ventilator and an infusion pump
DCCs, while at the same time it can be a DCC connected to a clinical
information system acting as BCC
MIB
MIB – Logical Interface
 ACSE: Association
control service
 ROSE: Remote
operation service
element
 CMDISE: Common
medical device
information service
element
 MDIB: Medical data
information base
HL7
 Health Level 7 (HL7) standard is
designed to enable different
health care applications to
exchange clinical and
administrative data
 The most recent version of the
HL7 specification uses XML
messaging as its foundation
 HL7 also allows the use of
trigger events, i.e. when a
patient’s EKG waveform is
available causes a request for
that observation data to be sent
to another information system
CodeBlue Infrastructure
 An ad hoc WSN Infrastructure for emergency medical care
 It is based on a publish/subscribe model for data delivery
 Designed to scale across a wide range of network densities an to operate
on a range of wireless devices
D. Malan, et al., “CodeBlue: An Ad Hoc Sensor Network Infrastructure for Emergency Medical Care,”
Intl. Workshop on Wearable and Implantable Body Sensor Networks, April 2004.
Architecture of a Sensor Node
Sensors Everywhere
Some current issues:
 There are already many deployed sensors
– Mobile phones
– Surveillance cameras
– GPS receivers
– Motion and light sensors
 How to organize them in networks
 How to retrieve, store, and index data from sensors
 Change the attention from “network” to “data”
 Combine data processing with data delivery
The Traditional WSN Myth
 The wireless sensor network
paradigm was a myth from the
late 1990s
 Usual “assumptions”:
– 1000s of homogeneous
“sensing only” nodes
– Mesh routing all nodes
 This market is marginal
Sink
 Luckily, the ideas and algorithms that were developed can be applied
to ubiquitous wireless applications
 Huge research and market potential
Convergent WSNs
 Convergent WSNs have
real potential
 Hierarchical part of other
networks such as B3G
 Ubiquitous embedded
devices go wireless
– Control & sensing
– Ubiquitous services
Convergent WSNs
 How do we integrate the Internet and Intranets with
sensor networks?
– Where is the intelligence?
– Heterogeneous protocol interfaces?
– Scalability and security are important issues
– Mobility support
 Gateways play an important role, as they communicate
with TCP/IP and sensor networks
– A proxy application often used to translate and shield
one level from another
Convergent WSNs
 Looking at the sales of uCs, there is a potential for
billions of networked devices – much larger than the
Internet itself
 Huge impact also on the core Internet
– IPv6 will be key to supporting convergent sensor
networks
– Intelligent data processing to reduce the network
traffic
Embedded Meets Wireless
 Microcontrollers are everywhere in embedded
systems
– appliances, watches, toys, cameras, industrial
control, mobile phones, sensors, cars, automation
 Microcontroller vs. microprocessor market
– 15 x more microcontroller units sold yearly
(8 billion)
– 20 billion vs 43 billion USD market by 2009
Embedded Meets Wireless
 Possibilities of wireless applications are endless
– Projected sales of 802.15.4 chips are 150 million units by
2009
 Embedded systems have special characteristics
 Academic community very computer science and protocol
driven, often ignoring
– Physical layer realities
– Embedded system operation
– Real-time capabilities
Device Architecture
 Microcontroller and program code
 Power supply
– Power management
– Renewable energy?
 Memory (RAM, FLASH)
 Sensors
 Actuators
 Communication
 Input/output
 Part of larger system?
Microcontroller
 Main processing units of embedded devices
 Special purpose and highly integrated
– Integrated RAM, ROM, I/O, peripherals
– Extremely good power to performance ratio
– Cheap, typically 0.25 - 10.00 USD
 Executes programs including embedded system control,
measurement & communications
– Usually time-critical requiring guarantees deadlines
– Real-time performance a must in most applications
• Pre-emptive scheduled tasks
• Queues and semaphores
MSP430
 Texas Instruments
mixed-signal uC
 16-bit RISC
 ROM: 1-60 kB
 RAM: Up to 10 kB
 Analogue
– 12 bit ADC & DAC
– LCD driver
 Digital
– USART x 2
– DMA controller
– Timers
ATmega AVR
 Atmel AVR family
 8-bit RISC
 RAM: Up to 4 kB
 ROM: Up to 128 kB
 Analogue
– ADC
– PWM
 Digital
– USARTs
– Timers
ATmega AVR
Current consumption
VCC = 3 V is:
Mode
Current
Active (4 MHz)
5.5 mA
Idle (4 MHz)
2.5 mA
Power-down
WDT enabled
25 µA
Power-down
WDT disabled
10 µA
WDT = Watchdog Timer
The dominating factors are
operating voltage and
frequency
The current consumption is a function of
several factors such as:
 operating voltage
 operating frequency
 loading of I/O pins
 switching rate of I/O pins
 code executed
 ambient temperature
Power Management
Power dissipation in CMOS systems modeled as
Ptotal  Pdyn  Pstat
2
P

f
V
Dynamic power depends on the switching behavior and
 dyn
the frequency of the circuit
Pstat V
2

Static power (also called leakage component) depends
only on the operational voltage
In the past the static power has been assumed as very small when
compared with Pdyn. This is no longer possible as the CMOS technology
is moving in the deep sub-micron range, e.g. 0.15 μm and smaller.
These devices have large leakage currents which increases the amount
of Pstat
Power Management
Dynamic voltage scaling (DVS) is a standard technique for
managing the power consumption of a system. In particular for
CMOS circuits the power consumption, P, is proportional to the
core voltage V and the frequency f,
Pdyn  f V 2
The number of clock cycles needed to complete a computation is
independent of the core frequency which means that the
execution time is inversely proportional to the frequency. The
total energy, E, is then proportional to the square of the voltage,
Edyn V 2
Dynamic Voltage Scaling
Implementing an effective DVS system requires:
 A variable power supply capable of a high voltage transition
rate and minimum transition losses
 A wide operational voltage range
 A power scheduler that effectively computes the
appropriate frequency and voltage levels needed to
execute the various tasks
Dynamic Voltage Scaling
The scheduler responsibilities include deciding when the
processor can reduce its power and by how much.
Its implementation assumes a preemptive operating system. This
is not possible or difficult to implement in the small operating
systems (OS) developed for microcontrollers used in WSN
applications.
These small OSs operate on an interrupt-driven policy and no
“overseeing” program knows what other parts are doing.
The implementation becomes even more complicated when the
application requires the use of a real-time operating system.
Dynamic Voltage Scaling
Experimental work on the effectiveness of DVS shows that:
 Static power consumption is a significant contributor, in
particular for the case of the controller memory
 The relationship between of power and the voltage and
frequency is not as simple as the equations above imply
 The best way to set the proper frequency and voltage is to
take measurements at run-time, e.g. while the application is
running
Dynamic Clock
Since Pdyn  f V an alternate way to manage the energy consumption
is to change the clock frequency. Typical applications do not require a
constant workload; they are event driven and are supposed to switch
between active and idle modes. Microcontrollers such as the TI MSP
430 have a flexible clock system which can facilitate energy saving
policies. This clock system provides for:
2
 Low clock frequency for energy conservation modes such as when in
an idle state and for time keeping
 High clock frequency for fast reaction to events and fast burst
processing capability
The low clock frequency is available via a low-power 32,768-Hz watch
crystal, the high clock frequency signal can be available from the onchip digitally controlled oscillator (DCO) or from a crystal.
Memory
 Random access memory (RAM)
– Included on-board in microcontrollers
– Often the most valuable resource
 Read-only memory (ROM)
– Usually actually implemented with NOR flash memory
 Flash
– Erasable programmable memory
– Can be read/written in blocks
– Slow during the write process
– Consumes power of course!
 External memory
– External memory supported by some microcontrollers
– Serial flash always supported
Flash Memory
Flash memory is very suitable to WSN applications because of its lowenergy consumption, small size, and capacity. There are different
types of flash memory depending on the underlying cell technology:
NOR – The read-only mode of NOR memories is similar to reading
from a common memory. NOR flash memories can be used as
execute-in-place memory (XIP). They are less dense that the NAND
memories and use more energy for erase and programming.
NAND – Cannot provide execute-in-place. They are accessed much
like block devices such as hard disks or memory cards. Associated
with each block are a few bytes that should be used for storage of
an error detection and correction block checksum. They are less
reliable than NOR memories thus the need of error correcting codes
(ECC)
Flash Memory
After writing a memory location in a flash memory it must be reset or
erased before it can be written again. This process is relatively slow
and energy consuming and can only be performed on fixed-sized
regions known as erase blocks.
Energy per bit (μJ)
Atmel NOR AT45DB041B (512 KB)
Hitachi MMC (NAND) HB28D032MM2 (32 MB)
Read
0.26
0.06
Write
4.30
0.58
Erase
2.36
0.47
From the perspective of energy consumption the number of write and
erase operations should be minimized and properly managed. The
proper choice of the flash technology plays an important role, NAND
technology is substantially more efficient that the NOR technology.
Common Interfaces
 Digital and analogue I/O
– Accessed by port and pin number (e.g. P1.3)
– Some pins are also connected to interrupts
 UART
– Asynchronous serial bus
– After level translation it is an RS232 bus
– Usually kbps up to 1 mbps
 SPI (serial peripheral interface)
– Synchronous serial bus
– Reliable with speeds of several Mbps
 I2C (inter-integrated circuit) bus
– 2-wire bus with data and clock
 Parallel bus
– Implemented with X-bit width
– X-bit address and clock signals
Transceivers
 Modern embedded communications chips are transceivers: they
combine half-duplex transmission and reception.
 Transceivers integrate varying functionality, from a bare analogue
interface to the whole digital baseband and key MAC functions.
Relevant Transceiver Characteristics
 Level of digital integration
 Power consumption and efficiency
– Transition speeds and consumption
– Levels of sleep
 Carrier frequency and data rate
 Modulation
 Error coding capabilities
 Noise figure and receiver sensitivity
 Received signal strength indicator (RSSI)
 Support for upper layers
 Data and control interface characteristics
RFM TR1000






Proprietary radio at 916 MHz
OOK and ASK modulation
30 kbps (OOK) or 115.2 kbps (ASK) operation
Signal strength indicator
Provides bit interface
Not included:
– Synchronization
– Framing
– Encoding
– Decoding
Current Consumption Characteristics
Operating voltage: 2.2 – 3.7 Vdc
Sleep
Tx
Rx
0.7 uA
12 mA
3.8 mA
CC2420




IEEE 802.15.4 compliant radio
2.4 GHz band using DSSS at 250 kbps
Integrated voltage regulator
Integrated digital baseband and MAC functions
– Clear channel assessment
– Energy detection (RSSI)
– Synchronization
– Framing
– Encryption/authentication
– Retransmission (CSMA)
Current Consumption Characteristics
Operating voltage: 2.1 – 3.6 Vdc
Sleep
Idle
Tx
Rx
20 μA
426 μA
8.5 – 17.4 mA
18.8 mA
Power Consumption
 To arrive to an energy efficient design all the components of a
WSNs have to be taken into account, in particular how they interact
with each other. An isolated energy optimization in a subsystem
might not yield the overall expected savings.
 Power output level (transceiver)
– Limited savings effect
– Optimal power difficult
– Must be considered globally
 Transition times
– Each transition costs
– Power equal to RX mode
– Should be accounted for
Power Consumption
These numerical values suggest
that in order to minimize the
energy consumption there is not
need of a fine power control
mechanism since the power
used does not change
significantly for a large range of
RF output power levels.
Output power control however cannot be completely ignored. In a
multiple Tx and Rx scenario the power of the transmitted signal has
substantial effect on the network topology and consequently in related
issues such as multiuser interference and end-to-end delay and
throughput.
Power Consumption
Transition times between different transceiver modes need also to be
taken into account. During wake-up time and the turn-around times (from
Tx to Rx and vice versa), the radio consumes as much power as during a
receive mode.
Power Consumption
Pavg 
1
PRxTwk up  PRx ( N TxTTxup  N RxTRxup )  PTxTTx  PRxTRx  PidleTidle  PsleepTsleep 
TF
Wakeup Time Effects
 The amount of time and power needed to wake-up (start-up) a radio
is not negligible
 When start-up energy consumption is taken into account the energy
per bit requirements can be significantly higher for the transmission
of short packets than for longer ones
TR 1000 (115kbps)
60
Ebit ( pJ )
50
40
30
20
10
0
10
100
1000
Packet Size (bits)
10000
Sensors & Actuators
 Sensors measure real-world phenomena and convert them to
electrical form
– Analogue sensors require an ADC
– Digital sensors use e.g. I2C or SPI interfaces
– Human interface can also be a sensor (button)
 IEEE 1451 standard becoming important
– Transducer interface to networks, systems, and instruments
– Defines standard interfaces and autoconfiguration
– Also some protocol specifications
 Actuators convert an electrical signal to some action
– Analogue and digital interfaces both common
– A motor servo is a good example
Real-time Operating Systems
 Operating system manages hardware and software computer
resources
 Embedded systems have pre-defined tasks
– Designed to optimize size, cost, efficiency etc.
 Real-time
– Real-time OS provides tools to meet deadlines
– Pre-emptive, queues, semaphores
 Concurrency
– Execution flows (tasks) able to run simultaneously
– Threads and processes
 Sockets and APIs
Real-time Issues
 Wireless embedded systems usually are real-time
– Watch, robot, building sensor, control node
 A RTOS only facilitates real-time system creation
– Still requires correct software development
 RTOS is not necessarily high performance
– Can meet general system deadlines (soft real-time)
– or deterministically (hard real-time)
 Deadlines can be met using
– Specialized pre-emptive scheduling algorithms
– Proper inter-task design & communication
– Semaphores and queues to avoid racing
Real-time Issues
Task1
Task2
Task3
Unlock
resource A
Lock
resource A
Task1
T1
T2
TN
Task2
Task1
Task3
Task2
Task3
T1
T2
TN
Try access
resource A
time
Concurrency
 Concurrency occurs when two or more execution flows
run simultaneously
 It introduces many problems such as
– Race conditions from shared resources
– Deadlock and starvation
 OS needs to coordinate between tasks
– Data exchange, memory, execution, resources
 There are two main techniques
– Process based
• CPU time split between execution tasks
– Event based
Concurrency
 Process based
 Event based
Programming Interfaces
 Application Programming Interface
– Need to be well planned, especially in embedded systems
– APIs to hide hardware specifics
– API to the protocol stack
– API to middleware components
 Sockets
– Software construct allowing communications between hosts or
processes
– The BSD Socket API the most common network programming
construct
– Used in NanoStack for accessing the protocol stack
OS Examples
 Example embedded operating systems
– Contiki (www.sics.se/~adam/contiki)
– FreeRTOS (www.freertos.org)
– TinyOS (www.tinyos.org)
– Ambient RT (www.ambientsystems.com)
– and thousands of others...
 For higher powered MCUs (e.g. ARMs)
– VX Works
– Microcontroller Linux
– Windows CE
– Symbian
IEEE 802.15.4
IEEE 802.15.4
Standard for home networking, industrial control and building automation.
It defines the physical layer (PHY) and the MAC sublayer specifications
for supporting simple devices that consume minimal power and operate
in the personal operating space of 10 meters.
Main characteristics
 Data rates of 250 Kb/s, 40 Kb/s, and 20 Kb/s
 Star or peer-to-peer operation
 Support for low latency devices
 CSMA-CA channel access
 Low power consumption
IEEE 802.15.4
Operating Frequency Bands
IEEE 802.15.4
Parameters
Transmit Power
 At least 1 mW
Transmit Center Frequency Tolerance
 ±40 ppm
Receiver Sensitivity
 -85 dBm @ 2.4 GHz band
 -92 dBm @ 868/915 band
RSSI Measurements
 Packet strength indication
 Clear channel assessment
IEEE 802.15.4
Frequency Bands and Data Rates
WLANS and WPANS
ZigBee uses IEEE 802.15.4 services and adds network construction (star networks,
peer-to-peer networks, cluster tree networks), security, application services, etc.
IEEE 802.15.4
Device Classes
 Full function device (FFD)
– Any topology
– Network coordinator capable
– Talks to any other device
 Reduced function device (RFD)
– Limited to star topology
– Cannot become a network coordinator
– Talks only to a network coordinator
– Very simple implementation
IEEE 802.15.4
Star Topology
PAN
Coordinator
Master/slave
Full function device
Reduced function device
Communications flow
IEEE 802.15.4
Peer-to-Peer Topology
Point to point
Full function device
Cluster tree
Communications flow
Combined Topology
Clustered stars - for example,
cluster nodes exist between rooms
of a hotel and each room has a
star network for control.
Full function device
Reduced function device
Communications flow
IEEE 802.15.4
Optional Superframe Structure
IEEE 802.15.4
MAC Frame Structure
4 Types of MAC Frames:
• Data Frame
• Beacon Frame
• Acknowledgment Frame
• MAC Command Frame
Network Layer
Routing
Network Layer
Basic issues:
Application
 Power efficiency
Transport
 Data centric – The nature of the data determines the traffic
Network
flow
Data Link
 Publish/subscribe paradigm
 Data aggregation – To manage the potential implosion of
Physical
traffic because of the data centric routing
 Rather than conventional node addresses, use attributebased addressing, e.g. “region where humidity is below
5%”
 Localization systems, i.e. ability of the nodes to establish
position information
 Internetworking with external networks via gateway or
proxy nodes
Data Centric
 In WSNs applications the identity of the node is not important
compared with the information being reported
 The same event could be sensed and reported by several nodes,
from the application point of view is of no concern which of these
nodes is reporting the data
 The fact that the data is the center of attention is what makes for a
data-centric networking
 Data centrality brings in different networking architectures such as
data-centric addressing and data fusion and aggregation
 These architectures also allowed for improved energy efficiency
since they scale better by being implementable using mainly local
information about the direct neighbors
Data Centric
 Sensor nodes advertise sensed data and wait for a request from the
interested nodes
Flow of the advertisement
Data Aggregation
 Data coming from multiple sensor
nodes are aggregated when they
reach a common routing or relaying
node on their way to the sink
 Aggregation takes place if the data
arriving the common node have
same attributes of the phenomenon
being sensed
Phenomenon being sensed
Routing
Phenomenon
being sensed
Data aggregation
takes place here
Sink
Multihop routing is common due to limited transmission range
Some routing issues in WSNs
•
•
•
•
•
Limited node mobility
Power aware
Irregular topology
MAC aware
Limited buffer space
Publish/Subscribe
Meets the need to be able to express the need for certain data and the
delivery of the data
 A node interested in a given kind of data can subscribe to it
 Any node can publish data, along with information about it
 Upon publication of some type of data all subscribers to that kind of
data are notified
 An very important issue is the use of appropriate “data descriptors”
that are used to match publications and subscriptions
 The content-based publish/subscribe approach is a naming scheme
that allows to formulate the matching conditions between
subscriptions and publications
Routing
Problem – How to efficiently route:
 Data from the sensors (or publishers) towards the sink (or subscribers) and,
 Queries and control packets from the sink (or subscribers) towards the sensor
nodes (or publishers)
Flooding
Flooding is a very simple technique that can be used to disseminate
information across a network. Each node sends an incoming packet to
all its neighbors and thus the packet is sure to arrive its intended
destination. It has severe drawbacks such as,
 Implosion – Duplicated messages are sent to the same node
 Overlap – Two or more nodes share the same observing region,
they may sense the same stimuli at the same time. As a result,
neighbor nodes receive duplicated messages
 Resource blindness – Not take into account the available energy
resources. A promiscuous routing technique such as flooding
wastes energy unnecessarily
Gossiping
 A variation of flooding attempting to correct some of its drawbacks
 Nodes do not indiscriminately broadcast but instead send a
packet to a randomly selected neighbor who once it receives the
packet it repeats the process
 It is not as simple to implement as the flooding mechanism and it
takes longer for the propagation of messages across the network
Flooding and Gossiping are variations of routing methods that try
to avoid the use of the routing tables that have been used
extensively for routing in conventional Ad-Hoc networks
Randomized Forwarding
A key parameter in gossiping-based routing algorithms is the
probability with which a node retransmits a newly incoming
message. It has been shown(†) that there is a critical probability
value below which gossip is not effective and the message reaches
a small number of nodes.
For larger probability values that the critical threshold the message
reaches most if not all of the nodes in the network.
Gossiping then has a bimodal behavior with the critical threshold
value between 0.6 and 0.8. By exploiting this behavior the gossip
protocol uses 35% fewer messages than flooding.
(†) Z. Haas, J. Halpern, and L. Li, “Gossip-Based Ad Hoc Routing”, IEEE/ACM Transactions on
Networking, Vol. 14, No. 3, pp. 479-491, June 2006
Behavior on a 20x50 grid
Behavior on a 20x50 grid
Behavior on a 20x50 grid
Routing
In addition to the concepts of data aggregation and data
centrality, it is important to identify the nature of the WSN traffic,
which will depend on the application.
Assuming a uniform density of nodes, the number of
transmissions can be used as a metric for energy consumption.
Since receiving a packet consumes almost as much energy as
transmitting a packet it is also important that the MAC protocol
limits the number of listening neighbors in order to conserve
energy.
Routing
If N is the number of nodes, Q the number of queries, and E the
number of events, and some type of flooding mechanism is being
used then:
 If the number of events is much higher than the number of queries
it is better to use some type of query flooding since the number of
transmissions is proportional to N*Q which is much less than N*E
 If the number of events is low compared with the number of
queries it is better to use some type of event flooding since now
N*E is much less than N*Q
 In both cases it is assumed that the “return path” (for the events or
the queries) is built during the flooding process
 Other underlying routing mechanisms are recommended if the
number of events and queries are of the same order
A Data-Centric Routing
SPIN – Sensor Protocols for Information via Negotiation(†) Attempts to
correct the major deficiencies of classical flooding, in particular the
indiscriminate flow of packets with the related energy waste
 SPIN messages
 ADV- advertise data
 REQ- request specific data
 DATA- requested data
 Resource management
 Nodes decide their capability
of participation in data
transmissions
(†)
ADV
A
B
REQ
A
B
DATA
A
B
W. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information Dissemination in Wireless Sensor
Networks,” Proc. 5th ACM/IEEE Mobicom Conference, Seattle, WA, August, 1999.
SPIN
A mechanism developed for the case where the number of queries is higher
than the number of events.
 Use information descriptors or meta-data for negotiation prior to
transmission of the data
 Each node has its own energy resource manager which is used to adjust
its transmission activity
 The family of SPIN protocols are:
 SPIN-PP – For point-to-point communication
 SPIN-EC – Similar to SPIN-PP but with energy conservation heuristics
added to it
 SPIN-BC – Designed for broadcast networks. Nodes set random
timers after receiving ADV and before sending REQ to wait for
someone else to send the REQ
 SPIN-RL – Similar to SPIN-BC but with added reliability. Each node
keeps track of whether it receives requested data within the time limit,
if not, data is re-requested
SPIN-BC
It
Sensor
sends
broadcasts
meta-data
data
toitself
neighbors
A
Neighbor
node
senses
sends
something
a REQ
listing
“interesting”
of the
data
The
Neighbors
process
aggregate
repeats
data
across
andall
broadcast
the
network
it would likemeta-data
to acquire
(advertise)
ADV
REQ
DATA
SPIN-BC
Advertise meta-data
Advertise
Send data
Send data
I am tired
Send
I need to
sleep …
data
Advertise
meta-data
Advertise
Send
data
Request
Nodes dodata
need
to
Requestnot
data
participate in the
process
Request data
SPIN
 Pros
– Energy – More efficient than classic flooding
– Latency – Converges quickly
– Scalability – Local interactions only
– Robust – Immune to node failures
 Cons
– Nodes always participating
– Need of and adequate MAC layer to support an efficient
implementation. The simulation analysis uses a modified
802.11 MAC protocol
Directed Diffusion(†)
A mechanism developed for the case where it is expected that the
number of events is higher than the number of queries
 Is data-centric in nature
 The sink propagates its queries or “interests” in the form of
attribute-value pairs
 The interests are injected by the sink and disseminated
throughout the network. During this process, “gradients” are set at
each sensor that receives an interest pointing towards the sensor
from which the interest was received
(†) C. Intanagonwiwat, R. Govindan, D. Estrin, and J. Heidemann “Directed Diffusion for Wireless Sensor
Networking,” IEEE/ACM Trans. on Networking, February 2003
Directed Diffusion
 This process can create, at each node, multiple gradients
towards the sink. To avoid excessive traffic along multiple
paths a “reinforcement” mechanism is used at each node
after receiving data, e.g. reinforce:
 Neighbor from whom new events are received
 Neighbor who is consistently performing better than
others
 Neighbor from whom most events received
 There is also a mechanism of “negative reinforcement” to
degrade the importance of a particular path
Directed Diffusion
Gradient
represents
both
direction
towards
data
matching
Uses
application-aware
communication
primitives
This
Consumer
Nodes
The
process
choice
diffuse
of sets
of
data
path
the
up
initiates
interest
gradients
is made
interest
towards
locally
in the
inproducers
at
network
data
every
with
node
tovia
certain
draw
afor
Every
route
has a probability
ofcost
being
chosen
Probability
 1/energy
Collect
energy
metrics
along
the way
and status
of demand
with
desired
expressed
terms
of
namedupdate
data rate
sequence
events
matching
every
ofin
attributes
local
packet
the
interactions
interest
Four-legged
animal
Source
Sink
Directed Diffusion
Reinforcement
andtolerance
negative to
reinforcement
used
Has built-in
nodes moving
to converge
to range
efficient
out of
ordistribution
dying
Source
Sink
Directed Diffusion
 Pros
– Energy – Much less traffic than flooding. For a network of size
N the total cost of transmissions and receptions is O(n N )
whereas for flooding the order is O (nN )
– Latency – Transmits data along the best path
– Scalability – Local interactions only
– Robust – Retransmissions of interests
 Cons
– The set up phase of the gradients is expensive
– Need of and adequate MAC layer to support an efficient
implementation. The simulation analysis uses a modified
802.11 MAC protocol
Geographic Routing
Geographic routing protocols assume:
 All nodes know their geographic location
 Each node knows its 1-hop neighbors
 Destination is a node with a given location
 Each packet can hold a limited amount of information as
to where it has been in the network
Geographic Forwarding
Greedy Approach
Select the neighbor geographically closest to the destination and
forward the data to that neighbor
Geographic Forwarding
Greedy Approach
Problem: It can get stuck in a local minima
Geographic Forwarding
When the connectivity between the nodes can be modeled as unit
graphs, i.e. a node is always connected to nodes within a fixed nominal
range and never connected to nodes outside this range, then
algorithms have been developed to escape from a local minima†.
† B. Karp , H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the 6th annual
international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, USA
Geographic Forwarding
For the case of a unit disk graph the greedy algorithm failure can be
illustrated in the following example:
A is closer to Y than B or C
and thus it will not forward
the packet to either of
them
† B. Karp , H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the 6th annual
international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, USA
Geographic Forwarding
A solution is to have a “perimeter” forwarding which attempts to route
the packet around the “void”.
To guarantee
perimeter forwarding
it is necessary that
the graph G that
represents the
network is “planar”,
i.e., no two edges
should intersect each
other
Planarized Graphs
Remove some edges so that the remaining graph is a connected planar graph
Planarized Graphs
Relative Neighborhood
Graph (RNG) – The edge
XY is introduced if the
intersection of circles
centered at X and Y with
radius the distance d(x,y) is
free of other nodes
Gabriel Graph (GG) – The
edge XY is introduced if no
other node is present within
the circle whose diameter is
d(x,y)
RNG and Gabriel graphs can be found in a distributed fashion
Routing Without Location Information
 Location information is not available, e.g. too expensive
 What are then the options to still have some type of geographic routing?
 One option is to assign “virtual” coordinates† to each node and then apply a
standard geographic routing algorithm
 The virtual coordinates do not need to be an accurate representation of the
actual location of the nodes, however they should preserve the existent
connectivity among the nodes
 It is also desirable to be able to compute the virtual coordinates using only
local connectivity information, i.e., each node knows about its neighbors
† A. Rao, C. Papadimitriou , S. Shenker, I. Stoica, “Geographic routing without location information,” Proceedings of the
9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
Routing: Virtual Coordinates
Case when the perimeter nodes and their location is known
 All non-perimeter nodes can determine their coordinates through an
iterative relaxation procedure
 Nodes will tend to move towards the perimeter nodes
Routing: Virtual Coordinates
 Perimeter nodes do not change their coordinates
 Non-perimeter nodes update their coordinates through
multiple iterations
 In each iteration, a node takes its coordinates as the
average coordinates of its neighbors
(i) 10 iterations
(ii) 100 iterations
(iii) 1000 iterations
Routing without Embedding the Link
Connectivity in a Plane†
 Still use virtual coordinates
 Divide the problem into computing a global topology and a local
routing mechanism
 Global topology estimation
– Provides information about connected components and holes in the
network
– The whole field is partitioned into tiles
– The assumed stable topology allows for proactive routing
 Within each tile the sensor distribution is expected to be “uniform”
and greedy forwarding using local coordinates can be used
 Local routing uses reactive protocols based on local connectivity
† Q. Fang, J. Gao, L.J. Guibas, V. Silva, and L. Zhang, “GLIDER: Gradient Landmark-based Distributed Routing
for Sensor Networks,” INFOCOM 2005.
GLIDER
 Select a set of landmarks
 Construct Landmark Voronoi
Complex (LVC)
 Construct Combinatorial
Delaunay Triangulation (CDT)
graph on landmarks
Voronoi Diagrams
Let P be a set of n distinct
points in the plane
The Voronoi diagram of P is
the subdivision of the plane
into n cells, one for each
point
A point q lies in the cell
corresponding to a point pi
 P if and only if
Euclidean_Distance(q, pi ) < Euclidean_Distance(q, pj ), for
each pi  P, j  i
Delauney Triangulation
It is the dual graph of the
Voronoi diagram
If one draws a line between
any two points whose
Voronoi domains touch
A set of triangles is
obtained, known as the
Delaunay Triangulation
No point in P is inside the
circumcircle of any triangle in a
Delauney Triangulation
GLIDER: Routing
 Global
The Combinatorial Delaunay graph D(L) encodes global connectivity
information that is accessible to every node for proactive route
planning on tiles
 Local
High-level routes on tiles are realized as actual paths in the network
by using reactive protocols
Transport Layer
Transport Layer
TCP variants developed for traditional wireless networks are not
suitable for WSNs where the notion of end-to-end reliability has
to be reinterpreted,
 Many more senders (the sensors) than destinations
 For the same event there is a high level of redundancy or
correlation in the data collected by the sensors, i.e. there is no
need for end-to-end reliability between individual sensors and
the destination, but instead between the event and the
destination
Application
Transport
Network
Data Link
Physical
 There is still need of end-to-end reliability between the sink and individual
nodes for situations such as retasking or reprogramming
 The protocols developed should be energy aware and simple enough to be
implemented for the low-end type of hardware and software of many WSN
applications
Transport Layer
Coverage
An important issue in sensor networks is the one of reliability. An aspect
of this issue is the one of detection reliability, i.e. whether the events
that the network is supposed to detect can be detected.
This means that the locations where events can occur are within the
sensing range of at least one node. The coverage problem deals with
the required node density and related topics.
Once the event has been detected the corresponding data must be
reliable reported to one or more sink nodes, which can be more than
one hop away. This translates into the need of a reliable transport
protocol.
Coverage
The Art Gallery Problem
Place a (the minimum?) number of cameras such that every point in
the art gallery is monitored by at least one camera
k-Coverage
Given a set of sensors S={s1, s2,…, sn} in a 2-D area A. Each sensor
has a sensing range ri, i.e., it can monitor any point that is within a
distance ri from si . A location in A is said to be k-covered it is within at
least k sensors’ sensing ranges.
Worst Case Coverage
Maximal Breach Path
It is a path through a sensor network that has the largest minimum
distance to any sensor node.
Given a sensor field for which the location of each sensor node si is
known, and given the location of the initial (I) and final (F) points the
problem is then to identify a path between I and F with the lowest
operability, i.e., the maximal breach path. For any point on this path, the
distance to the closest sensor is maximized.
By construction, the Voronoi diagram contains this path since the line
segments in the Voronoi diagram maximize the distance from the
closest nodes.
Worst Case Coverage
Maximal Breach Path Algorithm†
 Create a node for each vertex in the Voronoi diagram
 Create an edge for each line segment in the Voronoi diagram
 Assign the edge with its minimal distance from the closest sensor as its
weight
 Perform a Binary-Search and Bread-First-Search
 During each step of the Binary Search, check to see if a path exists
using only edges with weights larger than the specified search criteria
(breach_weight)
 If a path exists:
•
Increase breach_weight, and repeat the search
 If no path exists:
•
Reduce breach_weight to consider edges with lower weights
(†) S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivastava, “Coverage Problems In Wireless Ad-hoc Sensor
Networks”, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001.
Worst Case Coverage
Maximal Breach Path
I
F
Best Case Coverage
Maximal Support Path
It is a path through a sensor network that has the smallest maximum
distance to the sensor set.
Given a sensor field for which the location of each sensor node si is
known, and given the location of the initial (I) and final (F) points the
problem is then to identify a path between I and F with of maximal
support. For any point on this path, the distance to the closest sensor is
minimized.
By construction, the Delauney triangulation produces triangles that have
minimal edge length among all possible triangulations, therefore the
maximal support path must lie on the lines of the Delauney triangulation
of the sensors in S
Worst Case Coverage
Maximal Support Path Algorithm†
The algorithm used is exactly the same as for Maximal breach path,
with the following changes:
 The Voronoi diagram is replaced by the Delaunay triangulation as the
underlying geometric structure
 The edges in graph G are assigned weights equal to the length of the
corresponding line segments in the Delaunay triangulation
 The search parameter breach_weight is replaced by the new parameter
support_weight
support_weight is now an upper bound on all the edge weights that lie on the
maximal support path, and there must exist at least one edge with weight
equal to support weight
(†) S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivastava, “Coverage Problems In Wireless Ad-hoc Sensor
Networks”, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001.
Best Case Coverage
Maximal Support Path
I
F
Localization
Localization
Location necessary in order for sensed data to be meaningful e.g. forest
fire detection
Location information is taken for granted in many network designs, e.g.
geographic routing
Equipping each node with GPS is not always feasible due to power
constraints and other limitations inherent to sensor networks
Nodes can often measure their distances to nearby nodes, e.g. ultrawideband ranging
Localize using inter-node distances
?
Localization ?
A network in the plane
?
?
Anchors are nodes whose positions are known
Anchor positions from GPS or manual configuration.
The distances between some nodes are known
?
?
The network localization problem is to determine the positions of all the nodes
The network is localizable if there exists exactly one position in the plane
corresponding to each non-anchor node so that all known inter-node distances are
satisfied
A node is localizable if its position is uniquely determined by the known inter-node
distances and anchor positions
Localization
The localization problem is solvable if and only if the network is
localizable
The network localization problem is NP-Hard
Even assuming exact distance measurements, there is currently no
algorithm that can localize a large class of localizable networks without
requiring high connectivity while giving correctness guarantees
When distance between nodes are used in a localization problem the
approach is called lateration; when angles between nodes are used
the approach is called angulation
Multilateration
Base Station 1
u
Base Station 3
Base Station 2
 Base stations advertise their coordinates & transmit a reference
signal
 Node uses the reference signal to estimate distances to each of the
base stations
 Distance measurements are noisy
Problem Formulation
 Need to minimize the sum of squares of the residuals
f u ,i
2
2
ˆ
ˆ
 ru ,i  ( xi  xu )  ( yi  yu )
 The objective function is
F ( xu , yu )  min
f
2
u ,i
 This a non-linear optimization problem. There are many ways to
solve (e.g. gradient descent methods)
Collaborative Multilateration
 All available measurements are used as constraints
Known position
Unknown position
 Solve for the positions of multiple unknowns
simultaneously
 This is a non-linear optimization problem!
Problem Formulation
f 2,3  R2,3  ( x2  xˆ3 ) 2  ( y2  yˆ 3 ) 2
1
5
f 3,5  R3,5  ( xˆ3  x5 ) 2  ( yˆ 3  y5 ) 2
f 4,3  R4,3  ( xˆ4  xˆ3 ) 2  ( yˆ 4  yˆ 3 ) 2
f 4,5  R4,5  ( xˆ4  x5 )  ( yˆ 4  y5 )
2
3
2
f 4,1  R4,1  ( xˆ4  x1 ) 2  ( yˆ 4  y1 ) 2
4
6
2
The objective function is
F ( xˆ3 , yˆ3 , xˆ4 , yˆ 4 )  min
2
f
 i, j
Can be solved using iterative least squares
Estimating Distances - RSSI
Since every sensor node has a radio one way to estimate distances is to
transmit a signal of known strength and then use the signal strength of the
corresponding received signal and the path loss coefficient to estimate distance.
In theory the energy of a radio signal diminishes with the square of the distance
from the signal’s source. A more realistic assumption is to use path loss
coefficient
α and compute the received power as,
PTx
PRx  c 
d
cPTx
d 
PRx
α typically varies† between 2 and 5, depending on
several parameters such as the nature of obstacles,
carrier frequency, etc.
A major drawback of this model is that assumes that the
behavior is the same in all directions and thus the
connectivity between nodes is of a disk type nature.
† S.Y. Seidel, T.S. Rappaport, “914 Mhz Path Loss Prediction Models For Indoor Wireless Communications
in Multifloored Buildings”, IEEE Transactions on Antennas and Propagation, February 1992.
Connectivity Over Space†
A single transmitter (RFM TR 1000) is located at (6,6) in a 12x 14 grid of 147 nodes. All
nodes are identically oriented on a tennis court with 2-foot spacing.
† C. Whitehouse, “The Design Of Calamari: An Ad-hoc Localization System for Sensor
Networks”, Master’s thesis, University of California at Berkeley, 2002.
Radio Hop Count
If two nodes can communicate by radio their distance from each other is less
than R (the maximum radio range). This type of local connectivity can be used
to compute inter-node distances.
A very simple approximation would be that if the hop count between two
nodes si and sj is hij then the distance between si and sj , dij , is less than
R*hij. A better estimate is one takes into account the expected number of
neighbors, nlocal. The distance covered by one radio hop is then†
n
1  local  cos1 ( t ) t

nlocal
d hop  R1  e
 e  
1

1t 2 


dt 

and dij ≈ hij*dhop
† L. Kleinrock and J.A. Silvester, “Optimum Transmission Radii For Packet Radio Networks or Why
Six is a Magic Number”, In IEEE National Telecommunications Conference, December 1978.
Examples of Hop Count
hAC = 4, unfortunately, hBD is also four, due to an obstruction in the
topology
Estimating Distances
 Time of arrival (ToA)
– Use time of transmission, propagation speed, time of arrival to compute
distance
– Problem: Exact time synchronization
 Time Difference of Arrival (TDoA)
– Use two different signals with different propagation speeds
– Example: ultrasound and radio signal
• Propagation time of radio negligible compared to ultrasound
– Compute difference between arrival times to compute distance
– Problem: Calibration, expensive/energy-intensive hardware
Packet-Level Localization
An Experiment†
Motivation: Is it possible to learn about a node’s position by observing
the packet statistics?
Imagine an scenario where a mobile sink traverses an area of
stationary sensor nodes following different routes. Is it possible to
learn about the sink’s position if it traverses the same area many
times?
Assume also that the nature of the scene does not change, e.g., the
obstacles are the same or the way they behave is similar from one
instance to the other.
† T. L. Hemminger, D. R. Loker, and C. Pomalaza-Ráez, “A Neural Method for Identifying Transmission
Source Locations”, Proc. IEEE International Symposium on Personal, Indoor and Mobile Radio
Communications, Helsinki, Finland, September 2006.
Experimental Testbed
 IEEE 802.11 technology (Cisco Aironet)
 Multiple stationary nodes (clients)
 One mobile node (server)
 Mobile node broadcasts packets
 Stationary nodes record signal and packet statistics
 TCP network connection between the server and each client
 Diagnostic utility software provided with the wireless adapter cards
collect packet statistics
 Of the 42 statistics provided by this software, it was determined that
13 provided significant variability to be pursued as candidates in
determining the server location
Data Reduction
Trend analysis of the collected data revealed a large amount of correlation
between the variables and a matrix of rank 6, i.e., there was a strong level of
dependence between the variables. A eigenvalue, eigenvector statistical
analysis was used to reduce the dimensionality of the data and retain the most
relevant parameters.
Receive Statistics
Transmit Statistics
Bytes Received
Bytes Transmitted
Total Packets Received OK
Ack Packets Transmitted
MAC CRC Errors
Packets Deferred Energy Detect
SNR
Packets No Ack Received
Receiver Statistics
Bytes Received
The number of bytes of data that were
received successfully
Total Packets Received OK
The number of all packets that were
received successfully
MAC CRC Errors
The number of packets that had a valid
802.11 Physical Layer Convergence
Protocol (PLCP) header but contained a
CRC error in the data portion of the packet
Signal level → SNR
The signal strength for all received packets
Range: 0 to 100% or -95 to -45 dBm
Transmitter Statistics
Bytes Transmitted
The number of bytes of data that were
transmitted successfully
Ack Packets Transmitted
The number of acknowledgment (Ack)
packets that were transmitted in response
to successfully received unicast packets
Packets Deferred Energy Detect
The number of packets that were delayed
because RF energy was already detected.
This condition is usually caused by another
radio transmitting a packet or by some
other RF source jamming the signal (such
as a microwave oven)
Packets No Ack Received
The number of transmitted packets that did
not have their corresponding Ack packet
received successfully
Layout of the Building, Upper Floor
Six Pentium-class computers were used as stationary nodes. A laptop computer was configured
as a server (adjacent to the access point). Both were placed on a mobile cart. A-F are the
location of the clients. 1-16 are initial Tx points. 17-20 are additional Tx points.
B
11
13
A
16
6
15
17
F
E
C
19
12
11
18
10
9
8
5
4
3
1
20
14
7
2
D
MAC CRC Errors
Bytes Received
Packet Characteristics I
Bytes Received
Packets Def. Energy Detect
Packet Characteristics II
Bytes Received
Packets Def. Energy Detect
Packet Characteristics III
Data Collection
 One mobile server and six clients
 Two-minute accumulation
 16 transmission positions
 Interpolation to 134 points
 The interpolated points would correspond to points 61 cm apart
 The actual measurements were not used in the training of the NN
Data Processing
Neural Networks
Packet characteristics and RF SNR are affected in a non-linear manner by the
materials and topology of a building. This provides the rationale to explore the
possibility of obtaining solutions from a feed-forward neural network.
Neural networks have become popular in several engineering fields and
appear to be a logical approach to this problem since they are particularly well
suited in solving non-linear problems.
An 8-tuple input vector: vi {ai , bi , ci , d i , ei , f i , g i , si }
an output vector: oi {xi , yi } , where i  N is the position index,
a – g are the packet parameters described earlier, and s is the SNR, are
used to train a NN
Neural Network
 6 NN networks, one for each client
 8 input nodes
 2 output nodes (x, y)
 9 sigmoids in hidden layer
 Levenberg-Marquardt algorithm†
 It took 600 epochs to reach the desired mean-squared error of 10-4
† M.T. Hagan and M. Menhaj, "Training feed-forward networks with the Marquardt algorithm," IEEE
Transactions on Neural Networks, Vol. 5, No. 6, 1999, pp. 989-993, 1994.
Considerations
 Interpolation – The first sixteen set of measurements were used for
the interpolation process that yielded 134 training sets, the actual
measurements were used to test the NN
 Gaussian Weighting - In order to merge the contribution of each
network, it is necessary to combine the output (x-y positions) from
each, yet averaging them affords undue influence from clients
positioned further from the server, possibly skewing the results. To
compensate, a Gaussian weighting function was employed to reduce
the effects from distant clients, i.e.,
wi  e
 [( xi  xi ')2 ( yi  yi ')2 ] / 2
where (xi,yi) are the coordinates of the client and ( xi ' , yi ' ) are
the output of a specific network.
Results
Position predictions for the 16 original locations. Circles indicate true
locations and “+” represents weighted centroids from the contributions of all
networks.
Additional Test Points
Position predictions of four additional test points.
Circles indicate true locations and “+” indicates system output.
Std. dev. of range (m)
Range error in meters
Errors
Range error of system from the original 16 locations using median filter
Localization Experiment: Summary
 Off the shelf technology (hardware and software)
 The neural networks are trained off-line and require
very little computational or transmission overhead
during the consultation phase
 The statistics collected are related to the position of
the server and the multipath nature of the building
 There is need to more precisely determine which of
the packet statistics are more relevant and to refine
the algorithm
Tutorial Summary
 The use of wireless communications technology in Medical
Applications is increasing steadily
 This technology can have an important contribution in
improving lives of patients at the same time as reducing costs
 Wireless sensor networks (WSN) are already being deployed
in a variety of scenarios including those in the area of
medical care
 This tutorial focus on those WSN aspects that are deemed to
be of interest to medical applications
 A turning point in the use of WSN in the medical field will be
when the intended users (patients, doctors, nurses, etc.)
accept this technology as readily as the current medical
equipment and devices
References







S. Arnon, D. Bhastekar, D. Kedar, and A. Tauber, “A Comparative Study of Wireless
Communication Network Configurations for Medical Applications,” IEEE Wireless
Communications, pp. 56-61, February 2003
D. Cypher, N. Chevrollier, N. Montavont, and N. Golmi, “Prevailing over Wires in Healthcare
Environments: Benefits and Challenges,” IEEE Communications Magazine, April 2006
M. Fadlee, A. Rasid, and B. Woodward, “Bluetooth Telemedicine Processor for Multichannel
Biomedical Signal Transmission via Mobile Cellular Networks,” IEEE Transactions on
Information Technology in Biomedicine, pp. 35-43, March 2005
Q. Fang, J. Gao, L.J. Guibas, V. Silva, and L. Zhang, “GLIDER: Gradient Landmark-based
Distributed Routing for Sensor Networks,” INFOCOM 2005.
Z. Haas, J. Halpern, and L. Li, “Gossip-Based Ad Hoc Routing”, IEEE/ACM Transactions on
Networking, Vol. 14, No. 3, pp. 479-491, June 2006
M.T. Hagan and M. Menhaj, "Training feed-forward networks with the Marquardt algorithm,"
IEEE Transactions on Neural Networks, Vol. 5, No. 6, 1999, pp. 989-993, 1994.
W. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive Protocols for Information
Dissemination in Wireless Sensor Networks,” Proc. 5th ACM/IEEE Mobicom Conference,
Seattle, WA, August, 1999.
References






T. L. Hemminger, D. R. Loker, and C. Pomalaza-Ráez, “A Neural Method for Identifying
Transmission Source Locations”, Proc. IEEE International Symposium on Personal, Indoor and
Mobile Radio Communications, Helsinki, Finland, September 2006.
E. Jovanov, A. Milenkovic, C. Otto, and P. de Groen, “A wireless body area network of
intelligent motion sensors for computer assisted physical rehabilitation,” Journal of
NeuroEngineering and Rehabilitation, 2005, 2:6
B. Karp , H. T. Kung, “GPSR: greedy perimeter stateless routing for wireless networks,”
Proceedings of the 6th annual international conference on Mobile computing and networking,
p.243-254, August 06-11, 2000, Boston, Massachusetts, USA
L. Kleinrock and J.A. Silvester, “Optimum Transmission Radii For Packet Radio Networks or
Why Six is a Magic Number”, In IEEE National Telecommunications Conference, December
1978.
C. Intanagonwiwat, R. Govindan, D. Estrin, and J. Heidemann “Directed Diffusion for Wireless
Sensor Networking,” IEEE/ACM Trans. on Networking, February 2003
H. Lufei, W. Shi, and L. Zamorano, “Communication Optimization for Image Transmission in
Computer-Assisted Surgery,” Proceedings of 2004 Congress of Neurological Surgeons, October
16-21, San Francisco, California
References






D. Malan, T. Fulford-Jones, M. Welsh, and S. Moulton., “CodeBlue: An Ad Hoc Sensor
Network Infrastructure for Emergency Medical Care,” Intl. Workshop on Wearable and
Implantable Body Sensor Networks, April 2004.
S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivastava, “Coverage Problems In
Wireless Ad-hoc Sensor Networks”, Twentieth Annual Joint Conference of the IEEE Computer
and Communications Societies, 2001.
V. Megalooikonomou and D. Kontos, “Medical Data Fusion for Telemedicine,” IEEE
Engineering in Medicine and Biology Magazine, pp. 36-42, September/October 2007
M. Pacelli, G. Loriga, N. Taccini, and R. Paradiso, “Sensing Fabrics for Monitoring
Physiological and Biomechanical Variables: E-textile solutions,” Proceedings of the 3rd IEEEEMBS International Summer School and Symposium on Medical Devices and Biosensors,
Boston, Sept.4-6, 2006
A. Rao, C. Papadimitriou , S. Shenker, I. Stoica, “Geographic routing without location
information,” Proceedings of the 9th annual international conference on Mobile computing and
networking, September 14-19, 2003, San Diego, CA, USA
S. Seidel, T.S. Rappaport, “914 Mhz Path Loss Prediction Models For Indoor Wireless
Communications in Multifloored Buildings”, IEEE Transactions on Antennas and Propagation,
February 1992.
References




Y. Shie, F. Tsai, A. Anavim, M. Wang, C-M Lin, “Mobile Healthcare: Opportunities and
Challenges,” Proceedings of Sixth International Conference on the Management of Mobile
Business, July 9-11, 2007, Toronto, Ontario, Canada
V. Shnayder, B. Chen, K. Lorincz, T. Fulford-Jones, and Matt Welsh, “Sensor Networks for
Medical Care,” Technical Report TR-08-05, Division of Engineering and Applied Sciences,
Harvard University, 2005.
E. Sloane and T. Cooper, “Safety First! Safe and Successful Digital Network Wireless Medical
Device Systems,” 2006 HIMSS Annual Conference February, San Diego
C. Whitehouse, “The Design Of Calamari: An Ad-hoc Localization System for Sensor
Networks”, Master’s thesis, University of California at Berkeley, 2002.