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

University of HoustonClear Lake

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 Texas, especially in the Southeastern region of the State, to engage in wireless sensor network research and education.

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 Univ. of Minnesota. His researches are in the areas of performance evaluation, and secure distributed systems. At UHCL, he has successfully created two graduate courses (Web Security and Network Security), and has introduced a new undergraduate Computer Security course. He has published over a dozen referred articles related to wireless and network security. As the PI of an NSF-funded grant, he has led a team of researchers from UHCL and UH-Downtown in developing computer security labs and course modules.

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 Hawaii International Conference on System Sciences, Maui, Hawaii.

[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. Dept. of Computer Science, Louisiana State Univ. Retrieved 9/8/2005 at http://bit.csc.lsu.edu/sensor_web/final_papers/SensorSimulator-IEEE-Computers.pdf

[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. Springer-Verlag Berlin Heidelberg 2003.

[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). Houston, Texas. 3/1-5, 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, Taichung, Taiwan.


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).

 



[1] Note that the sensor network area is defined by a rectangle of (x_min, y_min, x_max, y_max), in which x_min and x_max are the min and max values of x, and y_min and y_max the min and max values of y in the collected positions.

[2] Examples are IEEE Pervasive Computing and the ACM Wireless Networks.

[3] The NSF Networking Technology and Systems (NeTS) program, for example, provides annual funding of $40 million to support advanced research in wireless and next-generation networking. As stated in the program solicitation (NSF 06-516), one of the four focus research areas is Networking of Sensor Systems (NOSS), and “Funded projects will seek to create architectures, tools, algorithms and systems that make it easy to assemble and configure networks of sensor systems.”