Sensor-based networks offer advantages compared to the currently used methods in space research. Recently, the NASA and European Space Agency (ESA) tests different sensor-based solutions like Seamless IP Diversity based Generalized Mobility Architecture (SIGMA) or Disruption Tolerant Networking tools [1,2]. Deploying sensors on the surface of distant planets will allow remote monitoring of non-easily accessible areas in preparation for human or robotic missions. For such kind of network, the mobility of sensing devices is an important element, due to the potential valuable scientific results gained from different sites, as opposed to static landers. In present days, expensive and sensitive multifunctional rovers were sent to analyze other planets. However, it is possible that in the future, thousands of cheap sensors will be placed on the surface of distant solar planet.

Sensor networks capable of distant planetary missions have been investigated by different groups. Our aim was to propose a mobile sensor network architecture that can localize its elements with minimal required resources. We used a recursive technique for the position estimation process, which technique extends the accessible coverage area using only three high performance devices with accurate positions. The location information of these super nodes serves as reference points for the recursive positioning of sensors [3]. At the same time, the super nodes play a gateway role between the deployed sensors and satellite(s).

We analyzed the performance of the recursive positioning algorithms in a custom implemented simulator. In our simulations, the surface and environmental characteristics—that influences the mobility and communication of mobile device—were also taken into account, e.g., dunes, holes, electromagnetic storm.

In this work, we identified different key questions of movement and positioning on the surface of a distant planet. We developed a simulation framework to analyze these questions. The article is organized as follows. Related Works describes the state-of-art of related works, including wireless sensor network deployment, data gathering methods and positioning techniques. Optimization of Multi-Hop Sensor Positioning gives a detailed description of the proposed model and the design goals of the architecture are introduced. The results are discussed in Results and Discussion

Wireless Sensor Networks (WSNs) will play a critical role in different environments, e.g., personalized healthcare, autonomous vehicles, distributed scientific measurements, meteorology, as well in space and planet exploration. The simple and cheap sensor devices have the ability to remotely monitor non-easily accessible areas, and can be used even to ensure the safety of actual human or robotic missions [4]. Due to their low cost and dimensions (even millimeter scale is possible), high number of these devices can be dispersed at the investigated area, to monitor atmospheric, terrestrial, electromagnetic features, and forward the collected data through their communication interface.

The efficient deployment of sensors is very important for the successful completion of sensing tasks. A sensor may move independently from others, or in a group, but usually uniform dispersion is preferred to minimize the uncovered area in the monitored environment. Different strategies were investigated in the literature, proposing movement control methods of the devices [5]. Most of these strategies [6-8] assume that the environment is sufficiently known and under control. However, in unknown or hostile environment— such as distant planets or disaster areas—sensor deployment cannot be performed manually. In these cases, the devices are scattered over great distances (e.g., airplane, space capsule), therefore the actual landing position cannot be precisely controlled due to the existence of wind or other obstacles. Zou and Chakrabarty proposed a centralized approach, where a powerful “cluster head” collects the sensor location, and determine the target location of the mobile sensors [9]. In certain deployment environments, the centralized approach is not always acceptable, because it may suffer from the problem of single point failure. In the case of special conditions, self-controlled methods are preferred.

Wang et al. investigated how to maximize the sensor coverage given less time, range of movement and message complexity [5]. The first step of their distributed self-deployment protocols is to discover the existence of coverage holes in the target area (areas not covered by any sensor) based on Voronoi diagrams [10,11]. After discovering a coverage hole, their proposed protocols calculate the target positions of these sensors. They introduced three movement-assisted sensor deployment protocols, VEC (VECtor-based), VOR (VORonoi-based) and Minimax, based on the principle of sensor movement from densely deployed areas to sparsely deployed areas. Common assumption of all the proposed control protocols is that the sensors have perfect positioning and navigation capability. Another alternative solution is, if the mobile sensors are proceeding on a determined path [12]. In this case, their current position can be estimated based on the elapsed time and movement velocity. Moreover, the future positions can be also predicted, so delivery of collected measurement data can be forecasted more efficiently.

The required energy for wireless transmission depends on the distance of the devices. The relation between the energy consumption and the distance (d) of devices is da, where a is between 2–5 depending on the wireless propagation conditions. The distance between the transmitter and the receiver is one of the most important parameters from the consumption point of view. Therefore, energy efficient network operation can be applied, if the data transmission is triggered when the distance between the source sensor and the receiver (central) sensor is the smallest. In the case of multi-hop sensor network, the devices close to the central equipment will consume more energy, because the data will travel through these sensors towards the data collector equipment. Assuming a sensor network deployed on a distant planet, the central data collector device will serve as a gateway, which forwards the collected records to the satellites, as it is illustrated in Figure 1.

