Adaptive Indexed Divisible Load Theory for Wireless Sensor Network Workload Allocation

Abstract

Energy depletion in wireless sensors is a major obstacle for a wireless sensor network (WSN) to operate over an extended period of time. This problem can be extenuated by minimizing the need for high-power transmission from sensors to the master processor. Sensors could be arranged in clusters, and their sensing workloads are properly determined for minimal energy consumption during the sensing and result reporting stages. The divisible load theory (DLT) is applied here to obtain optimal allocation of sensor workloads taking into account the balance of energy used such that the failure of the first sensor can be delayed. Since standard DLT assumes an ordered indexing of the sensors, its direct application in WSNs may result in unbalanced energy usage. Adaptive indexing schemes with the application of DLT, adaptive indexed divisible load theory (AIDLT), are thus proposed to redefine the indices of sensors in each sensing round while calculating the assigned workload portions. Furthermore, adaptations based on transmission distances, sensor residual energies, double ranking of distances with residual energies, and randomized sensor identifications are formulated and evaluated. Simulation results on a cluster of sensors have shown that adaptation based on residual energies outperforms the other indexing schemes while the randomization scheme is the simplest.

1. Introduction

With technological advancements in sensing, computation and communication, small-size, low-cost, and high-performing devices made up of sensors, processors, and radios have become available and integrated as a wireless sensor. A large number of these sensors can then be formed as a wireless sensor network (WSN) [1] to be deployed and to carry out monitoring and surveillance tasks. In practice, sensors are dispatched into their operation areas in an ad hoc manner instead of under preplanned location schemes. Some kinds of routing protocol design [2] are, therefore, needed in order for each sensor to report their sensed data to a master processor for further analysis. On the other hand, for the whole network to provide a desirable sensing quality, sensors also have to be operated in a coordinated manner [3] as if players in a game. However, sensors are often deployed to operate in harsh environments and it is difficult to gain access to their anchored locations and provide maintenance. Because of such difficulty, battery energies onboard sensors may deplete and eventually makes the whole WSN inoperative. On the other hand, only if added costs can be tolerated, energy harvesting mechanisms [4] could be included in the sensor to compensate for the energy drained. Therefore, energy conservation [5] has become a crucial consideration in operating the WSN in a prolonged duration of periods.

In addition to carefully planned result reporting routes to reduce energy usage, it is also possible to partition the sensing load assigned to each sensor with the aim to reduce their unnecessary energy consumptions. The divisible load theory (DLT) [6], originated in scheduling computation load among networked computers, is an attractive candidate in designing the sensing workload portions. The formulation of DLT is based on the assumption that the computation load can be arbitrarily divided into granular components [7] and the optimality of task completion time is guaranteed. In the derivation of workloads from the DLT, processors will receive commands on their allocated portion of workload. Depending on the operation scheme, processors may starts their calculations instantaneously or wait until the last processor receives its workload assignment and then simultaneously start their calculations. The time needed for a sensor to complete the calculation is proportional to the amount of workload assigned to each processor. They then report the results, also depending on the amount of workload, to the central processor. Moreover, DLT requires an ordered indexing of the processors so that it is able to proceed with calculating and assigning workloads to processors. The application of DLT in parallel processed computations has been successful in many cases. For instance, monetary computing costs were made to trade-off for task completion time [8]. The DLT is also sufficiently generic that it can be adopted for computation scheduling in different architectures [9] such as the star and tree network. Furthermore, DLT is able to cope with network design cases [10] that network resources may not be known before the network is constructed.

With regard to energy consumptions in WSN, the major portion of energy used is related to radio transmission from the sensor to the master processor at the base station (BS). The power used for transmission is, in fact, determined by the 2nd or 4th power of the distance between the sensor and the BS. However, it is generally not feasible to distribute the sensors into their desired locations for complete sensing coverage [11] and the control of energy depletion rate based on sensor deployment is, thus, impractical. An alternative and feasible approach is to put sensors into standby or sleep mode [12] while it is only permissible when continuous sensing is not required.

Since the energy onboard sensors would ultimately be drained, it becomes a critical WSN design consideration to find alternatives to reduce energy usage while maintaining the sensors in operation [13]. To this end, sensors were grouped into clusters in close geographic vicinities [14–18]. With such grouping of sensors, improvements on energy efficiency, data gathering, and communications could be made. One of the sensors within the cluster is elected as the cluster head (CH). This particular sensor, possessing a larger amount of onboard energy, is responsible to collect and fuse sensing data from sensors in the cluster and transmit an aggregated data packet to the BS. By using this communication protocol, element sensors in the cluster are able to shorten their radio transmission paths, thus reducing the need for high-energy consuming transmission to the distant BS. As an alternative to clustering sensors, approaches based on chained radio communications had been proposed [19]. Moreover, a dynamical routing scheme was formulated [20] taking into account to reduce energy consumed in radio transmissions. Furthermore, attempts had been made to pass the sensed data from sensors to the CH through multihop transmission [21]. Distance-dependent criteria [22] were also being adopted in selecting appropriate CHs.

