Abstract
A Sensor Web (SW) consists of a large collection of small nodes providing collaborative and distributed sensing abilities in unpredictable environments. Nodes composing such an SW are characterized by resource restrictions, especially energy, processing power, and communication capacities. A sensor web can be thought of as a spatially and functionally distributed complex system evolving in and interacting with a geographic environment. So far, the majority of the currently deployed SWs has been mainly used for prototyping purposes. These SWs operate without considering a management scheme and do not take into account the geographic environment characteristics in which they are deployed. Multiagent Geosimulation (MAGS) is a recent modeling and simulation paradigm which provides a flexible approach that can be used to analyze complex systems such as SW in large-scale and complex georeferenced environments. In this paper, we propose to use an MAGS approach to support SW management. Moreover, we present Sensor-MAGS, a multiagent geosimulation system which manages sensor nodes using Informed Virtual Geographic Environments (IVGE). This system is applied in the context of a water resource monitoring project.
1. Introduction
Recent advances in wireless communications and sensing technologies have enabled the development of low-cost, low-power, multifunctional sensor nodes that are small in size and which communicate over short distances [1]. Sensor Webs (SW) are distributed network systems composed of hundreds of such sensor nodes [2]. New capabilities such as microsensing and in situ sensing as well as the wireless connection of these nodes open new possibilities for applications in various domains such as military, environment, health, home, space exploration, chemical processing, and disaster relief [3]. The low per node cost and the shrinking size of microprocessors in addition to the enhancement of their computation capacities, while decreasing their energy consumption, will allow dense distribution of these wireless networks of sensors and actuators [4].
SW can be thought of as a macroinstrument concept that allows for the spatiotemporal understanding of phenomena which take place in geographic environments through the coordinated efforts of a large number of sensing nodes of different types [2]. However, once SW are deployed, the management of such complex systems is a real challenge because of their limited energy, communication, and processing capabilities [1]. In spite of the intensity of the research carried out in this field, SW are still in their infancy [3]. The majority of currently deployed sensor webs are mainly used for prototyping purposes [2]. In many cases, it is impractical to experiment on real sensor web systems for several reasons. First, a particular hardware platform, while theoretically possible, may not yet be manufactured because its fabrication may be constrained by technical or design limits [5]. Second, even if the hardware platform exists, it may be prohibitively expensive for experimentation [1]. For example, applications developed for research purposes may require hundreds or thousands of nodes in order to accurately monitor a natural phenomenon [3]. With current sensor nodes costing up to hundreds of dollars, evaluating such research could cost tens of thousands dollars [3]. Third, even if it is practical to evaluate research on the real hardware platform, it may not be practical to experiment in an appropriate environment [2]. An example of this are sensor webs which operate on glaciers, remote wildlife habitats, volcanoes, and other environments where in situ sensing techniques are required and with which it is expensive or dangerous to experiment [6]. Therefore, there is a need for an efficient modeling paradigm which allows us to analyze SW using actors representing sensor nodes evolving in and interacting with a representation of their geographic environment.
One solution to the problem of SW analysis is Multiagent Geosimulation (MAGS). MAGS is a modeling and simulation paradigm which aims to study phenomena in a variety of domains involving a large number of heterogeneous actors (implemented as software agents) evolving in, and interacting with, a virtual representation of the geographic environment (VGE) [7, 8]. Most of the current SW simulation platforms that we analyzed and assessed lack an explicit representation of the geographic environment [9]. A SW is deployed in a spatial environment, and ignoring the characteristics of this environment would greatly decrease the quality of SW simulations. A critical step towards the development of an efficient SW simulation tool is the creation of a VGE, using appropriate representations of the geographic space and of the sensors evolving in it, in order to efficiently support the sensors' situated reasoning [10]. Since a geographic environment may be complex and of large scale, the creation of a VGE is difficult and needs large quantities of geometrical data originating from the environment characteristics (terrain elevation, location of objects and sensors, etc.) as well as semantic information that qualifies space (trees, buildings, rivers, etc.). In order to yield realistic SW simulations, a VGE must precisely represent the geometrical information which corresponds to geographic features. It must also integrate several semantic notions about various geographic features. To this end, we propose to enrich the VGE with semantic information that is associated with the geographic features. A number of challenges arise when creating such a semantically enriched and geometrically accurate representation of a VGE, among which we mention [11]: (1) automatically creating an accurate geometric representation of a 3D VGE; (2) automatically integrating the geometric representation with several types of semantic information; (3) making use of this representation in “situated reasoning” algorithms. Examples of such algorithms include sensor placement which aims to support sensors' deployment in order to optimize the communication between sensor nodes and with base stations, with respect to the environment's characteristics (obstacles, land cover, terrain, etc.).
In this paper, we present Sensor-MAGS, a Multiagent Geo-Simulation (MAGS) architecture for the management of sensor webs. While most works in the sensor network domain address issues such as networking, communication protocols, and energy efficiency which do not really depend on geographical constraints, we are interested in large sensor webs which are highly constrained by the geographical environment. Indeed, we use an MAGS approach with the purpose of analyzing potential interactions between sensors, as previous works do, but also with the geographic environment in which the sensor web is deployed. We thus aim at showing how an MAGS approach can solve complex problems such as intelligent management in large sensor webs.
Consider a water resource monitoring project scenario which uses sensor webs (Figure 1). This project is a distributed system that spans a large geographic area to monitor, model, and forecast physical processes, such as environmental pollution and flooding. It includes several management goals and complex challenges. A deployed sensor node has several sensors, communication hardware, and a Measurement Agent (MA) controlling the station's behavior. Sensors take their measurements and the MA forwards them to the data store or application user according to a predefined schedule which depends on the sensitivity of their positions. For example, in Figure 1, the sensor node MA2 may sleep most of the time and be triggered when water flow in its location reaches a critical level. According to the activity of the factory, the sensor node MA1 increases the frequency of its measurements in order to analyze the water quality in the soil which may be polluted by the factory's wastes.
A water resource monitoring scenario. Measurement Agent (MA) operating on a sensor node [4].
When rain falls in abundance, the sensors MA10, MA4, MA11, and MA12 must increase the frequency of their measurements, assess the level of water in the big lake, and notify the authorities of any likely inundation. Due to flood risks in rough conditions and soil contamination, we need a sensor web that supervises the flow and levels of water in sensitive places (e.g., areas A, B, and C delimited by dashed circles in Figure 1) and adapts to changes on the basis of the collected data. This self-adaptation may be carried out by intelligent sensor nodes which collect, analyze, and share their data and coordinate their tasks in order to monitor water resources (Figure 2). Current sensor web solutions are unable to anticipate the evolution of such kinds of situations and adjust the priorities of their processing. Moreover, sensor nodes must be placed with respect to the environment characteristics in order to ensure an optimized communication between sensor nodes and with base stations. To meet this end, we propose a multiagent geosimulation approach.
The virtual sensor web using Multiagent Systems [8].
In the reminder of this paper, Section 2 presents fundamental notions related to the multiagent geosimulation approach. Next, Section 3 provides an overview of the sensor network management domain. Section 4 provides an overview of our multiagent geosimulation methodology for sensor web management. Section 5 describes the Sensor-MAGS system's main architectural features. Afterwards, Section 6 details the geometrically accurate and semantically-enhanced virtual geographic environment in which sensor agents evolve. Next, Section 7 points out the way we take advantage of Sensor-MAGS to support sensor placement in informed VGEs. We also highlight the advanced visualization and spatial analysis capabilities of Sensor-MAGS's viewer. Finally, in Sections 8 and 9 we discuss our proposal and conclude with future works.
2. Multiagent Geosimulation
A fundamental idea underlying our approach is to move the most intensive processing out of the Physical Sensor Web (PSW) into a parallel Virtual Sensor Web (VSW) operating on a base station or a remote server (Figure 2). The objective is to reproduce, in a realistic manner, the real world in a virtual environment. Indeed, in this virtual environment, which imposes no limits on data processing, energy consumption and communication capabilities, it is possible to create a system for the management of the physical sensor web. In order to faithfully mimic the physical sensor web deployed in the area of interest, we need to simulate, in a realistic way, the physical sensor nodes as well as the geographic environment where they are located. We propose to use software agents for the virtual representation of the physical sensor web. An agent is a program with domain knowledge, goals, and actions [12]. An agent can observe and sense its environment as well as affect it. Agents' capabilities may include (quasi-) autonomy, perception, reasoning, assessing, understanding, learning, goal processing, and goal-directed knowledge processing [13]. The reproduction of the geographic environment in which physical sensor nodes are deployed should be based on reliable data obtained from Geographic Information Systems (GIS). The concept of Multiagent Geosimulation (MAGS) evolves from such type of simulations involving software agents immersed in a virtual geographic environment.
MAGS has attracted a growing interest from researchers and practitioners to simulate various phenomena in a variety of domains including traffic simulation, crowd simulation, urban dynamics, and changes of land use and cover, to name a few [14]. Such approaches are used to study various phenomena (i.e., car traffic, crowd behaviors, etc.) involving a large number of simulated actors (implemented as software agents) evolving in, and interacting with, an explicit description of the geographic environment called Virtual Geographic Environment (VGE). MAGS is a useful approach to integrate the spatial dimension in models involving different kinds of interactions (economic, political, social, etc.) [15]. From this perspective, the Geographic Information System (GIS) plays an important role in the development of geosimulation models. MAGS can be thought of as a coupling of two technologies: the Multiagent Systems (MAS) and the Geographic Information Systems [14]. Based on the MAS technology, the simulated entities are represented by software agents that can behave and make decisions autonomously. They can interact with other agents and with a virtual representation of the actual geographic environment. They may be reactive, proactive, stationary or mobile, social or cognitive [14]. These agents evolve and interact with their VGE.
An accurate VGE requires the use of reliable GIS data. GIS data are usually available in either raster or vector formats [16]. The raster format subdivides the space into regular square cells, each associated with an attribute related to the space. In contrast, the vector format describes geographic information using unconstrained geometric shapes, and generally associates one qualitative object with each shape. Such data are usually exploited by a VGE in two ways [17]: the approximate geometric subdivision and the exact geometric subdivision methods. The approximate geometric subdivision method is the direct mapping of the raster format, but it can also be applied to the vector format (Figure 3(c)). This discrete representation can be used to merge multiple semantic data [18], the locations where these data are stored being predefined by the grid cells. The main drawback of the grid method is related to a loss in spatial precision [19], making it difficult to accurately position any information which is not aligned with the subdivision. Another drawback arises when trying to precisely represent large environments using a grid: the number of cells tends to increase dramatically, which makes the environment description very costly. The grid-based method is mainly used for overlay and animation purposes [20] because of the fast data access it provides.
The two common cell decomposition techniques used to represent environments.
The second method, called exact geometric subdivision, consists in subdividing the environment in convex cells using the vector format as an input. The convex cells can be generated by several algorithms, among which the most popular is the Constrained Delaunay Triangulation (CDT) [21]. The CDT produces triangles while keeping the original geometry segments which are named constraints (Figure 3(b)). The first advantage of the exact subdivision method is to preserve the geometry of the input data, allowing accurately manipulating and visualising the environment at different scales. Another advantage of this approach is that the number of produced cells only depends on the complexity of the input shapes, but not on the environment's size and scale as is the case with the grid method. The main drawback of this approach is the difficulty to merge multiple semantic data for overlapping shapes. Moreover, this method is generally used to represent planar environments because the CDT can only handle 2D geometries. This method tends to be used for microscale simulations centered on individuals where motion accuracy is essential [22].
3. Sensor Network Manage
According to our literature review, architectures for the management of sensor webs involving the Multiagent Geosimulation (MAGS) paradigm do not exist. However, a few research projects have attempted to integrate the agent paradigm into sensor web architectures such as IrisNet [23], Abacus [24], Biswas, and Phoha's architecture [25, 26], and SWAP [27]. Most of these architectures identify the need for distributed data collection and processing, and propose layered architectures to achieve this. In Abacus different agents in the processing layer detect and report alert conditions to a higher layer interacting with users [24]. IrisNet uses agents such as Sensor Agents (SA) and Sensor Organisers (SO) to collect and analyze data from sensors to answer specific classes of queries [23]. Biswas and Phoha's approach uses agents in the service layer to analyse data from sensors and transfer it to the application layer [25, 26]. All these approaches deal with data collection by providing a distributed infrastructure for publishing, discovering, and accessing sensor resources. They also address the challenge of data fusion, to some extent, and aim to provide end users with the information they need. These approaches share a common objective through the use of the agent paradigm which is the distribution of tasks. However, these applications do not take complete advantage of the multiagent systems approach. Indeed, they use reactive agents which are efficient for alerting purposes, but are neither able to perform situated behaviors nor autonomous decision-making. On the one hand, situated behaviors include performing spatial reasoning and taking advantage of the virtual environment's description where sensor agents are located. On the other hand, autonomous decision-making includes managing sensor nodes in order to efficiently cover the area of interest while taking into account their limited capabilities as well as local spatial characteristics. We think that, in order to achieve intelligent and autonomous, it is essential to use a multiagent geosimulation approach in which agents are endowed with advanced capabilities such as perception, navigation, memory, and knowledge management. As the abovementioned architectures do not address the more challenging sensor web management issues, we propose the Sensor-MAGS System, a multiagent geosimulation platform for the intelligent management of sensor webs.
4. Sensor-MAGS: An Intelligent Sensor Web Management System
In this section, we first introduce the concept of sensor web management. Next, we present the approach we propose to support the intelligent management of sensor webs. Finally, we describe the Sensor-MAGS system's main architectural features.
4.1. Sensor Web Management
Sensor web management, as defined in [29], is “to manage, co-ordinate and integrate sensor nodes to accomplish specific and often dynamic sensing mission objectives.” The term “manage” means the control over the sensors. The term “co-ordinate” outlines the load balancing of tasks assigned to sensors with respect to their limited capabilities. Finally, the term “integrate” highlights the organization of the sensor into a coherent and structured architecture.
Interpreting the collected data as well as managing the sensing resources has historically been done manually. However, this task has grown difficult, if not impossible, due to the complex functionalities of modern sensory systems. Current initiatives seek to automate the process of data interpretation and sensor management. Data and information fusion is a concept whereby data from various sources are integrated and interpreted to allow accurate inferences about the environment. The idea is that fusing data from numerous sources provides a better picture of the environment than inferring from sensor measurements independently. The concept of sensor web management is deeply related to the data fusion research field. Its aim is to utilize the sensing resources in a manner that synergistically improves the process of data acquisition and ultimately enhances the perception and the comprehension of the situation of interest.
Sensor web management also concerns the control and coordination of limited sensing resources in order to collect the most complete and accurate data from a dynamic scene (Figure 4). As such, sensor management is a key enabler of environment monitoring applications. Sensor web management may be thought of as closing the loop on the fusion process, whereby sensing resources are actively managed to improve the quality of inferences made about the environment. Therefore, there is a need for an architecture which is able to aggregate sensor nodes into a manageable organization. This architecture must take into account the characteristics of the geographic environment where the sensor web is deployed. Ultimately, this architecture must provide a context which governs the sensors' interactions while achieving their goals including sensing, resource optimization, data dissemination, information fusion, and decision making.
Sensor web management objectives [28].
4.1.1. Our Approach
We propose to use a computer simulation approach in order to support sensor web management. In this context, the simulation is actually a copy of the real system on which experiments (or scenarios) can be run to evaluate various strategies. However, creating a computer simulation in order to support sensor web management raises a number of challenges among which we mention: (1) collecting observations and measurements performed by physical sensor nodes deployed in the field; (2) simulation of the interactions occurring between sensor nodes and with their geographic environment; (3) an overall understanding of the situation in the field including the observed phenomena and the sensor web in order to monitor its evolution; (4) development of strategies to adequately intervene and better control the sensor web; (5) comparing alternative intervention scenarios and anticipating the consequences of these interventions. Figure 5 illustrates the Observe-Orient-Decide-Act (OODA) methodology of the proposed solution [30]. As depicted, the physical sensor web corresponds to the Observation phase. These observations refer to measurements obtained in the field (sensed data). The next phase, simulation, corresponds to our multiagent geosimulation infrastructure. This phase combines the sensed data of the Observation phase with the spatial information retrieved from GIS in order to carry out simulations. The Decision-Making phase analyses the simulations' results and proposes plans and strategies aim to improve the sensor web performance. It also may assess the efficiency of plans and strategies involving the simulation phase. Finally, the action phase corresponds to assigning scheduled tasks to the physical sensor nodes.
Our MAGS approach for the management of sensor webs based on the Observe-Orient-Decide-Act (OODA) loop.
4.1.2. System Architecture
In this section, we introduce a layered architecture to support sensor web management. This solution is based on a multiagent system and uses the geosimulation approach in order to carry out simulations in virtual geographic environments. Such simulations aim to evaluate various management strategies for sensor webs. Since the management of large-scale sensor webs remains a critical task which should be controlled by human administrators, our solution proposes different strategies in order to support decision makers. Sensor-MAGS can be thought of as a layered architecture as illustrated in Figure 6 (rectangles on the right hand side). This architecture is inspired by the layered simulation model proposed in [31, 32]. In what follows, we briefly present these layers.
The layered architecture of our multiagent geosimulation platform for the management of sensor webs.
The first layer is the software platform which is in charge of reproducing the real geographic world in the Virtual Geographic Environment (VGE). A GIS is essential to reproduce real spatial data in the simulation environment. In addition, human users need a visual tool to monitor the geographic environment. It is thus necessary to transform GIS data into a simulation software platform which is visual for human users and navigable for software agents. Therefore, the Sensor-MAGS system integrates geographic information such as elevation, ground cover, and land use. This information is relevant to the simulation of sensors' activities in the field.
The second layer is responsible for modeling the dynamic factors influencing the real world. External factors such as atmospheric phenomena and weather conditions make the environment more dynamic and unpredictable, which requires data that are not provided by a GIS. Complementary models (such as water contamination, forest fire) need to be used to simulate this dynamism. Data used by these models should first be captured from the real world and then be continuously updated and transferred to the VGE. The model can thus provide a reliable and progressive simulation of the environment. For example, in the context of a water resource monitoring project, there is a need to simulate dynamic data related to flood phenomena.
The third layer corresponds to the multiagent layer. It represents actors which perform actions in the world. There is a need for software agents situated in the terrain. Concretely, these could be sensors or electronic devices which sense their neighborhood and in which agents are embedded. We also need agents in the VGE. Agents within the real world may then communicate with agents within the VGE, which guarantees a better coherency between data collected from both the real world and the VGE. Each actor should have a software agent as a representative within the VGE. In our example, an actor may be a sensor node or a group of nodes. Such an agent interacts with the physical sensor nodes via an interface and communicates with its representative in the VGE via remote messages. Before they can act (navigate, perceive, etc.) within the VGE, software agents need to be coherently linked to real world actors.
The fourth layer represents the functionalities which are domain specific. Actually, the three previous layers provide a foundation for applications that support decision makers in understanding the situation in the field, monitoring its evolution, developing and comparing different strategies to adequately intervene. For our example, the goal of the simulation of the sensor web is to manage and control its activities and to propose recommended actions aiming at achieving efficient in situ sensing while optimizing resources.
5. Simulation Platform
In Figure 7, we present an overview of our multiagent geosimulation platform which is fed by two data flows. On the one hand, the simulation system gets data collected by the physical sensor web (right hand side of Figure 7), including data related to the observed phenomenon in the area of interest (measurements) and control data related to the status of the sensor nodes (level of energy, position, etc.). On the other hand, the application's administrators provide the simulation system with information (left hand side of Figure 7) describing sensor web management scenarios.
Conceptual architecture of our sensor web management platform.
Basically, a sensor web management scenario is a plan or a strategy proposed by the application's administrators whose objective is to respond to a critical situation in the field or to assess an intervention plan given a sensor web's characteristics. However, before applying the plan or the strategy, the application's administrators need to assess its adequacy and effectiveness. The sensor webs that we aim to manage are composed of a large number of heterogeneous sensor nodes of different types and with different capabilities, spatially distributed in geographic environments of various extents. It is rather complex or even infeasible to analytically model such a sensor web, and it usually leads to an oversimplified analysis in which people have limited confidence. Indeed, most works only consider homogeneous sensor webs (sensors with identical capabilities) evolving in a homogeneous and static geographic environment.
Such assumptions considerably reduce the capacity to handle large-scale and complex real world geographic environments. Besides, the effective deployment of sensor webs for prototyping purposes implies a huge effort [33].
In order to reduce the need for a real physical sensor web in early design stages, we propose to model the physical sensor using a sensor web simulator. Thus, the conceptual architecture is modified as shown in Figure 8. We propose to use OMNET++ [34] in order to simulate the physical sensor web. We assessed the capabilities of Omnet++ in [9] and found it suitable to the requirements of the water resource monitoring project.
Conceptual architecture of the sensor web management platform based on a sensor web simulator.
Sensor webs are deployed for data acquisition purposes within a region of interest. Therefore, the spatial dimension is a key part of any sensor web management system. In order to provide sensor nodes with spatial perception, navigation, and reasoning capabilities we propose to augment their knowledge using a virtual geographic environment. A virtual geographic environment is an explicit accurate spatial representation of the real world in which agents representing sensor nodes evolve and with which they interact. Such a virtual geographic environment is built using reliable GIS data. It is decomposed into cells which include some semantic information in order to enhance data extractions. Such cells are abstracted using graph theory techniques in order to accelerate data access. As a result, the virtual geographic environment may encompass levels that are of various conceptual abstractions. Thus, the spatial environment can be analyzed from various perspectives according to the proposed level of abstraction [4].
6. From GIS Data to IVGE
In this section, we present our automated approach to compute the IVGE data directly from vector GIS data. Figure 9 depicts the four stages which compose our approach: input data selection, spatial decomposition, maps unification, and finally the informed graph generation. Moreover, in Section 6.5, we propose a topologic abstraction technique which aims at enhancing the IVGE description when dealing with large scale and complex geographic environments.
The four stages to obtain an IVGE from GIS data. All the stages are automatic but the first.
Various geometric and semantic layers related to the Montmorency experimental forest, St. Lawrence Region, Quebec, Canada: (a) water resources including rivers, water streams, and lakes; (b) road network; (c) and (d) two types of vegetation characterizing the landcover.
6.1. Input Data Selection
The first step of our approach is the only one requiring human intervention. It consists in selecting the different vector data sets which are used to build the IVGE. The only restriction concerning these data sets is that they must respect the same scale. The input data can be organized into two categories. First, elevation layers which contain the geographical marks that indicate absolute terrain elevations. We only consider 2 : 5D IVGE in which a given coordinate cannot have two different elevations, making it impossible to represent tunnels for example. This defined, multiple elevation layers can then be specified, and the model merges them automatically. Second, semantic layers which are used to qualify various types of data in space. Each layer indicates the physical or virtual limits of a given set of features with identical semantics in the geographic environment, such as roads and buildings. The limits can overlap between two layers, and our model can merge the information.
6.2. Spatial Decomposition
The second step consists of obtaining an exact spatial decomposition of the input data into cells. This process is entirely automatic, using Delaunay's triangulation, and can be divided into two parts in relation to the previous phase. First, an elevation map is computed, corresponding to the triangulation of the elevation layers. All the elevation points of the layers are injected into a 2D triangulation, the elevation being considered as an additional datum. This process produces an environment subdivision composed of connected triangles (Figure 11(a)). Such a subdivision provides information about coplanar areas: the elevation of any point inside a triangle can be deduced thanks to the elevation of the three original points. Second, a merged semantics map is computed, corresponding to a constrained triangulation of the semantic layers. Indeed, each segment of a semantic layer is injected as a constraint which keeps track of the original semantic data by adding additional attributes. The obtained map is then a constrained triangulation merging all input semantics (Figure 11(b)): each constraint represents as many semantics as the number of input layers containing it.
The two processed maps (a) and (b) and the unified map (c). The semantic colours are the same as in Figure 10.
6.3. Maps Unification
The third step to obtain our IVGE data consists of unifying the two maps previously obtained. This phase can be depicted as the mapping of the 2D merged semantic map (Figure 11(b)) onto the 2 : 5D elevation map (Figure 11(a)) in order to obtain the final 2 : 5D elevated merged semantics map (Figure 11(c)). First, a preprocessing is carried out on the merged semantics map in order to preserve the elevation precision inside the unified map. Indeed, all the points of the elevation map are injected in the merged semantics triangulation, creating new triangles. This first process can be dropped if the elevation precision is not important. Then, a second process elevates the merged semantics map. The elevation of each merged semantics point P is computed by retrieving the corresponding triangle T inside the elevation map, that is, the triangle whose 2D projection contains the coordinates of P. Once T is obtained, the elevation is simply computed by projecting P on the plane defined by T using the Z axis. When P is outside the convex hull of the elevation map, then no triangle can be found and the elevation cannot be directly deduced. In this case, we use the average height of the points of the convex hull which are visible from P.
6.4. Informed Graph Generation
The resulting unified map now contains all the semantic information of the input layers, along with the elevation information. This map can be used as a topological graph in which each node corresponds to the map's triangles and each arc to the adjacency relations between these triangles. Then, common graph algorithms can be applied to this topological graph, especially graph traversal ones. One of these algorithms retrieves the node, and so the triangle, corresponding to given 2D coordinates. Once this node is obtained, it is possible to extract the data corresponding to the position, such as the elevation, and the semantic information. Many other algorithms can be applied, such as path planning and graph abstraction, but they are out of the scope of this paper and will not be detailed here.
6.5. Topologic Abstraction
When dealing with large-scale and complex geographic environments such as the geographic environment where we will deploy the sensor web in the context of a water resource monitoring project, the topologic graph becomes very large. The size of a topologic graph has a direct impact on the computation time of sensors' spatial reasoning processes. In order to optimize such a computation time, we need to reduce the size of the topologic graph representing the IVGE. The aim of the topologic abstraction is to provide a compact representation of the topologic graph suitable for situated reasoning of sensor nodes. To this end, the topologic abstraction process extends the topologic graph with new layers. In each layer (except for the initial layer which is called level 0), a node corresponds to a group of nodes of the immediate lower level (Figure 12). The topologic abstraction simplifies the IVGE description by combining cells (triangles) in order to obtain convex groups of cells. Such a hierarchical structure evolves the concept of Hierarchical Topologic Graph in which cells are fused in groups and edges are abstracted in boundaries (Figure 12).
The topologic graph extraction from space decomposition and extension into different levels using the topologic abstraction.
To do so, convex hulls are computed for every node of the topologic graph. Then, the coverage ratio of the convex hull is evaluated as the surface of the hull divided by the actual surface of the node. The topologic abstraction finally performs groupings of a set of connected nodes if and only if the group ratio is close to one. Let C be the convexity rate and
Illustration of the topologic abstraction process with a strict convex property (
Figure 13(b) presents 2 convex polygons generated by the topologic abstraction algorithm. The optimization rate of the number of cells representing the environment is around 55%.
To conclude, we proposed in this section an automated approach for the generation of geometrically-accurate and semantically-enhanced IVGEs. We also proposed an approach which aims to optimize the structure of the IVGE description when dealing with large-scale and complex geographic environments. This approach reduces the number of convex cells by overlaying the informed graph with a topologically abstracted graph produced by the topologic abstraction. The resulting IVGE is hence based on a hierarchical graph whose lowest level corresponds to the informed graph initially produced by the spatial decomposition.
The Montmorency experimental forest, St. Lawrence Region, Quebec, Canada, in which we envision to deploy the physical sensor web in the context of the water resource monitoring project is characterized by its large scale and by the complexity of the geographic features that it encompasses (vegetation covers of various types and extents, roads, rivers, lakes). Indeed, as we will detail in Section 7, this geographic region extends over an area of almost 87 km2. The IVGE generation as well as the topologic abstraction process constitutes a fundamental step to develop a system that will help sensor web's administrators to visualize, localize, and analyze the sensors' placement with respect to the characteristics of this large-scale geographic environment.
7. Results
In this section, we present some implementation characteristics of our Sensor-MAGS platform. First, we introduce Sensor-MAGS Viewer software that we developed in order to automatically generate geometrically-accurate and semantically-enhanced virtual geographic environments and to inspect the environment partitioning in 2D and 3D. Next, we demonstrate how we take advantage of the semantically enriched description of the IVGE in order to support sensor placement, taking into account the environmental characteristics.
7.1. Sensor-MAGS Viewer
The proposed environment extraction method is used to create an accurate semantically-enhanced virtual geographic environment (IVGE) and provides the advantages of the semantic merging of grids along with the accuracy of vector data layers. Thanks to the automatic extraction method that we propose, our system handles the IVGE construction directly from a specified set of input vector GIS files. This set of GIS data files accurately describes the geographic areas of the Montmorency experimental forest, in which we envision to deploy the sensor web in the context of the water resource monitoring project. The performance of the extraction process is very good, processing the described area with one elevation map and ten semantic layers, in less than five seconds on a standard computer (Intel Core 2 Duo processor 2.13 Ghz, 1 GB RAM). The obtained unified map approximately contains 478; 000 triangles covering an area of 87 km2. The time needed to obtain the triangle corresponding to a given coordinate is negligible (less than
ψ 2D-IVGE visualisation of the GIS data. (1) unified map, (2) selected position's information pointing out a sensor coverage field and including geometric and semantic data. Circles represent sensors deployed by the administrators of Sensor-MAGS for water resource monitoring purposes.
7.2. Sensor Placement in the IVGE
In the context of our water resource monitoring project, sensor placement must take into account the nature of the terrain. For example, for radio signal propagation we must consider several features including the landcover and obstacles such as trees and foliage in the line of sight, as well as uneven surfaces and elevations for hilly terrains. Indeed, the radio signal may be attenuated or degraded (called signal fade) due to absorption or scattering of the signal energy by natural or human-made obstructions along the line-of-sight path. The radio waves may also be reflected or refracted off nearby obstructions (i.e., multipathing), creating destructive interference and difficult signal processing. Strong signal fade can cause the effective transmission range to be less than the calculated radio horizon. Radio signal fading and interference interactions are highly variable and site dependent, and are therefore very difficult to fully predict and avoid in anticipation.
In the IVGE model, the geographic environment where the sensor web will be deployed is accurately described with respect to terrain and landscape features. This IVGE is populated with sensor agents (software agents representing physical sensors) which have the capability to interact with their virtual geographic environment. The sensor web's administrators can easily add, remove, and place sensors in the IVGE as shown in Figure 11(c).
In contrast with physical sensor nodes, sensor agents have an enhanced knowledge about their environment's characteristics. Sensor agents share the informed virtual geographic environment in which they are situated and with which they interact. They are able to easily access its description and use both quantitative such as absolute terrain elevations and qualitative data such as geographic feature characteristics (river, land cover, vegetation height and nature, etc.). Hence, sensor agents are able to use GIS data in a structured way through the IVGE description. In addition, taking advantage of the graph-based structure of the IVGE description, concurrent access of a large number of sensor agents is possible.
With respect to the environment's characteristics including elevation, vegetation density and foliage, and location of water resources, each sensor agent computes the radio signal propagation and attenuation. We use the propagation model presented in [35]. Indeed, the environmental conditions (landcover, vegetation, terrain) affect electromagnetic waves propagation, reducing its power. When a transmitter
Figure 15 depicts the quality of sensors' communication with respect to the characteristics of the Montmorency experimental forest. Three communication patterns are considered for sensor agents: nonconstrained communication, partially constrained communication, and highly constrained communication.
Illustration of the quality of sensors' communication with respect to the environment's characteristics including landcover and terrain conditions.
Nonconstrained sensors' communications are observed in flat areas, rivers surfaces, and terrain with very low vegetation (heights below 20 cm, e.g., grass or branches lying on the earth). Partially constrained sensors' communications are observed in slopping terrains, and landcover with bushes (heights below 80 cm). Finally, highly constrained sensors' communications are observed in steep slopes and areas where vegetation is high (heights over 80 cm). Hence, the sensor web's administrators can freely add, move, or remove sensors from the Sensor-MAGS viewer. They can also analyze the sensor's communication quality, illustrated by specific colors as shown in Figure 15, given the environment's characteristics of the location where this sensor is situated. Finally, the sensor web's administrators can investigate and assess various sensor web deployment strategies using the Sensor-MAGS viewer before effectively deploy the physical sensor web.
8. Discussion
As sensors are used in greater numbers for field operation, efficient deployment strategies become increasingly important. Related work on self-deployment for mobile sensors using the notion of potential fields is presented in [37]. However, self-deployment does not provide a solution in the case of static sensors that need to be deployed in a specific configuration for applications such as our water resource monitoring project.
A related problem in wireless sensor networks is spatial localization [38]. Localization is particularly important when sensors are not deployed deterministically, as for example, when sensors are thrown from airplanes in a battlefield or when underwater sensors drift under the current's action. A number of techniques for both fine- and coarse-grained localization have been proposed recently [39, 40]. The problem of determining the coverage provided by a given placement of sensors has also been discussed in the literature [41]. Sensor placement on two- and three-dimensional grids has been formulated as a combinatorial optimization problem, and solved using integer linear programming [42, 43]. This approach suffers from three main drawbacks. First, computational complexity makes the approach infeasible for large problem instances such as the experimental Montmorency forest. Second, the grid coverage approach relies on ideal sensor detection and communication, that is, a sensor is expected to yield a boolean (true/false) detection or communication outcome in every case.
There is inherent uncertainty associated with sensor readings; hence sensor detections must be modeled probabilistically. Third, the grid-based approach which is used to represent the geographic environment fails to capture the geometric complexity of the real space and do not take into account the semantic information associated with various geographic features (river, lake, road, vegetation). The approach and tools we propose can possibly solve these problems as the models are refined.
Currently, our approach allows a large number of sensor agents to concurrently access the IVGE description and accurately compute the total loss of the communication quality while taking into account the environment's characteristics including landcover and terrain conditions. Our next step is to improve the sensor agent model in order to support autonomous decision-making aiming at optimising spatial coverage and communication quality of physical sensor in the deployed in the field.
9. Conclusion and Future Works
As a result of new advances in wireless communications, sensing technologies, and application design in SW, the development of a SW management system is becoming necessary and possible. Because of the significant differences between traditional networks and SW, a different management solution is required. In contrast to classic sensor network management systems which address network-health monitoring, fault-detection, traffic management, congestion avoidance, power management, and resource management, we focus on the spatial interactions between sensor nodes and their geographic environment. Recent research works have started to integrate artificial intelligence techniques in sensor webs in order to improve their autonomy and capabilities. However, these techniques are mainly applied at the sensor level (microlevel), which is still suffering from its limited capabilities. Moreover, most research works used artificial intelligence techniques for distributed purposes. In this paper, we described an intelligent SW management framework based on the MAGS approach which takes into account the geographic environment characteristics.
Our Sensor-MAGS framework aims at gaining better insight in intelligent sensor web management by analyzing the interaction mechanisms between sensors and their geographic environment. None of the existing sensor web management systems provides a fully integrated representation of the geographic environment as we propose. However, the development of general-purpose intelligent SW management is a challenging problem and remains a largely unexplored area for SW.
Given the constraints inherent to the water resource monitoring project, certain aspects of Sensor-MAGS have been simplified or not fully addressed in this design. In particular, we focused on the role of the IVGE to support spatial decision-making of sensor nodes, but we did not discuss the synchronization of the physical (real) and virtual (simulation) sensor webs.
It is important to note however that this issue can be addressed within the Sensor-MAGS design proposed here and will be presented in forthcoming papers. In addition, the most challenging part of the proposed multiagent geosimulation approach corresponds to the mirroring of the physical sensor web using an agent-based architecture. Indeed, the original aspect of the proposed architecture is its capacity to go beyond the physical limits of the sensor nodes in order to manage sensor webs. Our goal is to provide resource constrained sensor nodes with agents' capabilities in order to improve the sensing and monitoring tasks of sensor webs. Besides, sensor webs are geographically distributed systems in which the spatial dimension is of fundamental importance. Hence, being able to access reliable GIS data helps assessing the spatial distribution of sensor nodes. It also allows guiding the geosimulation process by immersing software agents in virtual geographic environments. Currently, we are working on the implementation of the behavioral models for sensor agents and their integration within the IVGE with the goal of demonstrating the applicability of MAGS to SW management.