Summary
of ARP Grant (2006)
Project
title:
SOCO
- Secure and Optimized Communication & Organization for Target Tracking in
Wireless Sensor Networks
Project
Investigator: T. Andrew Yang (yang@uhcl.edu)
Computer
Science & Computer Information Systems
Houston,
Texas 77058
1.
Introduction
and Research Objectives
Wireless
sensor networks (WSN) have major impact upon military and civilian
applications. One of the most important tasks in WSN applications is target
tracking, in which the WSN is employed to detect intruders or intruding
objects. The challenge is that a sensor node is typically limited in its
processing power, battery life, and radio strength. In addition, due to the
environments where the WSN is typically deployed (sometimes inside a hostile
area), physical security is usually not available. The successful design of a
WSN depends on how well those challenges are addressed. When using a WSN in
tracking moving objects, we have identified five critical requirements: (a) Efficient energy dissipation – The
goal is to increase the overall longevity
of the WSN. (b) Accuracy of target detection – The primary goal is
to ensure consistent accuracy without sacrificing the network’s longevity. (c) Optimized computation
– Due to the limited battery power stored in a sensor, computation performed on
the sensor must be optimized, in order to incur minimum energy dissipation. (d)
Re-configurability – When one or more of the sensors cease to function, the
network should be able to self-organize or
re-configure itself, in order to
re-construct a functional WSN allowing the mission to be continued. (e)
Secure communications – In the context of WSN security, security features
such as authentication, data integrity, confidentiality, and availability
are needed.
|
|
|
Figure 1: Comparison of the three
methods in energy consumption |
There exist
three main approaches for target tracking in WSN: tree-based, cluster-based,
and prediction-based [1]. Existing methods such as the LEACH-based algorithms
[3] suffer problems such as complex computations, redundant data, and redundant
sensor deployment. Those drawbacks result in energy use inefficiency and/or
expensive computation overhead. To tackle these problems, the PI and his
students have devised OCO (Optimized Communication and Organization),
an efficient method providing self-organizing and routing capabilities to a
WSN. OCO ensures maximum accuracy of target tracking, efficient energy
dissipation, and low computation overhead. An OCO-based WSN is re-configurable, meaning it can self-organize
itself when some of the nodes cease to function. We have conducted
simulation-based evaluations to compare OCO against LEACH and Direct
Communication (DC) [2]. OCO appears to consume less energy, while achieving
superior accuracy (green line in Figure 1). The OCO algorithm and the results
of the evaluations were accepted for publication in referred forums [7] [8].
OCO seems to have met the first four requirements of an efficient WSN for
target tracking. To ensure secure operations of OCO, we propose to extend OCO
by adding security features, and to build a distributed WSN Test Bed to test
the features.
2.
Methodology
OCO includes 4
phases: (a) position collection, (b) processing, (c) tracking, and (d) maintenance.
A. Position collection phase: In this phase, the base collects positions of all
reachable nodes. When the sensor nodes are first deployed in an area, the base
starts sending messages to its neighbors to gather their IDs and positions, and
advertising its own ID as the parent of the neighbors. Each of the base’s
neighbors, after sending its ID and position to its parent, marks itself as recognized, and then performs the same
actions as the base by collecting IDs and positions from their neighbors, and
advertising itself as the parent. Note that, when a node gets the position and
ID from a neighbor, it forwards the information to its parent. This process
continues until the message eventually reaches the base.
|
Table 1:
Algorithm for Removing Redundant Nodes |
|
1. Build a geographic image of the network by assigning
color value = 1 for all points that is covered by at least one sensor node.
The rest of the points are assigned color value = 0. (Note[1]) |
|
2. Initialize a list of nodes that are supposed to
cover the whole network area, called Area_List.
Assign Area_List = null. |
|
3. Add the base node to the Area_List. |
|
4. For all the nodes in the area, if a node is not
overlapping with any node in the Area_List,
add it to the Area_List. The
purpose of this step is to optimize node distribution. |
|
5. For each point in the network area, if the point is
not covered by any node in the Area_List,
add the node that contains the point to the Area_List. |
|
6. Nodes that are not in the Area_list after the “for” loops in steps 3, 4, and 5 are
redundant nodes. |
B. Processing phase: In this phase, OCO applies image processing techniques to
clean up the redundant nodes, detects the border nodes, and finds the shortest
path from each node to the base. (i)
Clean up redundant nodes: Table 1 is the algorithm removing
redundant nodes. A redundant node is a node whose sensing zone is occupied by
one or more other nodes. To identify redundant nodes, we first build a
geographical binary image representing the coverage zone of the network. (ii)
Define the border nodes: Nodes positioned along the border of
the network are border nodes. To
identify these nodes, we first apply the border
detection algorithm (Table 2) to identify a list of points (border points) that traverse the border
of the image. Finally, find a minimum set of nodes in the Area_List that contain all the border points, which are the border nodes. (iii) Find the shortest path to the base: The algorithm is given in Table 3.
|
Table 2:
Algorithm for Finding the Border |
|
1. For each pixel in the image, check if the color
value =1. |
|
2. If true
(meaning this pixel belongs to an object), scan all its neighbors to see if any
of them having the color value = 0. If true, this pixel belongs to the
border. |
|
Table 3:
Algorithm for finding the shortest path to the base for each node in the Area_List |
|
1. Work only with nodes in the Area_List of the ‘cleaning up redundant nodes’ step (Table 1). |
|
2. Assign parent_ID = 0 for all nodes. |
|
3. Assign parent_ID = the base’s ID for all neighbors
of the base and add these nodes to a list, called Processing List. |
|
4. For each node in the Processing List, consider all its neighbors. If the neighbor has
parent_ID = 0, assign the neighbor’s parent_ID = the node’s ID. Add the
neighbor to the Processing List. |
|
5. Repeat step 4 until all nodes are assigned
parent_ID. |
|
6. After the loop, each node in the Area_list has a parent_ID. When a node
wants to send a message to the base, it just delivers the message to its
parent. The message is then continually forwarded until it reaches the base.
The algorithm ensures that all the messages will reach the base through a minimum
number of hops. |
C. Tracking
phase: In the tracking phase, the sensor nodes all
work together to detect and track intrusion objects. Objects are assumed to
have come from the outside. Normally, only the border nodes are ACTIVE. When a
border node detects an object, it periodically sends its position information
to the base by first forwarding the information to its parent.
D. Maintenance phase: The purpose of this phase is to
reconfigure the WSN when the need for topology change arises. Such changes
include ‘exhausted nodes’, ‘damaged nodes’, ‘re-positioned nodes’, etc. In the
case of exhausted nodes, when the
energy level of a node is below a threshold, it turns all its children to SLEEP
and sends a report to the base. When the base gets the report, it enters the processing phase to reconfigure the
network, with dead nodes being removed and the network restructured.
2.1. Proposed Research
2.1.1.
Adding Security Features to OCO: As stated above, security in WSN is
faced with primary challenges. In addition, the WSN may be prone to impersonation attacks, possibly launched
by thieves or terrorists attempting to enter a WSN-monitored restricted area.
The data packets transmitted across the network may be prone to polluted blocks attacks, meaning the
attacker may re-organize or modify some of the data bytes. Encryption alone is
not sufficient against such attacks.
In the context of WSN security, features such as authentication, integrity,
confidentiality, and availability are needed.
As illustrated in Figure 2, there exist three generic types
of authentications in a WSN:
|
|
|
Figure 2:
Authentications in a WSN |
A. Node-to-base Authentication: Because a base station is typically
more powerful than a simple sensor node, the base station may rely on more
rigorous but computation-intensive algorithms (such as digital signatures) when
authenticating a sensor node.
B. Base-to-node
authentication:
On the other hand, it is commonly believed that digital signatures and
certificates will incur heavy computational overhead and thus inappropriate as
the authentication methods on the sensor node. Instead, lightweight authentication protocols, such as the key-pair
authentication methods surveyed in [3] and [4], would be the more appropriate
authentication method on the sensor node.
C. Node-to-node authentication: In this case, both the
authenticator and the authenticated are sensor nodes, and therefore is faced
with challenges similar to the base-to-node authentication.
2.1.2. Simulation-based Evaluation of the Devised Methods: The simulation models built to test
the performance of the evaluated methods are based on [5], and consist of
several sub-modules: The sensor-node sub-module (Figure 3) is
used to simulate a sensor node. It includes three layers (application, MAC, and
physical), and several modules (the coordinator, radio, sensor, and energy
modules). The sensor-network sub-module
contains a set of sensors, and is used to represent the WSN. Two nodes can
communicate with each other if the distance in between is smaller than their
communication radius.
|
|
|
Figure 3: A sensor-node model |
Four metrics
are used in evaluating the methods: (a) Energy consumption
measures the total energy consumed by the nodes after the simulation is
started. (b) Accuracy is the number of detected positions of the
intruding object(s) in a given method, compared to the number of detected
positions in the DC method, which is used as the base of comparisons [6]. (c)
Cost per detected position is the ratio between energy consumption and the number of detected positions. (d) Time
before the first dead node is the time when the first node of the
network runs out of energy [3].
Out of the proposed work, the existing OCO method will be extended. The
extended method(s) will be evaluated by using the existing simulation-based
evaluation environment [7][8]. New metrics and models will be built to evaluate
the security of the OCO-based sensor network.
2.1.3. Development of a WSN Test Bed: In addition to simulation-based evaluation, a complementary
evaluation method is to use a real WSN to evaluate the algorithms. We propose
to develop a WSN Test Bed, with actual controller boards and sensor nodes.
Recently we have conducted a survey of three wireless sensor network
development kits, including Crossbow’s MICA Developers Kit, Jennic’s Wireless
Microcontroller Kit, and MoteIV’s Tmote Sky Developers’ Kit. An overview table
comparing the primary features of those kits is included in Appendix A. Figure
4 depicts a high-level design of a WSN Test Bed.
|
|
|
Figure 4.
Design of a Wireless Sensor Network Test Bed (Source: Crossbow Wireless
Sensor Networks Product Reference Guide, 2006.) |
The proposed
WSN Test Bed will be deployed across the UHCL and the Lamar sites, and be
integrated into the existing Distributed Computer Security Lab (DCSL) at UHCL,
which provides servers, workstations, and Internet connectivity to remote sites
at Lamar and possibly other colleges/universities across the State. When
completed, the WSN Test Bed will provide a cutting-edge facility for faculty
and students of small colleges in
2.2. Research Schedule
|
Phase |
Research activities |
Anticipated outcome |
|
1.
5/15 - 12/31/06 |
1.
Develop SOCO’s node-to-node, node-to-base, and base-to-node
authentication protocols 2.
Develop the data confidentiality algorithms 3.
Develop the WSN Test Bed |
a)
Authentication & confidentiality protocols b)
WSN Test Bed |
|
2.
1/1 – 5/14/07 |
4.
Simulation-based evaluation of the authentication
and the data confidentiality features 5.
Test and fine-tune the WSN Test Bed 6.
Publish the findings in referred papers |
c)
Experimental design d)
Evaluation results e)
Referred papers |
|
3.
5/15 - 8/31/07 |
7.
Develop a graduate course on Security
in Sensor Networks 8.
Develop course projects to be implemented by students in both the
simulation environment and the WSN Test Bed |
f)
A new course design g)
Course projects |
|
4.
9/1 - 12/31/07 |
9.
Offer the Security in Sensor
Networks course 10. Test the developed
algorithms (authentication, confidentiality) in the WSN Test Bed |
h)
A new class i)
Evaluation results |
|
5.
1/1 - 5/14/08 |
11. Publish the findings in
referred papers 12. Write external grant
proposals to acquire additional funding to continue the research |
j)
Referred papers[2] k)
Grant proposal(s)[3] |
3. Qualifications
of the Investigators and Project Management
Yang is an associate professor of Computer Science and Computer
Information Systems, at the University of Houston-Clear Lake (UHCL). He received his Ph.D. in Computer Information
Science from the
In addition to coordinating the project, Yang will work with two graduate
research assistants, and focus on the study of symmetric authentications,
simulation-based evaluations of the existing and the newly devised features of
SOCO, and the development of the WSN Test Bed and its integration into the
existing security labs.
1.
Institutional Commitment and Sources of Additional Support
NSF has
funded a team of UHCL and UH-Downtown researchers for $200,000 to develop a
Distributed Computer Security Laboratory (DCSL) over a period of three years
(6/2003-5/2006). The UHCL
administration has provided $100,000 matching fund and lab space to support the
project. As the PI of the project, Yang has led the team in developing
labs for supporting research and teaching of network security, including
wireless networks. The work proposed in this proposal is an extension to the
NSF project, by focusing on developing secure and effective algorithms for WSN,
and integrating a WSN Test Bed into the existing computer security labs. The DCSL, currently providing ample space to
host the network devices and security appliances of the DCSL network, will be
used to host the WSN Test Bed. Network infrastructure and additional details of
the labs are included in the ‘Current Support’ section (Yang).
2.
Student Involvement and Training Opportunities in Science and Engineering
The proposed projects, when funded, will provide excellent opportunities
for students to engage in researches in WSN, especially in adding security features
into OCO. Over the two-year period, two student assistants per year at UHCL will
be hired to work on the projects..
3.
References
[1] Chuang, S. C. (2005) “Survey on Target Tracking in
Wireless Sensor Networks”. Dept. of
Computer Science – National Tsing Hua University. Retrieved 11/8/2005.
[2] Guo,
Weihua, Zhaoyu Liu, and Guangbin Wu (2003). “An Energy-Balanced Transmission Scheme
for Sensor Networks”. Proc. of the ACM
SenSys’03 Conf. 2003.
[3] Heinzelman, Wendi R., Anantha Chandrakasan, and Hari
Balakrishnan (2000). “Energy-Efficient Communication Protocol for Wireless
Microsensor Networks”. Proc. of the
[4] Liu, Donggang and Peng Ning (2003). “Location
based pair-wise key establishment for Static Sensor Networks”. Proc. of the 2003 ACM Workshop on Security
of Ad Hoc and Sensor Networks (SASN '03). http://discovery.csc.ncsu.edu/~pning/pubs/sasn03.pdf
[5] Mallanda,
C., A. Suri, V. Kunchakarra, S.S. Iyengar, R. Kannan, and A. Durresi (2005).
“Simulating Wireless Sensor Networks with OMNeT++”. LSU Simulator, version 1, 01/24/2005.
[6] Pattem,
Sundeep, Sameera Poduri, and Bhaskar Krishnamachari (2003). “Energy-Quality
Tradeoffs for Target Tracking in Wireless Sensor Networks”. Proc. of the 2nd Int. Workshop on
Information Processing in Sensor Networks, F. Zhao and L. Guibas (Eds.):
IPSN 2003, LNCS 2634, pp. 32–46.
[7] Tran, Sam Phu Manh, and T. Andrew Yang.
“Evaluations of Target Tracking Methods in Wireless Sensor Networks”. Accepted
for publication in the Proceedings of the 37th ACM SIGCSE
Technical Symposium on Computer Science Education (SIGCSE 2006).
[8] Tran, Sam Phu Manh, and T. Andrew Yang. “OCO:
Optimized Communication & Organization for Target Tracking in Wireless
Sensor Networks”. Accepted for publication in the Proceedings of the IEEE International Conference on Sensor Networks,
Ubiquitous, and Trustworthy Computing (SUTC2006). 6/5-7, 2006,
Links to Cluster Areas
The primary cluster area of the proposed work is Information Technology and Computer
Technology. Wireless sensor network is one of the cutting-edge research
areas in this cluster. An efficient and secure WSN method such as OCO will
likely lead to major external funding and possibly be integrated into practical
industry applications of WSN.
The proposed research also has strong applicability
in other cluster areas, including but not limited to, Advanced Technologies and Manufacturing, Aerospace and Defense, and Biotechnology
and Life Sciences. In fact, an efficient and effective WSN method for
target tracking, such as OCO, will find numerous applications in various
industry clusters that have a need for monitoring intrusion or object movement,
especially in aerospace and defense, and any critical facilities where secure
monitoring is a must. A list of WSN researches and applications can be found at
the TinyOS site (http://www.tinyos.net/related.html).