In scheduling workload in wireless sensor networks, complication arises as the sensor has to operate in the assignment, sensing, and reporting phases. For these challenges, clustering in a single tier or multiple tiers is an attractive scheme, especially for hierarchical sensor networks [23]. Alternatively, it is possible to properly schedule the workload with regard to data aggregation [24] at the CHs or BSs. Nonetheless, it is necessary to consider how workload assignment, sensing, and reporting should be scheduled. In particular, the use of DLT in sensing allocation for WSNs with different operation schedules was studied in [25] for multi-hop reporting. The effects of different sensing commencement schemes on the WSN performance were evaluated using DLT [26] for the number of sensors included in a cluster. Further WSN operation schemes, also employing DLT, were independently developed [27] for sensing and reporting scheduling. An upper bound on the number of sensors needed was then suggested. In addition, sensor energy consumption was considered while applying the DLT [28] for WSN scheduling where the existence of realizable workload allocations was analyzed.

From the reported work in the application of DLT to WSN workload allocations, it is observed that DLT is able to devise satisfactory schedules such that sensor energy consumption can be reduced. However, solutions for the limitation that DLT requires an ordered processor or sensor indexing have not been addressed in depth. In this work, the goal is to extend the operation lifespan of a WSN, arranged in a clustered star topology, through balancing the energy consumptions and minimizing depletions among sensors. We propose and examine several DLT-based reindexing schemes in the assignment of DLT-derived sensing workloads. These include reindexing based on the distances of sensors to the CH, reindexing based on sensor residual energies, double ranked reindexing of distances and residual energies, and purely randomized reindexing. Their performances are evaluated and choices of system designs are suggested.

The rest of this paper is organized as follows. In Section 2, the dependence of indexing in the divisible load theory is revealed. Reindexing schemes are proposed in Section 3. In Section 4, simulations conducted to verify the effectiveness of the proposed schemes are described and results are discussed. Finally, in Section 5, a conclusion is drawn.

2. Application of Divisible Load Theory in Wireless Sensor Networks

The divisible load theory has been successfully applied in scheduling computation works between connected computers [6] such that computations can be finished in the shortest time. Based on its analytical tractability and the equivalence between computer networks and WSNs, the DLT had also been applied in scheduling sensor workloads [20]. On the contrary, the operation of the WSN is severely affected by the limited battery energy stored onboard the sensors. Therefore, the DLT has to be further enhanced to cope with this implementation challenge. In the sequel, more detailed descriptions of the network architecture and the dependence on sensor indexing in standard DLT implementation are revealed.

2.1. Wireless Sensor Network Architecture and Operation

The divisible load theory is applied in wireless sensor network workload scheduling with the assumption that the load can be arbitrarily divided into small portions. Workloads assigned to sensors are calculated at the BS and the duration of sensing depends on the workload assigned to the sensor. The overall information gathered from the sensed environment is fused at the BS for analysis. Consider that N homogeneous sensors in the WSN, having the same sensing and reporting characteristics, are grouped into a cluster [15] and a CH has been selected. The sensors, arranged in a star network topology, receive workload assignments from the BS through the CH. Moreover, the sensed data are reported from sensors to the CH in a single radio channel [27]. Figure 1 illustrates the wireless sensor network architecture in star topology.

Figure 1

Star network architecture.

Let the base station requires B bytes of data to extract the phenomenon measured from the environment. The WSN reports sensed results in digital form at a transmission rate of R bits/sec corresponding to a bit-time of ${\tau }_b=\mathrm{1}/R$  sec/bit. Thus, for the required amount of data, it needs $T_r=\mathrm{8}\times B\times {\tau }_b$ sec to complete the report transmission by all sensors. Furthermore, the duration of sensing is a linear proportion of the report time that is, $T_s=k\times T_r$ sec. Hence, the workload of the WSN is here regarded as the duration of time that the whole network needs to conduct sensing and result reporting.

When all the sensors within the cluster have sequentially received the assignments, they start to sense the environment for the desired phenomenon. Sensors then send the results to the CH also in a sequential manner. Furthermore, the amount of result generated is proportional to the sensing duration. The timing diagram that describes the operation of the network is depicted in Figure 2. In the diagram, the label $S_i$ , $i=\mathrm{1},\dots ,N$ denotes the sensor index for its identification; ${\alpha }_i$ is the normalized portion of sensing workload assigned to sensor $S_i$ . In order to calculate the assignments, the DLT is applied and presented in the next subsection.

Figure 2

Sensing and result reporting schedule.

2.2. Divisible Load Theory

Based on the aforementioned wireless sensor network architecture, it can be seen from the timing diagram that the time for workload assignment $T_a$ is equal for all sensors and measurement starts simultaneously for all sensors at time $T_{\mathrm{0}}$ and the whole network finishes the sensing task at time $T_f$ .

The sensing time for sensor $S_i$ , depending on the assigned workload ${\alpha }_i$ , is

