الگوریتم ژنتیک بر اساس روش دقیق برای حداکثر کردن طول عمر شبکه های حسگر جهت دار

This paper addresses the problem of maximizing lifetime of directional wireless sensor networks, i.e., where sensors can monitor targets in an angular sector only and not all the targets around them. These sectors usually do not overlap, and each sensor can monitor at most one sector at a time. An exact method is proposed using a column generation scheme where a two level strategy, consisting of a genetic algorithm and an integer linear programming approach, is used to solve the auxiliary problem. The role of integer linear programming (ILP) approach is limited to either escaping from local optima or proving the optimality of the current solution. Computational results clearly show the advantage of the proposed approach over a column generation approach based on solving the auxiliary problem through ILP approach alone as the proposed approach is several times faster.

Rapid advancements in embedded systems and wireless communication technologies have facilitated the wide spread use of Wireless Sensor Networks (WSNs) for data gathering in remote or inhospitable environments such as battlefield surveillance, fire monitoring in forests, ecological and tsunami monitoring in deep sea. Under such environments, sensors are usually deployed in an ad hoc or random manner as their accurate placement is ruled out owing to risks and/or cost considerations. To cope with this random deployment, more sensors are deployed than actually required. This over deployment also makes WSNs more resilient to faults as some targets are redundantly covered by multiple sensors. Each sensor operates on a battery that has a limited lifetime. Moreover, replacement of batteries is not possible in remote or inhospitable environments. Therefore, prolonging the network lifetime by making best use of available resources is of prime concern in the design of WSNs for such environments. Most of the existing techniques for prolonging the network lifetime make use of redundancy in sensor deployment. These techniques divide the set of sensors into a number of subsets or covers (not necessarily disjoint), such that sensors in each subset covers all the targets. Amount of time during which each cover is used is also determined. Then, these covers are activated one-by-one for their determined time duration, i.e., at any instant of time only sensors belonging to a single cover are active, whereas all other sensors are inactive. This leads to a significant increase in lifetime because of the following two reasons. First, energy consumption of sensors in inactive state is negligible in comparison to active state [1] and [2], and, therefore, only keeping a required minimum subset of sensors active at any particular instant of time saves a lot of energy. Second, a sensor’s battery lasts for longer duration, if it oscillates frequently between active and inactive states. In fact, if a battery is discharged in many short bursts with considerable off time then its lifetime may double in comparison to a situation where it is discharged continuously [3] and [4]. This paper is concerned with the lifetime maximization problem mentioned above in the Directional Sensor Networks (DSNs), i.e., wireless sensor networks consisting of directional sensors only. Directional sensors can monitor targets in an angular sector only and not all targets around them. Video sensors [5] and [6], ultrasonic sensors [7] and infrared sensors [8] are common examples of directional sensors. In this paper, directional characteristics of sensors are assumed to be limited to sensing only and not to their communication ability. The sensing ability of directional sensors can be extended in several ways [9] and [10]. We can place several directional sensors of the same type on one sensor node in such a way that each sensor covers a different angular sector. A practical example of this kind of arrangement can be found in [8], where four ultrasonic sensors are placed on a single node to detect ultrasonic signals from any direction. Alternatively, each sensor node can be fitted with a mobile device so that nodes can move around. Another possibility is to equip each sensor node with a device that can switch the direction of the sensor over a range of directions in such a way that it can sense in all the directions though not at the same time. The direction of an active sensor at any instant of time is called its work direction at that instant of time. Like several previous approaches [9], [10], [11], [12] and [13], in this paper we have considered the last model and assumed that several possible directions in which a sensor can work do not overlap and a base station is located within the communication range of each sensor, i.e., we have not discussed the connectivity issue of the active sensors. The lifetime maximization problem in directional sensor networks, which we denote by LM-DS (Lifetime Maximization with Directional Sensors), can be formally stated as follows. Given m targets with known locations and n directional sensors randomly deployed in the vicinity of the targets, each sensor, when active, can monitor targets in one of σ non-overlapping directions at any instant of time and the sensor i has battery life bi. The LM-DS problem consists in scheduling the sensor’s activity in such a way that the network lifetime is maximized under the restriction that during the entire lifetime, each target is covered by the work direction of at least one active sensor. It has been shown in [14] that the problem is NPNP-Hard in the strong sense even when there is no restriction due to the work direction (i.e., all sensors have a 360° sensing ability), then so is LM-DS, which is a generalization of this problem. Fig. 1 and Fig. 2 illustrate LM-DS with the help of a simple example. Fig. 1 shows a simple directional sensor network with n = 9, m = 4 and σ = 4. For the sake of simplicity, all sensors are assumed to have the same orientation and same battery life time of one time unit. Fig. 2 shows an optimal solution to LM-DS problem in directional sensor network of Fig. 1 with nine covers and total lifetime of 2.25 units. Fig. 2 shows for each cover, the work direction of each active sensor in that cover as a shaded sector centered at that active sensor. The time duration of each cover is also mentioned in this figure.

This paper discussed the lifetime maximization problem of directional sensor networks. Owing to directional characteristic of sensors, this problem is more complex than its counterpart in conventional omnidirectional WSNs. In contrast to previously proposed approaches for the problem which are all heuristic in nature, a column generation based exact approach referred to as GA + ILP is proposed where a two level strategy comprising a genetic algorithm and an integer linear programming (ILP) approach is used to address the auxiliary problem. Computational results demonstrated the superiority of the proposed approach over a column generation approach relying on ILP approach alone to solve the auxiliary problem as the proposed approach is found to be several times faster. Our proposed approach is about 4.74 times faster on an average over all instances than the approach which uses the ILP alone. The advantage of the proposed approach is most pronounced on instances with m = 0.6n & σ = 3, where it is about 12.24 times faster on an average. Our approach can be extended to cater to directional sensor networks with one or more of the following additional requirements: • Where different targets have different quality-of-service requirements. • Where there is a bandwidth constraint on the number of sensors that can be active simultaneously. • Where sensors can communicate to a base station only through a multi-hop path of active sensors. • Where sensors have adjustable sensing ranges. Our future work will focus on aforementioned directions. The ideas presented in this paper can be used to develop exact methods for other problems also.