Figure 1: Overview of a sensor-based network, which contains sensors, ground station and satellites. The arrows represents the different moving directions of the sensors.

In most of the cases, the collected measurement data is useful only if the accurate position of data gathering is known. Therefore, we can categorize the related works according to data gathering or positioning point of view.

Data gathering

Two types of data collector devices can be used to collect sensor data: fixed or mobile. In the first case, the sensors must move to the vicinity of the collector to transfer the measured data, while in the second case, the central device is also moving in order to collect the measurement records, consuming less energy for wireless transmission due to shorter distances, but the fuel economy of the motion must also be taken into account. The motion of data collector device can be random, predictable or controlled.

MULE devices (Mobile Ubiquitous LAN Extension) [13] visit randomly the sensors. When a MULE device arrives in close range to a sensor, it picks up the measured data, buffers it, and delivers the records to the data center when the communication becomes possible with it. A similar solution is used by the SENMA (SEnsor Networks with Mobile Agents) architecture [14] for low power and large scale sensor networks. Mobile agents in SENMA are powerful hardware units, both in their communication and processing capability, and in their ability to traverse the sensor network. Mobile agents can be aerial or ground vehicles equipped with sophisticated terminals and power generators, or specially designed light nodes that can hop around in the network.

In the case of predictable movement of the collector device, it can move on a pre-defined path as Chakrabarti et al. propose [15]. As the observer is assumed to traverse the same path repeatedly, the data is pulled by the receiver device periodically by waking up the nodes when it is close to them. Since the sensor nodes only transmit when the receiver device approaches them, the power requirements can be significantly reduced.

The third possibility is the controlled receiver device movement. Controlled movement generally consists of mobile devices in the network and moving to specified destinations with defined mobility patterns for specific objectives. The receiver node can adapt its route to achieve more efficient coverage management [16-18], energy composition reduction [19,20], transport layer parameters’ improvement [21,22], etc. Controlling the device’s movements offers new possibilities to improve the data collection efficiency, or optimize the network topology for different type of objectives as the above referenced works show [23].

Sensor positioning

Localization is one of the most significant challenges for mobile sensor networks. In order to gather sensor data in a spatial context or for proper navigation through a sensing region, the position must be precisely known. Mobile sensors must frequently estimate their coordinates, which takes time and energy, and consumes other resources needed by the sensing application. Different types of position estimation method exist, but all of them are based on measurement of radio signal propagation features. While receiving a radio signal, some of its properties, such as arrival time, signal strength, and direction, are captured by the receivers. In the second phase, certain signal parameters, such as TOA (Time of Arrival), TDOA (Time difference of Arrival), RSS (Received date: Signal Strength) and AOA (Angle of Arrival) are extracted from the captured values. The three most popular categories of methods for position estimation are time based, angle based and received signal strength based method.

With TOA [24], the distance between the transmitting node and the receiving node is deduced from the transmission time delays and the corresponding speed of signal. The main drawback of this approach is that it is difficult to precisely record the arrival time of radio signals, since they travel close to the speed of light. TDOA localization [25] improves upon the TOA approach by eliminating the need to know when the signal was transmitted. Several time-synchronized nodes receive a signal, and look at the difference in arrival times. For each TDOA measurement, the transmitter must lie on a hyperboloid with a constant range difference between the two measuring units. The equation of the hyperboloid is given by

(1)

where (xi, yi, zi) and (xj, yj, zj ) represent the fixed receivers i and j; and (x, y, z) represent the coordinate of the target.

The AOA method [26] determines the angular separation between two beacons, or a single beacon and a fixed axis. This method requires special antennas. Using RSS-based technique [27], the distance is estimated based on the wireless signal attenuation from the transmitting node to the receiving node. Empirical mathematical models are used toG calculate the distance according to signal propagation. As the final step, the calculation of the coordinates is done using triangulation (AOA) or trilateration (TOA, TDOA, RSS) [23].

Positioning systems assume that reference points exist in the network with precisely known coordinates. Recursive positioning [3] is an alternative solution that can increase system coverage iteratively, as nodes with newly estimated positions join the reference set. In hostile environment, where only few high performance centralized devices can be deployed, recursive positioning can extend the sensor network coverage area. Our model—proposed for monitoring distant planets with wireless sensors—utilizes the benefits of this method.

Several questions arise regarding monitoring the environment of a distant planet. In the sensor network planning process, the monitored data types, the network topology and the sensor movement strategy must be defined. In this article, we focus on a set of related questions, discussed in details in this Section. Other issues of reliability (including the effects of hardware or software errors on a WSN) are out of the scope of this work.

Measurable data on a planet