$$\begin{array}{cc}& \mathrm{\hspace{0.17em}\hspace{0.17em}}{T}_{s,i}={\alpha }_i{T}_s,\end{array}$$

(1)

when sensing is completed, the sensor sends the result to the CH in time:

$$\begin{array}{cc}& T_{r,i}={\alpha }_i{T}_r,\end{array}$$

(2)

and the total time that sensor $S_i$ used for the portion of assigned workload is

$$\begin{array}{cc}& T_{S_i}={\alpha }_i{T}_s+{\alpha }_i{T}_r.\end{array}$$

(3)

Since the communication channel allows only one originator to transmit, the strategy adopted here is to align the sensing time of sensor $S_{i-\mathrm{1}}$ to that of the overall sensing and reporting time of sensor $S_i$ . That is,

$$\begin{array}{cc}& {\alpha }_{i-\mathrm{1}}{T}_s={\alpha }_i{T}_s+{\alpha }_i{T}_r={\alpha }_i\left(k+\mathrm{1}\right)T_r={\alpha }_{i-\mathrm{1}}k{T}_r,\end{array}$$

(4)

and it can be rewritten as

$$\begin{array}{cc}& {\alpha }_i=s_i{\alpha }_{i-\mathrm{1}},\hspace{1em}i=\mathrm{2},\dots ,N,\end{array}$$

(5)

where

$$\begin{array}{cc}& s_i=\frac{k}{k+\mathrm{1}},\end{array}$$

(6)

which is a constant for the network of homogeneous sensors.

The portion of workload assignments ${\alpha }_i$ can then be obtained recursively from the following set of equations, namely,

$$\begin{array}{l}{\alpha }_{\mathrm{2}}=s_{\mathrm{2}}{\alpha }_{\mathrm{1}}\\ {\alpha }_{\mathrm{3}}=s_{\mathrm{3}}{\alpha }_{\mathrm{2}}=s_{\mathrm{3}}{s}_{\mathrm{2}}{\alpha }_{\mathrm{1}}\\ \phantom{{\alpha }_{\mathrm{3}}}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}⋮\\ {\alpha }_N=s_N{\alpha }_{N-\mathrm{1}}=s_N{s}_{N-\mathrm{1}}\cdots s_{\mathrm{2}}{\alpha }_{\mathrm{1}};\end{array}$$

(7)

thus, in general, we have

$$\begin{array}{cc}& {\alpha }_i={\alpha }_{\mathrm{1}}\prod _{j=\mathrm{2}}^i‍s_j,\hspace{1em}i=\mathrm{2},\dots ,N.\end{array}$$

(8)

Furthermore, when the sensing workload is normalized to unity,

$$\begin{array}{cc}& \sum _{i=\mathrm{1}}^N‍{\alpha }_i=\mathrm{1},\end{array}$$

(9)

then the first workload assignment ${\alpha }_{\mathrm{1}}$ can be obtained from separating ${\alpha }_{\mathrm{1}}$ from all other workload assignments in (8) by making use of (9); hence

$$\begin{array}{cc}& {\alpha }_{\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{1}+{\sum }_{i=\mathrm{2}}^N{\prod }_{j=\mathrm{2}}^i\hspace{0.17em}{s}_j},\end{array}$$

(10)

and the other assignments, ${\alpha }_{\mathrm{2}},\dots ,{\alpha }_N$ , can be found from invoking (7) recursively.

From (6), for $k>\mathrm{0}$ it is surely that $s_i<\mathrm{1}$ , and it can be observed from (7) that the workload portions to be assigned to sensor $S_i$ is in the form of a multiplicative series determined by the magnitudes of the constant coefficients $s_i,s_{i-\mathrm{1}},\dots ,s_{\mathrm{2}}$ . Thus, it is also certain that ${\alpha }_i>{\alpha }_{i+\mathrm{1}}$ and sensors with higher indices, in a homogeneous WSN, would receive lesser portions of workload. Therefore, it may be concluded that the assigned workload to a sensor depends critically on its identifying index defined at the BS. However, once the index is fixed to a particular sensor, its workload portion would remain unchanged until the completion of the whole sensing task. Consequently, its rate of energy consumption cannot be controlled and would lead to a prematured depletion of onboard energy making the whole WSN inoperative. Hence, reindexing schemes are proposed to resolve this problem for an extended sensing lifespan.

3. Adaptively Indexed Workload Allocation

Based on the observation, in the previous section, that fixing sensor indices in the DLT-based scheduling scheme might not enable the WSN to balance its energy consumption for extended operation duration. Several reindexing strategies ranging from simple intuitions to more complex considerations are proposed in the following with the aim to prevent premature depletion of sensor battery energies. These include reindexing on the bases of the distances between sensors and the CH, sensor residual energies, combined ranking on residual energies and distances, and pure randomization. It is also assumed that sensors are given a default identification index when the network is firstly initiated. However, during the operation or sensing rounds, the indices are adaptively changed in accordance with the reindexing schemes. This idea is illustrated in Figure 3.

