ISSNIP

Sensor Scheduling - Optimization and Control

Background

A sensor network is an array of sensors of diverse type interconnected by a communications network. Sensor data is shared between the sensors and used as input to a distributed estimation system which aims to extract useful information from the available sensor data. When all the data from all the sensors in the network is available at one place, conventional centralized estimation techniques can be employed. Centralized multi-sensor estimation theory critically assumes that the choice of which data to send from any particular sensor to the centralized node is fixed. If the network bandwidth changes during operation then such a system design can at best respond in a pre-planned manner. The centralized approach is typically only feasible for certain non-critical static sensor situations, as it fails to adequately address the issues of scalability or of survivability under real world degradation. Destruction of the central node (or an associated critical communications link) results in total network failure. A scalable system is required, in which new sensors or network links can be easily added, that continues to provide useful information even when some sensors and parts of the network fail or are destroyed, and can continue to operate within performance bounds while the communications bandwidth is varying (perhaps due to environmental conditions or electronic jamming).
In order to realise these practical requirements, a distributed estimation architecture as shown in Figure 1 is needed. Distributed data fusion overcomes many of the limitations of centralized fusion but also introduces new problems. To date distributed data fusion systems have been heavily reliant upon having very high communication bandwidths, due to the large amount of sensor data that must be transferred in real time between sensor nodes. The acquisition cost of such high bandwidth communications systems is usually very significant. Network scalability is also affected by the amount of allocated bandwidth. Hence to ensure that the sensor network operates and is scalable to some reasonable degree, very high bandwidths must typically be allocated. In order to solve the bandwidth problem, the system must make use of dynamically changing partial information from remote sensors by requesting sensor data in an optimal manner so that the most useful sensor data is sent over the currently available network bandwidth (no matter how small the available bandwidth is). The time sequence which specifies the best sensor data to utilise is called the optimal sensor schedule . Many currently implemented sensor scheduling algorithms for distributed sensors employ ad hoc sensor scheduling techniques. The problem with such approaches is the difficulty in quantifying system performance in multi-target or dynamic sensor and bandwidth conditions. Therefore, there is a need to develop a well founded analytic approach to the distributed sensor scheduling problem based on stochastic sensor scheduling and control. The theory can be applied to the distributed multi-sensor estimation problem where there are time-varying communication bandwidth constraints. The underlying problem of stochastic sensor scheduling with system constraints, however, presents a computational burden.

Significance / Benefits

Sensing accuracy: The utilization of a larger number and variety of sensor nodes provides potential for greater accuracy in the information gathered as compared to that obtained from a single sensor. The ability to effectively increase sensing resolution without necessarily increasing network traffic will increase the reliability of the information for the end user application.

Area coverage: A distributed wireless network incorporating sparse network properties will enable the sensor network to span a greater geographical area without adverse impact on the overall network cost.

Fault tolerance: Device redundancy and consequently information redundancy can be utilized to ensure a level of fault tolerance in individual sensors.

Connectivity: Multiple sensor networks may be connected through sink nodes, along with existing wired networks (eg. Internet). The clustering of networks enables each individual network to focus on specific areas or events and share only relevant information with other networks enhancing the overall knowledge base through distributed sensing and information processing.

Minimal human interaction: The potential for self-organizing and self-maintaining networks along with highly adaptive network topology significantly reduce the need for further human interaction with a network other than the receipt of information.
Operability in harsh environments: Robust sensor design, integrated with high levels of fault tolerance and network reliability enable the deployment of sensor networks in dangerous and hostile environments, allowing access to information previously unattainable from such close proximity.

Dynamic sensor scheduling: Dynamic reaction to network conditions and the optimization of network performance through sensor scheduling. This may be achieved by enabling the sensor nodes to modify communication requirements in response to network conditions and events detected by the network, so that essential information is given the highest priority.

Challenges

Sensor networks are rapidly becoming important in applications from environmental monitoring, navigation to border surveillance. However, due to bandwidth constraints, even very simple networks have proven to be very complex to properly control.

Applications

Surveillance: A major current challenge for border surveillance is to deliver the benefits associated with intelligent sensor networks using the existing low bandwidth communications infrastructure. However, even very simple sensor networks have proven to be very complex to properly control resulting in a number of ad hoc design procedures yielding severely limited realizable benefits from the data fusion system. The development of techniques for distributed data fusion within such sensor networks is thus required.

Supply chain management: An important application arises in the well known problem of supply chain management in a warehouse. Several tens of mobile Personal Digital Assistants (sensors capable of transmitting images, text and voice) interact with central sophisticated servers provide command and control solutions for smooth delivery of products and maintenance of inventory. Sensor scheduling algorithms are immediately applicable to this application.

Approach Distributed communication and control of sensor networks