On the surface of a planet different types of data can be monitored and forwarded. We must define how important the measured data is. In the case of water discovery or soil pattern monitoring, it is not a problem if the collected data reach the command center on the Earth later since the measurements remain valid. However, if temperature is measured, it could be important to arrive in time, because the collected data could lose its actuality. Moreover, we must define that the measuring process is periodic, continual or event controlled. In our model, we chose a sensor network assuming that the collected data are valid for period of time and the measurements are periodic.

Satellite system

A satellite system makes it possible to forward the measured data to the communication station. If more satellites are used, permanent coverage can be ensured, but on the other hand the deployed network will be too expensive or even unrealizable. Therefore, we suppose to use a satellite system, keeping the number of satellites as low as possible in the proposed model.

Supersensors in the network

In our model, we used some special sensors, named supersensors. The supersensors collect data from the other sensors and forward to the Earth via satellites. Their actuation is more expensive, because the communication with satellites needs more energy that must be produced using bigger solar cells, compared to other regular sensors. We assume that these sensors are able to precisely determinate their own position (e.g., through GPS) and serve as base points for the iterative position estimation process of regular sensors. The supersensors move in formation with the other, more simple measuring sensors too, so they ensure to be at service, if there is data to be forwarded.

Sensors motion

The sensors are able to move and take measurement at different locations. In order to model the movement of the sensor equipment, we used both random and fixed path motion. The sensors get a random motion direction first, then a protecting zone border is defined, which determines the limit of the y coordinate displacement

Due to the iterative positioning technique that is used to estimate the coordinates of the equipment, the sensors must stay in groups and without moving away from each other. If a sensor reaches the predefined border limit, the movement direction must be changed in order to keep the sensors in group. During the angle adjustment, y coordinate of the motion changes, so the chance of leaving the border will be smaller. In case of crossing the border, the connection will be probably lost with the other sensors, as it is shown in Figure 2. The left original spots sign the starting point of the sensors. The highlighted points sign supersensors that are able to communicate with satellites and determinate their accurate position. In Figure 2, we can follow the movement of a sensor. In Step 2, the sensor reaches the protecting zone border, thus its y coordinate changes (it will become -y) and begins to move to a new direction. The x coordinate is not modified during the movement, so the sensors will move until reaching the line of point D. Using a large number of sensors, we can ensure that measurements will be performed uniformly on the determined territory of the lane from the starting point to the final destination (D).

Figure 2: Movement of a sensor in our model. The left original spots sign the starting point of the sensors. The highlighted points sign supersensors. x and y are the actual coordinates of the sensor. The line represents the border of the protecting zone. The sensor will move until reaching the line of point D.

Sensor communication

The measuring sensors can communicate with each other (multihop network) forwarding the monitored data sensor to sensor. The other solution is if the communication works only between a sensor and supersensor (single-hop network). In the first case, the data can reach to the supersensors in multiple steps, while in the second case, the sensors must wait until they arrive within the range of a supersensor. In our model the supersensors move in formation with the regular sensors, so we chose the second case due to its simplicity.

Sensor positioning

Simple sensor devices have limited energy production and complexity, so we cannot use GNSS-based (Global Navigation Satellite System) navigation. Instead of the satellite system, we use sensor based triangulation method for position determination as it is shown in Figure 3. Utilizing the position information of three sensors, we are able to estimate the position of a fourth sensor, if this sensor is within the range of the three reference sensors [28].

Figure 3: Calculating the position of sensor A using triangulation method. B1, B2 and B3 points are the known positions of the three sensors and sensor A has the unknown position. d1, d2 and d3 are the radius of the three circle.

Figure 3 shows a scenario, where B1, B2 and B3 points are the known positions of the three sensors and sensor A (in the middle) has the unknown position. In order to calculate its position we use circle engraving. If the cover of sensors B1, B2 and B3 are bigger than the distance from sensor A, then the method is adaptable. Circles, with d1, d2 and d3 radius and B1, B2 and B3 center, define the position of A. In this case, the B1, B2 and B3 are reference points. The reference point is the position of a sensor, which is used by the positioning algorithm. After determining the position of A sensor, it will become a reference point for determining still unknown sensor positions

Using this technique recursively and assuming that there are no lost sensors, the positions of all sensors within the group will be known. If there are some lost sensors, the determination process will be harder because probability of finding three reference sensors will be lower

At the beginning of our algorithm, the first reference points are the supersensors. These positions are always precisely known, because they can communicate with the satellites.

We use the following formulas for the calculation

(2)

(3)

where x, y are the coordinates of sensors, p(x) and p(y) are the coordinates of point P, and function dist(B1,B2) returns the distance between B1 and B2. The accuracy of the method was analyzed by using different optimization algorithms as it will be discussed later.

Optimization algorithms