Figure 3

Concept of reindexing strategy.

3.1. Indexing Based on the Distance to Cluster Head

In this reindexing scheme, it is assumed that the BS knows the locations of the sensors. For instance, sensors might be equipped with directional antennas for localization [29]. Furthermore, the majority of energy consumed in the sensor is related to that used in radio transmission [30, 31] which depends on the distance between the sensor and the CH. Hence, a first attempt is made to reindex the sensors according to this attribute.

Consider that the cluster head is positioned at $(x_{\text{CH}},y_{\text{CH}})$ with reference to some coordinate system. Let a sensor be located at $(x_{S_j},y_{S_j})$ , then the distance is given by

$$\begin{array}{cc}& d_j=\sqrt{{\left(x_{S_j}-x_{\text{CH}}\right)}^{\mathrm{2}}+{\left(y_{S_j}-y_{\text{CH}}\right)}^{\mathrm{2}}},\hspace{1em}j=\mathrm{1},\dots ,N.\end{array}$$

(11)

These distances are then sorted in the ascending order such that a new index for workload assignment purposed is given to each sensor. That is,

$$\begin{array}{cc}& \forall d_j,\hspace{0.17em}\text{assign}\mathrm{\hspace{0.17em}\hspace{0.17em}}j⟶i,\hspace{0.17em}\text{such that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{d}_i\le d_{i+\mathrm{1}},\end{array}$$

(12)

where the index i now corresponds to the index for workload assignment ${\alpha }_i$ .

3.2. Indexing Based on Residual Energy

In addition to re-index sensors in accordance to their distances to the CH, the residual energy onboard the sensor is a critical factor that affects the WSN operation. Here, a further reindexing strategy is devised to assign new sensor indices according to the residual energies.

Let each sensor be initially installed with a battery onboard as the energy source [30] and let the normal battery voltage be V volt ( $V=\mathrm{3}\hspace{0.17em}\text{volt}$ ) and the battery capacity is A ampere hour ( $A=\mathrm{0.5}\hspace{0.17em}\text{Ah}$ ). The initial energy carried by the sensor is

$$\begin{array}{cc}& {\stackrel{-}{E}}_{\mathrm{0}}=VA\times \mathrm{6}{\mathrm{0}}^{\mathrm{2}}.\end{array}$$

(13)

Further, assume that when the network is deployed for the first time and sensor locations are to be determined. Throughout this localization phase, some energy ${\eta }_{\mathrm{1}}{\stackrel{-}{E}}_{\mathrm{0}}$ would be consumed. Moreover, when sensors form into clusters [15] and a further amount of energy ${\eta }_{\mathrm{2}}{\stackrel{-}{E}}_{\mathrm{0}}$ is consumed. Thus, the onboard energy of a sensor $S_j$ before any measurement is made becomes

$$\begin{array}{cc}& E_{\mathrm{0},j}=\left(\mathrm{1}-{\eta }_{\mathrm{1}}-{\eta }_{\mathrm{2}}\right){\stackrel{-}{E}}_{\mathrm{0}},\end{array}$$

(14)

where ${\eta }_{\mathrm{1}}\in [\mathrm{0.01}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0.02}]$ and ${\eta }_{\mathrm{2}}\in [\mathrm{0.01}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{0.03}]$ are random numbers representing the initial portion of energy usage.

For the sensor $S_j$ assigned with workload fraction ${\alpha }_j$ , the sensing time is $T_{s,j}={\alpha }_j{T}_s$ , ( $T_s=k\times T_r=k\times \mathrm{8}\times B\times {\tau }_b$ ). Also assume that the current drained to sense a bit of data is I, ( $I=\mathrm{0.3}$  mA), then the energy consumed per bit in sensing is $E_s=VI{\tau }_b$ ( ${\tau }_b=\mathrm{64}\hspace{0.17em}\mu \text{s}$ ). During this period, an equivalent number of data bits is $B_{s,j}=T_{s,j}/{\tau }_b$ and the energy consumed is

$$\begin{array}{cc}& E_{s,j}=B_{s,j}{E}_s.\end{array}$$

(15)

For sensed data reporting, the report time is   $T_{r,j}={\alpha }_j{T}_r$ , ( $T_r=\mathrm{8}\times B\times {\tau }_b$ ), and the number of bits reported is $B_{r,j}=T_{r,j}/{\tau }_b$ . In addition, assume that the transmit power can be adjusted according to the distance $d_j$ between the sensor and the CH [31]. The energy consumed in transmitting the result to the CH is

$$\begin{array}{cc}& E_{r,j}=B_{r,j}\left(\mathrm{1046}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{9}}+d_j^{\mathrm{2}}\times \mathrm{22}.\mathrm{2}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{12}}\right).\end{array}$$

(16)

The residual energy remained on the sensor, after the tth sensing and reporting round, is hence equal to