Distributed communication and control of sensor networks will benefit immediately and substantially from ongoing research in various subfields including distributed control, agent-based simulation and hierarchical programming. Hierarchical or multi-level programming in the optimisation community is a relatively recent and rapidly growing area. Considerable advances and theoretical understanding and numerical methods have been made in the last two decades for nonlinear optimization problems called mathematical programs with equilibrium constraints MPCCs, which are closely related to bilevel programs. Most recently equilibrium problems with equilibrium constraints, EPCCs, have become part of the research agenda of both mathematical programmers, who investigate the fundamental mathematical properties of MPCCs, and economists who are interested in behaviour of systems of agents. Bilevel and multi-level optimization problems are relevant to optimal control of sensor networks given the large-scale, massive redundancy and low reliability of sensors. EPCCs are particularly exciting because they are designed to allow for multiple control objectives, and address the question of whether coordination will occur implicitly, that is, without a top-down control structure. The issue of implicit coordination is closely linked to research on distributed control methods.

National Importance

This project addresses a number of issues related to utilization, operation and control of complex sensor networks. The results of this research will find application in coastal surveillance, border protection, terrain mapping and navigation, knowledge acquisition and interpretation with distributed sensors for wide area surveillance etc. In addition, the fundamental techniques developed can be used for a range of other related applications in speech and image processing, target classification, mobile user tracking, and others such as robot navigation. All these areas are of prime significance in enhancing Australia 's technological competitiveness. A very direct benefit arises in the context of border surveillance. The key to successful deployment and utilization of intelligent sensor networks in the Australian environment lies in finding a solution to the bandwidth constrained distributed sensor network. Hence the outcomes of this project will greatly enhance Australia's capability in a critical area and be of very considerable national benefit.

Links

Satellite Sensor Communications

Irrigation scheduling  

Sensor networks

Intelligent sensors

Routing protocols

Sensor networks

References

  1. Sciacca LJ, Evans RJ, "Cooperative Sensor Networks with Bandwidth Constraints ", SPIE Aerosense Conference, Orlando , Florida , April 2002.
  2. Evans RJ, Krishnamurthy V, Nair GN. " Sensor Adaptive Tracking over variable Bandwidth Data links ",[Book Chapter] Essays in Adaptive Control , (Ed.) Goodwin G, Springer-Verlag, December 2000.
  3. Musici D, Evans RJ, "Linear Joint IPDA for Multi-Target Tracking in Clutter ", IEEE Conference on Decision and Control, Las Vegas, USA, December 2002.
  4. Majumder S, Rosenblatt J, Scheding S, and Durrant-Whyte H: Map Building and Localization for Underwater Navigation. ISER 2000: 511-520
  5. Steven Reece, Hugh Durrant-Whyte: A Qualitative Approach to Sensor Data Fusion for Mobile Robot Navigation. IJCAI 1995: 36-41.
  6. Gordon N, D. Salmond and A. Smith, " Novel Approach to nonlinear/non-Gaussian Bayesian state estimation ", IEEE Proceedings-F , Vol. 140, pp. 107-113, April 1993.
  7. Doucet A, N. Gordon, and V. Krishnamurthy, " Particle Filters for state Estimation of Jump Markov Linear Systems ", IEEE Trans on Signal Processing , Vol. 49, pp. 613-624, March 2001.
  8. Bar-shalom Y and X. R. Li, Multitarget-Multisensor Tracking: Principles and Techniques, ISSN 0895-99110, YBS Publishing, 1995.
  9. Vapnik, V. and Mukherjee, S., "Support Vector Method for Multivariate Density Estimation ", Advances in Neural Information Processing Systems, Vol 12, MIT Press 2000.
  10. Vapnik V, " Nature of Statistical Learning Theory ", Second Edition, Springer, NY, 1999
  11. Challa S, Palaniswami M and Shilton A "Distributed Data Fusion System Using Support Vector Machines ", FUSION2002, Annapolis, USA, July 2002.
  12. Titsias, M. K. and Likas, A. C. Shared Kernel Models for Class Conditional Density Estimation, IEEE Trans. On Neural Networks, Vol. 12, No. 5, September 2001.
  13. Lee HWJ, Teo KL, Lim AEB. Sensor scheduling in continuous time. Automatica, vol.37, no.12, Dec. 2001, pp.2017-23. Publisher: Elsevier, UK.
  14. Evans J, Krishnamurthy V. Optimal sensor scheduling for hidden Markov model state estimation. International Journal of Control, vol.74, no.18, 15 Dec. 2001, pp.1737-42. Publisher: Taylor & Francis, UK.
  15. Savkin AV, Evans RJ, Skafidas E. The problem of optimal robust sensor scheduling. Systems & Control Letters, vol.43, no.2, 15 June 2001, pp.149-57. Publisher: Elsevier, Netherlands.
  16. McIntyre GA, Hintz KJ. Sensor measurement scheduling: an enhanced dynamic, preemptive algorithm. Optical Engineering, vol.37, no.2, Feb. 1998, pp.517-23. Publisher: SPIE, USA.
back
top of page