We developed three different algorithms for optimization of positioning and we compared them from different viewpoints.

Basic position algorithm without optimization (BPA): In case of the initial algorithm, there is no optimization method. In order to calculate the position of a sensor, three parent sensors are chosen from the list of potential reference devices. The algorithm examines the potential reference sensors in the sensor group, and selects the first one that is capable to serve as a reference. After the first three hits, the examination stops, and the triangulation process can be started.

BPA is not an effective solution, because if the algorithm chooses three sensors, which estimated position is not accurate enough due to accumulated errors, the new calculation will contain all of these errors, too. This means that the calculated coordinates will be different from the real position. Actually, if the three basic supersensors can be selected as parents, then the calculated value will contain lower error, since the position of supersensors are precisely known.

Positioning algorithm based on hop number (PAHN): The PAHN algorithm differs from the BPA in the method of choosing the parents. In PAHN, the sensors use a hop value that contains how many steps of positioning lead to the calculated coordinates. Hop values of supersensors are zero, because the supernode positions are precisely known, and their coordinates are not estimated. Each simple sensor position is estimated from the position of three parent nodes, therefore the average of the hop values of the parents are calculated and set as a hop value of the currently estimated sensor.

For example, if we want to calculate the hop value of sensor A, and the parents of this sensor are supersensors S1, S2, and S3, the hop value will be the following:

(0+0+0)/3 + 1 = 1. (4)

If sensor B is chosen which parents are sensor A and two supersensors, then the hop value will be calculated as follows:

(0+0+1)/3 + 1 = 4/3. (5)

This means that the hop value shows how accurate calculation can be performed in the position estimation. If the hop value is small, then the calculation value is probably more accurate. Therefore a sensor chooses its parents on the basis of smaller hop values in order to estimate the position as accurately as possible. An example is illustrated in Figure 4.

Figure 4: Hop value calculate example with the PAHN algorithm. S1, S2, S3 are supersensors, A and B are simple sensors. The arrows represents the source of calculation.

Extended basic positioning algorithm (EBPA): We extended the previously described BPA with heuristic optimization. During the positioning process, the sensor sets all combination of reference sensors and calculates the coordinates for each one. The sensor position is calculated as the average of the estimated coordinates based on the examined reference sensor combination.

In order to analyze the performance of the proposed solutions, a simulation tool was implemented in C#. The tool is capable to set the surface of the planet, the number of the sensors, the communication range, the starting point and the final destination, etc. The parameters used in the simulation are listed in Table 1.

Table 1: Except otherwise indicated, we used the above described parameters.

Analyzing the error during the positioning process applying the three algorithms

In the research, we were interested in answering the following question: How much error will appear using these positioning algorithms? The error means the difference (in meters) between the real coordinates (controlled by the simulator itself) and the calculated coordinates, using the positioning algorithm. The averaged errors are presented in Figure 5.

Figure 5: The average error of the three algorithms. Horizontally the value of error distance, vertically the algorithms are illustrated.

According to Figure 5, the BPA algorithm works with an average error of 3.4 meter. The PAHN algorithm generates less error (around 3.1 meter) and the error of the EBPA is between these two values with 3.2 meter. This means that the entire two improved algorithm shows better results than the original one. There is the less error distance with less lagging sensors, because the lane border is stepped over with lower probability and the chance of data loss is reduced as well. According to the simulation results, the most effective algorithm is PAHN. In the case of PAHN, the calculations were always performed with the most accurate coordinate values, therefore the estimation of the position was also more precise compared to the other algorithms.

Change of error distance in function of sensor number

In this analysis, we were interested in the changes of the averaged error value in the function of the number of sensors. The results are interpreted for all of three algorithms, therefore we illustrated the results in one graph for the sake of transparency.

The measurement results are shown in Figure 6. In the case of BPA algorithm, if sensor number increases, the three supersensors are selected with lower probability as a reference sensor. Hence, the calculated sensor coordinates are less accurate. The EBPA algorithm shows better results than BPA. As we can see, the PAHN algorithm is the most effective one.

Figure 6: Change of error distance in function of sensor number. Horizontally the value of error distance, vertically the algorithms are illustrated.

The new algorithms, especially the PAHN can be effectively used in unexplored territories without any infrastructure. If three initial reference points are determined, the sensor positions can be estimated recursively expending the area of the covered region where the measurements can be performed. The proposed algorithms can be used in future exploration missions, where high number of sensor devices is used to monitor the surface of the distant solar body. We focused on distant planet surface monitoring as the main object of our research work, our position estimation algorithms can be used in other environment, too, where the lack of positioning infrastructure makes general positioning algorithms unacceptable. However, further studies of localization errors are needed before a related space application is developed, and a space system is launched.