$$\begin{array}{cc}& E_{t,j}=E_{t-\mathrm{1},j}-E_{s,j}-E_{r,j},\hspace{1em}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}}t=\mathrm{1,2},\dots .\end{array}$$

(17)

In this residual energy-based reindexing strategy, and at the end of a sensing round, the amount of residual energy onboard each sensor is reported to the BS in conjunction with the sensed result. At the BS and before the commencement of the next sensing round, the workload assignments are calculated according to the magnitude of the sensor residual energy. Here, the energies are sorted in a descending order, such that

$$\begin{array}{cc}& \forall E_{t,j},\hspace{0.17em}\text{assign}\mathrm{\hspace{0.17em}\hspace{0.17em}}j⟶i,\hspace{0.17em}\text{such that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{E}_{t,i}\ge E_{t,i+\mathrm{1}};\end{array}$$

(18)

hence, sensors with a larger amount of residual energy are assigned with larger portions of sensing workload. The sensor with a less amount of residual energy will have a smaller amount of workload, reporting a shorter data stream. Thus, their energy consumptions are reduced and their operation lifespan are prolonged.

3.3. Indexing Based on Double Ranking of Residual Energy and Distance

Reindexing based on the distances from sensors to the CH and based on the residual energies onboard sensors had been considered and presented in the previous subsections. An attempt is now made to evaluate the feasibility of hybridizing those two attributes to formulate a sensor reindexing strategy.

The distances and residual energies are ranked and produce two sets of ordered indices for distances and residual energies. That is,

$$\begin{array}{cc}& \forall d_j,\hspace{0.17em}\text{assign}\mathrm{\hspace{0.17em}\hspace{0.17em}}j⟶m,\hspace{0.17em}\text{such that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{d}_m\le d_{m+\mathrm{1}},\end{array}$$

(19)

$$\begin{array}{cc}& \forall E_{t,j},\hspace{0.17em}\text{assign}\mathrm{\hspace{0.17em}\hspace{0.17em}}j⟶n,\hspace{0.17em}\text{such that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{E}_{t,n}\ge E_{t,n+\mathrm{1}}.\end{array}$$

(20)

Furthermore, a combined ranking is performed and the final ranking is

$$\begin{array}{l}\forall k=ℛ\left(m+n\right),\hspace{0.17em}\text{assign}\mathrm{\hspace{0.17em}\hspace{0.17em}}k⟶i,\\ \text{such that}\mathrm{\hspace{0.17em}\hspace{0.17em}}{ℛ}_k\left(m+n\right)\le {ℛ}_{k+\mathrm{1}}\left(m+n\right),\end{array}$$

(21)

where $ℛ(·)$ is the ranking operator. Here, the result of the reindexing operation is that sensors having a shorter distance to the CH and a higher level of residual energy will receive a larger amount of sensing workload assignments. The overall effect is that energy consumptions are balanced between sensors depending on their distances to the CH and residual energies.

3.4. Indexing Based on Pure Randomization

The reindexing strategies proposed above all require that the BS knows the sensor positions and their onboard energies. On the other hand, a simple strategy depending on a pure randomization or permutation of the sensor indices is proposed and examined. Now,

$$\begin{array}{cc}& \left\{i⟵𝒫\left(j\right)\right\},\hspace{1em}j=\mathrm{1},\dots ,N,\end{array}$$

(22)

where $𝒫(·)$ is the randomization or permutation operator on the original sensor indices. Here, the workload portion ${\alpha }_i$ is assigned to a randomly selected sensor $S_j$ irrespective of its distance to the CH or its residual energy.

4. Simulations

Simulations are conducted to verify the effectiveness of the proposed adaptively indexing methods when they are applied in the workload allocation of a wireless sensor network. Two test cases are studied including the standard DLT (SDLT) approach without reindexing and the proposed adaptive indexed (AIDLT) approaches. These include distance-based reindexing (DisDLT), energy-based reindexing (EnergyDLT), rank-based reindexing (RankDLT), and randomization-based reindexing (RandomDLT). It is assumed that sensors are deployed randomly over an area that is to be monitored. Because of the randomness in initial sensor deployments, the effectiveness will be assessed by Monte Carlo repetitive tests for 100 repetitions. Statistics are collected on the instances that the first sensor energy depletes, and the sensing rounds that half-sensors deplete their energies. The simulations conducted are based on the system and sensor parameters given in Table 1.

Table 1

Simulation parameters.

Parameter description	Value
Number of simulation runs for each SDLT and AIDLT case	100
Area of square environment monitored	50 × 50 m
Number of sensors (N)	30
Data required by master processor (B)	2 × 106 bytes
Time to transmit 1 bit ( ${\tau }_b$ )	64 × 10−6 sec
Ratio of sensing/reporting durations (k)	8
Average battery voltage (V)	3 V
Battery capacity (A)	0.5 Ah
Current drain in sensing per bit time (I)	0.3 × 10−3 A/bit

4.1. Evolution of Energy Depletion

In the simulations for SDLT and the proposed AIDLT approaches, sensors are deployed randomly over a square sensing area as shown in Figure 4(a) at the first sensing round. In this figure, a red square is used to represent the CH. Sensors are indicated as black dots while their initial energies are denoted by circles whose diameters are proportional to the onboard energy.

Figure 4

Sensor energy evolution in standard DLT (SDLT) workload allocation. (a) Initial energy onboard sensors, (b) instance when first sensor depleted, and (c) instance when half-sensors depleted.

4.1.1. Standard DLT (SDLT)

The instance that the first sensor depletes its energy for the SDLT test case is depicted in Figure 4(b). Since the sensors are deployed randomly and their positions relative to the CH would affect the energy consumption, numerical values given here are regarded as typical sample values only. It can be seen that in the SDLT approach, at a small number of sensing rounds at $\mathrm{1910}$ , other sensors still maintain relative large amount of remaining energies. Figure 4(c) illustrates the instance when half the sensors depleted their energies according to initial of energies inherent in the system and the amount of sensed data transmitted through the radio channel. The sensing round conducted in the SDLT case is 4708. For sensing rounds beyond the deaths of more than half-sensors, it is regarded that the WSN has become inoperative and is not further considered here.

4.1.2. Distance-Based Reindexing (DisDLT)

For the test on reindexing based on the distances between sensors and the CH, simulation snapshots are shown in Figure 5. It is of note that due to random deployment of sensors, their positions are different from the previous test. Sensing lasts until the 1926th round before the first sensor depleted its energy. Moreover, at the 4691th round, half of the sensors depleted their energies. It is also interesting to observe that the first depleted sensor is located at a close vicinity to the CH. This situation is expected as this reindexing strategy is designed such that the sensor closest to the CH is allocated the largest amount of sensing workload ${\alpha }_{\mathrm{1}}$ . Hence, the sensor has the largest amount of data to be sent to the CH irrespective of the short radio path distance and the smaller radio power needed. On the other hand, when half of the sensors depleted their energies, the $N/\mathrm{2}\text{th}$ sensor depleted is located at a moderate distance to the CH. The remaining sensors, as seen in the figure, are located at longer distances to the CH. This situation is also expected as those sensors were assigned lesser amount of workloads, hence consuming lesser amount of energy in radio transmissions.

Figure 5

Sensor energy evolution in distance-based adaptive Indexing DLT (DisDLT) workload allocation. (a) Initial energy onboard sensors, (b) instance when first sensor depleted, and (c) instance when half-sensors depleted.

4.1.3. Residual Energy-Based Reindexing (EnergyDLT)

Test results for the strategy of residual energy-based reindexing are shown in Figure 6 while the instance when the first sensor depleted its energy is depicted in Figure 6(b). The situation when half of the sensors depleted their energies is shown in Figure 6(c). With this strategy, the instance at which the first sensor depleted its energy is found at the 6475th sensing round while half of the sensors depleted energies at the 6477th round. It is noted that these two instances are significantly extended as compared to the previous cases. Furthermore, the instances at which the first and half-sensors depleted are only separated by two sensing rounds and there were more than one sensor that depleted at each of these instances. This observation reveals, as a salient characteristic, that this strategy enables almost all sensors to prolong their operation lifespan. The balance of energy consumption is evident where the positions of depleted sensors were seen evenly distributed across the sensing region.

Figure 6

Sensor energy evolution in residual-energy-based adaptive indexing DLT (EnergyDLT) workload allocation. (a) Initial energy onboard sensors, (b) instance when first sensor depleted, and (c) instance when half-sensors depleted.

4.1.4. Distance- and Residual Energy-Rank-Based Reindexing (RankDLT)

With regard to the test with the distance and residual energy ranked reindexing strategy, the results on the evolution of onboard energies are depicted in Figure 7. In Figure 7(b), it is seen that the first sensor depleted at the 6357th sensing round and half of the sensor depleted at the 6487th round, see Figure 7(c). The instance when the first sensor depleted is comparable and at the same order of magnitude with the test for residual energy-based reindexing strategy. In addition, the instance when half-sensors depleted is also close to that of the energy-based strategy. However, since this strategy requires two sorting operations, its implementation may be more costly when compared to the previous strategies. This may be partly caused by the fact that distance based ranking gives fixed ranks once the sensors are deployed in their sensing environment, thus losing the adaptation to the dynamic energy consumption conditions. On the other hand, although the performance is slightly below that of the residual energy based reindexing case, this strategy is still performing better than the standard DLT approach.

Figure 7

Sensor energy evolution in ranking-based adaptive indexing DLT (RankDLT) workload allocation. (a) Initial energy onboard sensors, (b) instance when first sensor depleted, and (c) instance when half-sensors depleted.

4.1.5. Pure Randomization-Based Reindexing (RandomDLT)

For the randomization-based reindexing strategy, the simulation results are presented in Figure 8. As seen in Figure 8(b), the first sensor depleted its energy at the 6244th round while at the 6462th round, half of the sensors depleted. It is also observed that the performance of this strategy is comparable to the residual energy-based and the ranking-based strategies. On the other hand, a particular feature of the randomized reindexing strategy is that its implementation is the simplest. Sensors do not need to report their residual energies to the BS to calculate the workload assignments.

Figure 8

Sensor energy evolution in randomized adaptively indexed DLT (RandomDLT) workload allocation. (a) Initial energy onboard sensors, (b) instance when first sensor depleted, and (c) instance when half-sensors depleted.

4.2. Characteristics of Energy Consumption

The characteristic of energy consumption critically affects the performance of the wireless sensor network. When energies onboard sensors are drained, the WSN will become inoperative. Specifically, the instances or the sensing rounds, that the first sensor dies and half of the sensors in the WSN deplete, are important indicators of the network operation and they will be monitored and discussed below.

4.2.1. First Sensor Energy Depletion

The energies onboard sensors, just before the sensing round that the first sensor depletes its energy, for the approaches under test are plotted in Figure 9. For the standard DLT case, Figure 9(a), since the indices are fixed, sensors with lower indices deplete energies earlier than other sensors which contain residual energies around 5000 J. For the distance-based reindexing strategy, Figure 9(b), a similar situation is observed as in the standard DLT case. However, note that since indexing is based on the distance determined by the initial deployment, the ordering is not in a sequential manner. In Figure 9(c), the energy onboard sensors are depicted for the energy based reindexing strategy. The energy distribution is not ordered, but all of them are at very low values of less than 2 J. This further demonstrates that energy consumptions are well balanced among sensors using this strategy. Energy distribution for the ranking based reindexing strategy is shown in Figure 9(d). The magnitudes of remaining energies, at the order of 80 J, is higher than the energy-based case but is much smaller than the standard DLT and distance-based DLT cases. The balance of energy consumption among sensors is satisfactory and the whole WSN is able to extend its lifespan. Figure 9(e) shows the energy distribution using the randomization-based reindexing strategy. It is observed that the magnitudes of remaining energies are lager, at 350 J, than the ranked strategy case. There is a trade-off for the implementation simplicity using the randomization-based reindexing strategy.

Figure 9

Characteristics of energy consumption when the first sensor depletes. (a) Standard DLT (SDLT), (b) distance-based reindexing DLT (DisDLT), (c) energy-based reindexing DLT (EnergyDLT), (d) rank-based reindexing DLT (RankDLT), and (e) randomization-based reindexing DLT (RandomDLT).

4.2.2. Half-Sensors Energies Depletion

In another set of tests, the energies onboard sensors just before the sensing round that half of the sensors would deplete their energies are plotted in Figure 10. For the standard DLT case, Figure 10(a), sensor indices are fixed, sensors with lower indices deplete energies first while the other sensor still contain large amount of residual energies around 4000 J. For the distance-based reindexing strategy, Figure 10(b), the result is similar to that in the standard DLT case. However, note that since indexing is based on the distance determined by the initial deployment, the ordering is no more sequential. In Figure 10(c), for the energy-based reindexing strategy, the energies onboard sensors when half of the sensors deplete are drawn. The energy distribution is not ordered, but all of them are at very low values of less than 1 J. It is illustrated that energy consumption is well balanced among sensors using this strategy. Energy distribution for the ranking-based reindexing strategy is shown in Figure 10(d). The magnitudes of remaining energies, at the order of 40 J, are higher than the energy-based case but are significantly smaller than the standard DLT and distance-based DLT cases. The balance of energy consumption among sensors is satisfactory and the lifespan of the whole WSN is extended. Figure 10(e) shows the energy distribution using the randomization-based reindexing strategy. A similar characteristic is noted as in the previous ranked strategy case. However, it is observed that the magnitudes of remaining energies are lager, at 180 J, than the ranked strategy case. This slight degradation in energy consumption balance is a trade-off for the implementation simplicity using the randomization-based reindexing strategy.

Figure 10

Characteristics of energy consumption when half of the sensors deplete. (a) Standard DLT (SDLT), (b) distance-based reindexing DLT (DisDLT), (c) energy-based reindexing DLT (EnergyDLT), (d) rank-based reindexing DLT (RankDLT), and (e) randomization-based reindexing DLT (RandomDLT).

4.3. Test Statistics

The mean values of the life sensors against sensing rounds for the proposed reindexing schemes and the standard deviations obtained from the tests are presented and discussed below. Furthermore, it is regarded here that when the first sensor depleted its energy, the WSN is said to be starting degradation. When less than 50% of the sensors remain operating, the WSN is denoted as inoperative. The distribution of sensing rounds of the above two instances that occurred in the tests are shown in Figures 11, 12, and 13.

Figure 11

Distribution of sensing rounds when the first sensor depleted its energy. (a) Standard DLT (SDLT), (b) distance-based reindexing DLT (DisDLT), (c) energy-based reindexing DLT (EnergyDLT), (d) rank-based reindexing DLT (RankDLT), and (e) randomization-based reindexing DLT (RandomDLT).

Figure 12

Distribution of sensing rounds when half-sensors depleted their energies. (a) Standard DLT (SDLT), (b) distance-based reindexing DLT (DisDLT), (c) energy-based reindexing DLT (EnergyDLT), (d) rank-based reindexing DLT (RankDLT), and (e) randomization-based reindexing DLT (RandomDLT).

Figure 13

Statistical summary of the number of life sensors against sensing rounds. (a) Standard DLT (SDLT), (b) distance-based reindexing DLT (DisDLT), (c) energy-based reindexing DLT (EnergyDLT), (d) rank-based reindexing DLT (RankDLT), and (e) randomization-based reindexing DLT (RandomDLT).

4.3.1. First Sensor Energy Depletion

At the instances when that the first sensor depleted its energy, it is observed that all test cases show close approximations to the Gaussian distribution shape, see Figure 11. As indicated by the example cases of energy evolution, the mean values of the standard DLT and distance-based DLT workload allocation cases have lower values, around 1900, as compared to the energy, ranked, and random indexing cases in the range of about 6300 rounds. The ranges of the sensing rounds when the first sensor depleted, however, have different features. In the SDLT and DisDLT cases, the standard deviations are 26 and 28 rounds. For the EnergyDLT, RankDLT and RandomDLT cases, the standard deviations are 33, 54, and 70. In particular, in the RankDLT case, the standard deviation is the largest. This can be regarded as it is difficult to predict the performance of the RankDLT reindexing approach.

4.3.2. Half-Sensors Energies Depletion

The distributions for instances of sensing rounds when half of the sensors depleted their energies are plotted in Figure 12. As in the first sensor depletion cases, the distributions here also follow the shape of a Gaussian distribution. The mean values of the SDLT and DisDLT cases are very close at 4871 and 4860, respectively. For the EnergyDLT, RankDLT, and RandomDLT cases, the mean values are larger by a factor of approximately $\mathrm{1.5}$ . The values are 6499, 6487, and 6455. The behavior of the mean values from repeated tests verifies that obtained in the example cases shown in the previous section. With regard to the second order statistic, the standard deviations of all cases center around 33. With the smaller standard deviations as compared to the distributions for first sensor depletion, it can be expected that the sensing rounds for the WSN to become inoperative can be predictable.

4.3.3. Statistical Summary

Figure 13 gives plots of the instances that the first sensor depleted, 10%, 50%, and 90% of the sensors depleted, and the instances when all sensors depleted their energies. For the SDLT and DisDLT cases, the depleting sensing rounds show a slowly decreasing trend. Larger numbers of sensing rounds would expire before the WSN rapidly changes from its start of degrading stage, where the first sensor depleted, to the inoperative stage. On the contrary, the EnergyDLT, RankDLT, and RandomDLT cases all show that the WSN changes from degrading to inoperative stage after the expiry of a large number of sensing rounds. This feature indicates that these reindexing schemes are effective in extending the lifespan of WSNs.

4.3.4. Comparison

Figure 14 shows a comparison of the mean values of the ratio of life sensors against the sensing rounds. It is seen that DisDLT is very similar to the SDLT approach in performance. The sensing rounds when the first sensor depleted its energy for these two cases are at the order of 1900 rounds. For the RankDLT and RandomDLT schemes, the sensing rounds that the first sensor depleted increased to above 6000 rounds. For the EnergyDLT strategy, the mean time for the first sensor to deplete is increased to about 6500 rounds. Furthermore, it is observed that the death of the first sensor is very close to the instance when all sensors deplete. It can be summarized that the EnergyDLT strategy is the most effective approach. Since the aim of reindexing is to balance sensor energy consumption, and now the energy criterion is directly used in the reindexing scheme, a high performing WSN with prolonged operation duration is obtained. Furthermore, it is noticed that the randomization-based reindexing scheme also provides satisfactory performances.

Figure 14

Comparison of ratio of life sensors between standard and adaptive reindexing DLT for workload allocation.

5. Conclusion

In this paper, approaches are proposed aiming at extending the operation lifespan of a wireless sensor network (WSN) in a clustered star-topology. Approaches using the divisible load theory (DLT) to assign sensing workloads to sensors are considered. By revealing the dependence of the DLT implementation on the ordered indexing of sensors, several adaptive reindexing strategies are formulated and evaluated. These strategies include reindexing based on the distances between sensors to the cluster head, sensor residual energies, double ranked distances and residual energies, and pure randomization. Simulation tests have been conducted and the effectiveness of the proposed approaches is evaluated against the sensing rounds when the first sensor would deplete its energy as well as the instance when half of the sensors deplete. Results have verified that the energy-based reindexing scheme is the most effective approach in the sense of longest lifespan and sensor deaths at evenly located positions. Moreover, the randomization-based reindexing scheme is an attractive approach because of its implementation simplicity. By using these strategies, energy consumptions among sensors are well balanced and the operation duration of the WSN is significantly increased.