Volume 17 Number 3
May 2020
Article Contents
Tian-Yun Shi, Jian Li, Xin-Chun Jia, Wei Bai, Zhong-Ying Wang, Dong Zhou. Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks[J]. International Journal of Automation and Computing, 2020, 17(3): 439-452. doi: 10.1007/s11633-017-1074-y
Cite as: Tian-Yun Shi, Jian Li, Xin-Chun Jia, Wei Bai, Zhong-Ying Wang, Dong Zhou. Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks[J]. International Journal of Automation and Computing, 2020, 17(3): 439-452. doi: 10.1007/s11633-017-1074-y

Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks

Author Biography:
  • His research interests include intelligent computing theory and application, railway information system, railway intelligent transportation system and wireless sensor networks.

    His research interests include data gathering, topology optimization and wireless communication in wireless sensor networks. E-mail: mrlijian163@163.com

    Her research interests include networked control systems and wireless sensor networks. E-mail: baiweisxu@163.com

    His research interests include channel modeling and wireless sensor networks. E-mail: wzy3652255@163.com

    His research interests include intelligent algorithm and wireless sensor networks. E-mail: xsqf110@126.com

  • Corresponding author: Xin-Chun Jia   received the B. Sc. degree in mathematics from Shanxi University, and M. Sc. degree in operational research and control theory from Chinese Academy of Sciences, China in 1985 and 1988, respectively, and the Ph. D. degree in control science and control engineering from Xi0an Jiaotong University, China in 2003. In 1988, he joined the School of Mathematical Sciences. Currently, he is working as a professor in the School of Mathematical Sciences, Shanxi University, China.
    His research interests include networked control systems, timedelay systems, fuzzy systems and complex systems.
    E-mail: xchjia@sxu.edu.cn (Corresponding author)
  • Received: 2016-02-26
  • Accepted: 2016-11-08
  • Published Online: 2020-05-24
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures (13)  / Tables (2)

Metrics

Abstract Views (781) PDF downloads (10) Citations (0)

Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks

  • Corresponding author: Xin-Chun Jia   received the B. Sc. degree in mathematics from Shanxi University, and M. Sc. degree in operational research and control theory from Chinese Academy of Sciences, China in 1985 and 1988, respectively, and the Ph. D. degree in control science and control engineering from Xi0an Jiaotong University, China in 2003. In 1988, he joined the School of Mathematical Sciences. Currently, he is working as a professor in the School of Mathematical Sciences, Shanxi University, China.
    His research interests include networked control systems, timedelay systems, fuzzy systems and complex systems.
    E-mail: xchjia@sxu.edu.cn (Corresponding author)

Abstract: In order to achieve low-latency and high-reliability data gathering in heterogeneous wireless sensor networks (HWSNs), the problem of multi-channel-based data gathering with minimum latency (MCDGML), which associates with construction of data gathering trees, channel allocation, power assignment of nodes and link scheduling, is formulated as an optimization problem in this paper. Then, the optimization problem is proved to be NP-hard. To make the problem tractable, firstly, a multi-channel-based low-latency (MCLL) algorithm that constructs data gathering trees is proposed by optimizing the topology of nodes. Secondly, a maximum links scheduling (MLS) algorithm is proposed to further reduce the latency of data gathering, which ensures that the signal to interference plus noise ratio (SINR) of all scheduled links is not less than a certain threshold to guarantee the reliability of links. In addition, considering the interruption problem of data gathering caused by dead nodes or failed links, a robust mechanism is proposed by selecting certain assistant nodes based on the defined one-hop weight. A number of simulation results show that our algorithms can achieve a lower data gathering latency than some comparable data gathering algorithms while guaranteeing the reliability of links, and a higher packet arrival rate at the sink node can be achieved when the proposed algorithms are performed with the robust mechanism.

Tian-Yun Shi, Jian Li, Xin-Chun Jia, Wei Bai, Zhong-Ying Wang, Dong Zhou. Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks[J]. International Journal of Automation and Computing, 2020, 17(3): 439-452. doi: 10.1007/s11633-017-1074-y
Citation: Tian-Yun Shi, Jian Li, Xin-Chun Jia, Wei Bai, Zhong-Ying Wang, Dong Zhou. Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks[J]. International Journal of Automation and Computing, 2020, 17(3): 439-452. doi: 10.1007/s11633-017-1074-y
  • The sensed data is forwarded to the sink node through collaboration and multi-hops among sensor nodes to realize data gathering, which is one of the primary functions in wireless sensor networks (WSNs). Nowadays, the WSNs have been used to gather data for monitoring purposes in various areas, especially, there exist some special monitoring scenarios, such as monitoring the long laneways in underground mines[1], monitoring power lines[2], monitoring high-speed railways and acquiring the traffic state of roadways, etc, in which their structures are characterized by long-distance and strip-type.

    In recent years, with the rapid development of the high-speed railways in China, the operational safety of high-speed trains has attracted more and more attention. Some emergencies around the railways, e.g., the tunnel collapsing, deformation of the viaducts and landslides along the railway, can threaten the safety of running trains. Therefore, seeking a suitable data gathering network is a significant topic for monitoring the environment of running trains.

    To guarantee the operational safety of high-speed trains, the data gathering in WSNs deployed around the railways must be of low-latency and high-reliability to provide timely and accurate monitoring information, where the WSNs are heterogeneous as they consist of three types of nodes, namely, a sink node, some relay nodes and sensor nodes. For the heterogeneous wireless sensor networks (HWSNs) monitoring the environment of running trains, we will investigate the problem of multi-channel-based data gathering with minimum latency (MCDGML) in this paper, which associates with construction of data gathering trees, channel allocation, power assignment of nodes and link scheduling. To achieve a low-latency and high-reliability data gathering, MCDGML problem is formulated as an optimization problem with the objective of minimizing data gathering latency, while guaranteeing the signal to interference plus noise ratio (SINR) of all scheduled links is not less than a certain threshold to satisfy the reliability of links.

    Next, we show the optimization problem is NP-hard and divide the problem into two subproblems for seeking a suboptimal solution: 1) constructing data gathering trees, 2) scheduling links with power assignment. For the first subproblem, we optimize the topology of nodes and propose a multi-channel-based low-latency (MCLL) algorithm, which constructs several subtrees rooted at the sink node to share the traffic load as balanced as possible. Especially, the constructed subtrees are vertex-disjoint except the sink node. The MCLL algorithm also allocates the interference-free orthogonal channels for these subtrees to eliminate the interferences of links, thus, the number of parallel transmissions is increased.

    For the second subproblem, a maximum links scheduling (MLS) algorithm is proposed by considering the power assignment of nodes, which can schedule as many links as possible to transmit in each time slot and guarantee that the SINR constraints of all scheduled links are satisfied. More specifically, the MLS algorithm searches a maximum set of schedulable links and schedules the links in the set to transmit for each time slot. Thus the latency of data gathering can be minimized by equivalently minimizing the number of time slots allocated to links in a round of data gathering.

    Finally, due to the hardware degradation of nodes and the serious interferences from other equipment around railways, considering that the dead nodes or failed links may occur, a robust mechanism is proposed by using a one-hop weight to select certain assistant nodes to complete the delivery of data packets. The contributions of this paper are summarized as follows:

    1) For the data gathering of HWSNs used to monitor the environment of running trains, a multi-channel-based low-latency algorithm and a maximum links scheduling algorithm are proposed to achieve the lower latency and high-reliability.

    2) A simple and practical allocation mechanism of channels, which can eliminate the interferences of links and increase the number of schedulable links in each time slot, is introduced.

    3) To ensure that the sensing data of sensor nodes are forwarded to the sink node more efficiently, a robust mechanism is proposed, which aims to deal with the interruption problem of data gathering caused by dead nodes or failed links.

    The remainder of this paper is organized as follows. Section 2 summarizes the related works. The heterogeneous network model and the problem formulation are presented in Section 3. Section 4 designs some algorithms for solving the formulated problem. Some simulation results are presented in Sections 5. Section 6 concludes the paper.

  • The timeliness of data gathering in WSNs has been extensively investigated. To improve the latency for the data gathering, some distributed algorithms were proposed to optimize the process of data gathering and the theoretical performance bounds for the latency were presented in [3, 4]. A time division multiple access (TDMA) protocol used to assign appropriate time slots for transmitting and receiving, and the corresponding scheduling algorithm for data gathering were proposed in [5]. The proposed scheduling algorithm can decrease the number of retransmission caused by packet collisions and improve the timeliness of data gathering.

    In addition, some researchers can achieve the more parallel links for transmitting by allocating different channels for nearby links, thus the timeliness of data gathering is improved. Xiao[6] indicated that the physical layer of IEEE 802.11a supports 13 orthogonal channels, which can be used to communicate simultaneously. Zhang et al.[7, 8] proposed a multi-channel MAC (MMAC) protocol and a decentralized non-global MAC (DNG-MAC) mechanism, respectively, which can be used for multiple channels. Some distributed protocols for channel allocation in WSNs were investigated to minimize the interference of links[9], therefore, the number of schedulable links in each time slot is increased and the latency of the network is reduced. However, the proposed protocols of channel allocation are too complex to implement, especially for the sensor nodes which have finite computation ability and limited energy supplement. Furthermore, the latency caused by switching channels was neglected.

    In order to improve the reliability of data gathering in WSNs, a multi-path structure for data gathering was constructed through the rings overlay, and an enhanced relay scheme for improving the reliability of data gathering was presented[10]. Similar works focus on the multi-path structure[11, 12]. Sitanayah et al.[13] presented a fault-tolerant relay placement algorithm for ensuring k vertex-disjoint paths, which can avoid the dependence on some common nodes in multi-path structure. Although a higher reliability is obtained, a large amount of energy can be wasted since the mechanism of multiple paths forwards lots of redundant data.

    The robustness of data gathering is closely related to topology control in WSNs. Cardei et al.[14-16] proposed some fault-tolerant topology control algorithms and some power assignment strategies in WSNs such that the resulting network topologies are $ k $-vertex connected. However, Laszka et al.[17] pointed out that the connectivity of the network fails to well capture the robustness since the connectivity to the sink node is usually neglected, and then proposed a new metric of robustness called persistence. To improve the robustness of the network, some efficient heuristic algorithms for optimizing the deployment of the sink node were presented based on the new metric. The works above can achieve a stronger connectivity through enhancing the transmitted power of nodes, however, the reliability of links becomes worst because the interferences among links are increased unintentionally. In addition, to obtain the energy-efficient and fault-tolerant performance, distributed clustering and routing algorithms were presented jointly in hierarchical WSNs[18-19].

    A maximum cover problem with the objective of maximizing network lifetime was investigated and proved to be NP-complete in WSNs[20]. Chen et al.[20] proposed a maximum connected load-balanced cover tree (MCLCT) algorithm to achieve a longer network lifetime as well as full coverage by dynamically forming load-balanced routing cover trees. For the chain-type WSNs, an energy-efficient chain formation algorithm for data gathering was presented[21], which resolves the unbalanced energy consumption problem caused by long-distance delivery of data packets in the chain. There exist abundant works on improving the unbalanced load of sensor nodes, such as [22, 23]. However, these literatures do not consider the timeliness and reliability of networks.

    For the timeliness and reliability of data gathering in WSNs, the problems of constructing data gathering tree, power assignment and link scheduling were investigated and corresponding algorithms were presented in [24]. However, the considered network model is a homogeneous wireless sensor network and the ranges of transmitted powers of all nodes are the same in [24]. Furthermore, Gong and Yang implied successful transmissions of all links and ignored the malfunctions of nodes or links. The dead nodes or failed links can interrupt the process of corresponding data gathering, which motivates us to investigate a robust mechanism to suppress the interruption of data gathering.

  • Now, we consider a common situation that a slope around the railways is a few kilometers away from a rail-side room which are located in the surrounding of railways after every 3 kilometers. In order to monitor the slope and realize the warning for the emergency, a sink node is deployed around the rail-side room, which can provide sufficient energy to transmit the sensed data received from some sensor nodes to the passing trains.

    Meanwhile, the sensor nodes are deployed on the slope to acquire various information such as humidity, ground settlement and structural distortion, etc. Some relay nodes are deployed along a railway to forward the sensing data generated by sensor nodes in a multi-hops way so that the sink node receives the sensing data. Especially, it is assumed that every relay node has a larger communication radius than that of each sensor node for the long-distance forwarding. The whole strip-type monitoring network is shown in Fig. 1. The WSNs in Fig. 1 are heterogeneous, which includes three types of nodes with different functions, namely, the sink node, the relay nodes and sensor nodes.

    Figure 1.  Model of HWSNs monitoring the slope around a high speed railway

    It has been proved in [25] that the total energy consumption is minimum for the uniformly deployed nodes in linear WSNs. Hence the relay nodes are uniformly deployed along the railways and the deployment is based on redundancy to effectively forward data in our network.

    For the HWSNs, the network topology is represented by a directed graph $ G = (V, L) $, where $ V $ is the set of all nodes in the network, namely, including a sink node, sensor nodes and relay nodes. $ L $ corresponds to the set of directed links among all the nodes. And let $ S $ and $ R $ to be the sets of the sensor nodes and the relay nodes, respectively.

  • For the MCDGML problem, the relevant problems, i.e., the data gathering, link scheduling and the reliability of links, are stated in this subsection. Then, the MCDGML problem is formulated as an optimization model.

    1) Data gathering

    Let the set $ D $ denote the data packets generated by the all sensor nodes in a round of data gathering, where $ D = \cup_{v_i\in S}D(v_i) $, $ D(v_i) $ is the data packets generated by the $ i $-th sensor node. As stated in Section 3.1, the sensor nodes collect different types of data for monitoring the slope around railways. A round of data gathering is completed when $ D $ is forwarded to the sink node. A large enough constant $ N $ is used to confine the number of time slots allocated to the links in a round of data gathering. Thus, the allocated time slot $ t $ satisfies

    $ \begin{align*} 1\leq t\leq N. \end{align*} $

    In a round of data gathering, a subset of $ L $ will be scheduled to form a data gathering tree $ T $ rooted at the sink node and Fig. 2 shows the data gathering tree.

    Figure 2.  A data gathering tree in HWSNs

    In Fig. 2, the solid arrows denote the scheduled links in a round of data gathering. The numbers beside the nodes are the amount of data packets being transmitted in current time slot. And the set $ L $ consists of all the links represented by solid arrows and dotted arrows, while the links of dotted arrows are not scheduled in Fig. 2, i.e., they are not on the tree.

    2) Link scheduling

    The binary variables $ X(v_i, v_j) $ and $ Y^t(v_i, v_j) $ are defined to indicate whether link $ (v_i, v_j) $ is on the tree $ T $ and is scheduled to transmit data in time slot $ t $, respectively.

    $ \begin{align*} X(v_i, v_j) = \left\{ \begin{array}{ll} 1, & (v_i, v_j)\in T\\ 0, & \rm{otherwise} \end{array} \right. \end{align*} $

    $ \begin{align*} Y^t(v_i, v_j) = \left\{ \begin{array}{ll} 1, & (v_i, v_j)\ {\rm{is\ activated\ in}}\ t, \; 1\leq t\leq N \\ 0, & \rm{otherwise}. \end{array} \right. \end{align*} $

    As only the links on the tree $ T $ can be scheduled in a round of data gathering, we have

    $ \begin{align*} Y^t(v_i, v_j)\leq X(v_i, v_j), \quad\forall (v_i, v_j)\in L. \end{align*} $

    Without loss of generality, we make assumptions that only one data packet is received or transmitted in a time slot and the data is not aggregated in the process of delivery. The number of all time slots for receiving at the sink node should equal to the number of data packets generated by all sensor nodes in a round of data gathering, hence, we have

    $ \begin{align*} \sum\limits_{1\leq t\leq N}\sum\limits_{v_j\in\bf R}Y^t(v_j, Sink) = \sum\limits_{v_i\in S}D(v_i). \end{align*} $

    For the leaf nodes on $ T $, as they only transmit their own data to parent nodes and do not receive the data from other nodes, the number of time slots for transmitting should equal to the number of data packets generated by themselves.

    $ \begin{align*} \sum\limits_{1\leq t\leq N}\sum\limits_{v_i\in V\setminus Sink\atop j\neq i}Y^t(v_j, v_i) = D(v_j), \quad \forall v_j\in leaf. \end{align*} $

    The remaining sensor nodes on $ T $ need to transmit their own data and the data received from their children. Thus, the number of time slots used to receive from their children plus the number of their own data packets should equal to the number of time slots for transmitting. Thus, for any $ v_j\in S\setminus leaf $, we have

    $ \begin{align*} \sum\limits_{1\leq t\leq N}&\sum\limits_{v_m\in V\setminus Sink\atop j\neq m}Y^t(v_j, v_m) = D(v_j)+\; \; \; \; \; \; \; \; \; \; \\&\sum\limits_{1\leq t\leq N}\sum\limits_{v_i\in S\atop i\neq j}Y^t(v_i, v_j). \end{align*} $

    Since the relay nodes deployed along a railway only forward the data of sensor nodes, the numbers of time slots for transmitting and receiving are equal. For any $ v_j\in {\bf R} $, we have

    $ \begin{align*} \sum\limits_{1\leq t\leq N}\sum\limits_{v_m\in V\setminus S\atop j\neq m}Y^t(v_j, v_m) = \sum\limits_{1\leq t\leq N}\sum\limits_{v_i\in V\setminus Sink\atop i\neq j}Y^t(v_i, v_j). \end{align*} $

    In addition, due to the half duplex characteristics of transceivers equipped in the nodes, a node can only transmit or receive in a time slot. Namely, at most, one incoming link or outgoing link can be active for any sensor nodes or relay nodes in the time slot $ t $. This constraint can be expressed by

    $ \begin{align*} &\sum\limits_{v_i\in V\setminus Sink\atop i\neq j}Y^t(v_i, v_j)+\sum\limits_{v_m\in V\atop j\neq m}Y^t(v_j, v_m)\leq 1, \; \nonumber\\&\; \; \; \; \; \; \; \; \; \; \forall v_j\in V\setminus Sink. \end{align*} $

    3) Reliability of links

    As stated previously, to achieve the reliability of links, the SINR of scheduled links should be greater than a certain threshold, which is related to the strength of received effective signal, interferences from other links and the background noise. A well-known propagation model[26] is adopted to estimate the power level of received effective signal. Let $ p(v_j) $ be the power level of received effective signal at the receiver $ v_j $ of link $ (v_i, v_j) $, we have

    $ \begin{equation} p(v_j) = \left(\left(\frac {d_0}{d_{i, j}}\right)^{\rho}\times 10^{\frac {R_{\delta}^{ \rm{d}B}}{10}-\frac {PL_{d_0}^{ \rm{d}B}}{10}}\right)\times p(v_i) \end{equation} $

    (1)

    where $ p(v_i) $ is the power level at the transmitter $ v_i $ of link $ (v_i, v_j) $ in watt, $ d_0 $ is a reference distance used by the model and $ PL_{d_0}^{ \rm{d}B} $ is the propagation loss at $ d_0 $ in decibel. $ d_{i, j} $ is the distance between nodes $ v_i $ and $ v_j $. $ \rho $ is the propagation loss exponent and $ R_{\delta}^{ \rm{d}B} $ is a zero-mean Gaussian random variable with a standard deviation $ \delta $.

    Let $ g(v_i, v_j) $ denote the channel gain from $ v_i $ to $ v_j $ and the propagation model above can be abbreviated as

    $ \begin{align*} p(v_j) = g(v_i, v_j)\times p(v_i). \end{align*} $

    The interferences occur only in the case that a set of links are scheduled in the same time slot, hence the SINR of link $ (v_i, v_j) $ is different in most cases due to the changes of its transmitting power and the interference sources. Especially, if a link $ (v_i, v_j) $ is not scheduled, we say the SINR of link $ (v_i, v_j) $ equals to zero. Now, let $ \eta^t(v_i, v_j) $ denote the SINR of link $ (v_i, v_j) $ in time slot $ t $, we have

    $ \begin{align*} \eta^t&(v_i, v_j) = \\&\frac{p(v_i)\times g(v_i, v_j)\times Y^t(v_i, v_j)}{\sum\limits_{v_m\in V\setminus Sink\atop m\neq i}\sum\limits_{n\in V\atop n\neq j}p(v_m)\times g(v_m, v_j)\times Y^t(v_m, v_n) +B(v_j)} \end{align*} $

    where the first term in the denominator denotes the interferences on receiver $ v_j $ of link $ (v_i, v_j) $ from all other scheduled links in the time slot $ t $. $ g(v_m, v_j) $ is the interference gain from other transmitter $ v_m $ to $ v_j $. $ B(v_j) $ corresponds to the background noise at $ v_j $.

    Let $ \lambda $ denote the SINR threshold value and the SINR constraint of link $ (v_i, v_j) $ in time slot $ t $ can be expressed as

    $ \begin{align*} \eta^t(v_i, v_j)\geq \lambda\times Y^t(v_i, v_j), \quad \forall (v_i, v_j)\in L. \end{align*} $

    In this paper, the network model has a heterogeneous structure in which the relay nodes have a larger communication radius compared with the sensor nodes. Moreover, the transmitted powers are adjustable for the two types of nodes in their ranges of powers, namely

    $ \begin{align*} &p_{ \rm{min}}\leq p(v_i)\leq p_{\max}, v_i\in S \\ &p {'}_{\min}\leq p{'}(v_j)\leq p'_{\max}, v_j\in {\bf R}. \end{align*} $

    In order to further reduce the interferences among the links and increase the number of schedulable links in each time slot, a multi-channel-based mechanism is adopted for data gathering in this paper. Let $ C $ denote the set of some available orthogonal channels in the network and

    $ \begin{align*} C = \left\{c_1, c_2, \cdots, c_l\right\}. \end{align*} $

    In our multi-channel-based mechanism, the orthogonal channels in $ C $ will be allocated to each subtree rooted at the sink node for eliminating the interferences among the links on different subtrees, thus, the number of constructed subtrees cannot be larger than the size of $ C $.

    On the other hand, the number of constructed subtrees is related to the distance between two adjacent relay nodes which are deployed along the railway. To guarantee the reliability of links, the number of constructed subtrees, which is denoted as $ K $, should satisfy: $ K\leq \lfloor \frac{d_m}{d}\rfloor $, where $ \lfloor\cdot\rfloor $ denotes rounding down to the integer and $ d $ is the distance between two adjacent relay nodes. $ d_m $ is the maximum distance of link reliability that satisfies the SINR constraints of links when the relay nodes transmit at the power $ p_{\max} $. $ d_m $ can be obtained by (1) and (10) since the interference and background noise can be measured by received signal strength indicator (RSSI)[9].

    Hence, the number of constructed subtrees is determined by

    $ \begin{align*} K = \min\left\{\lfloor \frac{d_m}{d}\rfloor, | C|\right\} \end{align*} $

    where $ | C| $ denotes the number of available channels in $ C $.

    Constructing $ K $ subtrees increases the transmission distance of relay nodes and the energy consumption of transmitting data. However, the relay nodes can be supplied energy by some facilities along the railways, thus, the latency and reliability of the network are mainly considered in the paper.

    4) The optimization problem

    Let $ F(T) $ denote a time frame which consists of consecutive time slots allocated to the scheduled links on the tree $ T $ in a round of data gathering. We minimize the length $ |F(T)| $ of the time frame to equivalently achieve a minimum latency of data gathering. Then, the MCDGML problem is formulated as an optimization model as follows, and the optimization model is abbreviated as MCDGML-OP in this paper.

    Minimize

    $ \begin{align*} |F(T)| \end{align*} $

    subject to

    $ \begin{align} &Y^t(v_i, v_j)\leq X(v_i, v_j), \; \forall (v_i, v_j)\in L, \; 1\leq t\leq N \end{align} $

    (2)

    $ \begin{align} &\sum\limits_{1\leq t\leq N}\sum\limits_{v_j\in {\bf R}}Y^t(v_j, Sink) = \sum\limits_{v_i\in S}D(v_i) \end{align} $

    (3)

    $ \begin{align} &\sum\limits_{1\leq t\leq N}\sum\limits_{v_i\in V\setminus Sink\atop j\neq i}Y^t(v_j, v_i) = D(v_j), \; \forall v_j\in leaf \end{align} $

    (4)

    $ \begin{align} \sum\limits_{1\leq t\leq N}& \sum\limits_{v_m\in V\setminus Sink\atop j\neq m}Y^t(v_j, v_m) = \\ & D(v_j)+\sum\limits_{1\leq t\leq N}\sum\limits_{v_i\in S\atop i\neq j}Y^t(v_i, v_j), \; \; \forall v_j\in S\setminus leaf \end{align} $

    (5)

    $ \begin{eqnarray} &&\sum\limits_{1\leq t\leq N}\sum\limits_{v_m\in V\setminus S\atop j\neq m}Y^t(v_j, v_m) = \sum\limits_{1\leq t\leq N}\sum\limits_{v_i\in V\setminus Sink\atop i\neq j}Y^t(v_i, v_j), \\ && \quad \forall v_j\in {\bf R} \end{eqnarray} $

    (6)

    $ \begin{align} &\sum\limits_{v_i\in V\setminus Sink\atop i\neq j}Y^t(v_i, v_j)+\sum\limits_{v_m\in V\atop j\neq m}Y^t(v_j, v_m)\leq 1, \\& \quad \forall v_j\in V\setminus Sink \end{align} $

    (7)

    $ \begin{align} &p_{\min}\leq p(v_i)\leq p_{\max}, \; \; v_i\in S \end{align} $

    (8)

    $ \begin{align} &p{'}_{\min} \leq p {'}(v_j)\leq p{'}_{\max} , \; \; v_j\in {\bf R} \end{align} $

    (9)

    $ \begin{align} &\eta^t(v_i, v_j)\geq \lambda\times Y^t(v_i, v_j), \; \; \forall (v_i, v_j)\in L \end{align} $

    (10)

    $ \begin{align} & C = \left\{c_1, c_2, \cdots, c_l\right\} \end{align} $

    (11)

    $ \begin{align} &K = \min\left\{\lfloor \frac{d_m}{d}\rfloor, | C|\right\} \end{align} $

    (12)

    where (2)$ - $(7) are the constraints of data gathering and links scheduling, (8) and (9) specify the ranges of transmitted power for the sensor nodes and relay nodes. (10) corresponds to the SINR constraints of links. The constraint of available channels is expressed as (11) and the number of constructed subtrees is determined by (12).

    For the above MCDGML-OP problem, we have Lemma 1.

    Lemma 1. The MCDGML-OP problem in HWSNs is NP-hard.

    Proof. As it has been proved that the SINR-based data gathering problem in [24] is NP-hard, a reduction process is used to prove the NP-hardness of our MCDGML-OP problem. We reduce the SINR-based data gathering problem to our MCDGML-OP problem from the following two aspects.

    On one hand, a single channel is adopted in the SINR-based data gathering problem, which is a special case of our mechanism that multiple channels are allocated to links of different subtrees, especially, both are similar when the number of elements in $ C $ satisfies $ | C| = 1 $.

    On the other hand, our data gathering is based on the HWSNs in which the sensor nodes and relay nodes have different ranges of transmitting power. The links among relay nodes are considered except the links of sensor nodes in our network model, thus, our data gathering problem is more complexity than the SINR-based data gathering problem.

    Hence, the SINR-based data gathering problem is a special case of our MCDGML-OP problem. As the special-case of our formulated problem is already NP-hard, the general MCDGML-OP problem is NP-hard.

  • As our MCDGML-OP problem is NP-hard, to make the problem tractable, the problem is divided into two subproblems for seeking its suboptimal solution: constructing data gathering trees and scheduling links with the power assignment. And corresponding algorithms are presented for the two subproblems.

  • In this subsection, a data gathering tree is constructed by optimizing the topology of the nodes. The latency of data gathering is related to the topology of nodes, on one hand, the congestion of data traffic in networks can cause the waiting delay in the queue of data packets being transmitted. To avoid excessive congestion, the traffic load in the network should be distributed uniformly over several subtrees rooted at the sink node, and there are no common nodes shared by these subtrees except the sink node.

    An example is given in Fig. 3. The vertex-disjoint backbone subtrees, $ e-c-a $ and $ f-d-b-a $, are formed by some relay nodes. Assuming that the data traffic of cluster $ B $ consisting of several sensor nodes can be forwarded by connecting to relay nodes $ e $ or $ f $. Since the cluster $ A $ has been connected with the relay node $ e $ to form a subtree $ A-e-c-a $, to avoid excessive congestion of data traffic, cluster $ B $ should select the relay node $ f $ rather than $ e $ to connect to the sink node $ a $.

    Figure 3.  Distributing traffic loads over two subtrees

    On the other hand, a sensor node should add to a tree through the node with a smaller degree, that is because a larger degree usually means that a heavier conflict of links may occur, which can reduce the number of schedulable links. Therefore, the traffic load and the degree of node should be considered when constructing a data gathering tree. A definition of traffic load of a tree is given as follows.

    Definition 1. Traffic load of a tree. The sum of data packets generated by all sensor nodes of a tree in a round of data gathering is defined as the traffic load of the tree.

    Now we let $ load(T_i) $ and $ degree(v_i) $ denote traffic load of the tree $ T_i $ and degree of the node $ v_i $, respectively. An algorithm is presented to construct a data gathering tree for the multi-channel-based low-latency, and is called the MCLL algorithm whose pseudo code is given in Algorithm 1. The data gathering tree constructed by our MCLL algorithm consists of $ K $ vertex-disjoint subtrees rooted at the sink node and each subtree occupies an orthogonal channel.

    Algorithm 1. Constructing a data gathering tree for multi-channel-based low latency

    Input: Set of sensor nodes $ S $, set of relay nodes $ R $ and the sink node $ Sink $, set of directed links $ L $.

    Output: A data gathering tree $ T $ consisting of $ K $ subtrees.

    1) Initialize $ d, d_m, C $

    2) Initialize relay nodes integer $ id $ starting from 1 in order from $ Sink $

    3) $ K\leftarrow \min\left\{\lfloor \frac{d_m}{d}\rfloor, | C|\right\} $

    4) for each relay node $ r \in\mathcal {\bf R} $ do

    5)    $ M_r\leftarrow id\bmod K $

    6)    broadcast the $ hello\_message $ including $ id $ and $ M_r $

    7)    if $ M_r = M_{r'} $ then

    8)      add $ r' $ to $ neighbor\_list $

    9)    else

    10)      discard the $ hello\_message $

    11)    end if

    12) end for

    13) for $ i = 1 $ to $ K $ do

    14)    $ Sink $ add to $ T_i $

    15)    the relay nodes with Mod $ i-1 $ add to $ T_i $ by $ Sink $

    16)    $ load\; (T_i)\leftarrow 0 $

    17) end for

    18) $ T\leftarrow \cup_{i = 1}^{K}T_i $

    19) while there exists sensor node $ s\in S $ not add to $ T $

    do

    20)    compute $ load $ of trees within $ s $

    21)    $ T^{\ast}\leftarrow T_j $ with minimum $ load $

    22)    $ degree^{\ast}\leftarrow infinity $

    23)    for each $ v\in T^{\ast} $, $ (s, v)\in L $ do

    24)    $ degree^{temp}\leftarrow degree(v) $

    25)    if $ degree^{temp}<degree^{\ast} $ then

    26)      $ v^{\ast}\leftarrow v $

    27)      $ degree^{\ast}\leftarrow degree^{temp} $

    28)     end if

    29)   end for

    30)    $ s $ add to $ T_j $ by $ (s, v^{\ast}) $

    31)    update $ load(T_j) $ and $ degree(v) $

    32) end while

    33) for each subtree $ T_i $ do

    34)    allocate the channel $ c_i $ to $ T_i $ from $ C $

    35) end for

    36) update $ T $

    At the beginning of the MCLL algorithm, the number of constructed subtrees is determined by (12). Considering that the relay nodes do not generate sensing data, the relay nodes are organized to form $ K $ backbone subtrees rooted at the sink node which are distributed in the network evenly. To realize this process, the relay nodes perform the modulus operator, and form chain-type backbone subtrees with the relay nodes that have the same modulus (see the lines 4$ - $17 of Algorithm 1).

    After the $ K $ backbone subtrees are formed, the sensor node $ s $ obtains the traffic loads from all the available subtrees, then add to the subtree $ T^{\ast} $ with the minimum traffic load by connecting with the node $ v^{\ast} $ of $ T^{\ast} $, where $ (s, v^{\ast})\in L $ and the $ degree(v^{\ast}) $ is minimum (lines 19$ - $32 in Algorithm 1). When all the sensor nodes add to the $ K $ subtrees, each subtree chooses and occupies an orthogonal channel from $ C $, respectively (see the lines 33$ - $35 of Algorithm 1).

  • 1) Power assignment

    A data gathering tree $ T $ consisting of $ K $ vertex-disjoint subtrees rooted at the sink node is constructed by the MCLL algorithm. Although the different channels are allocated to the $ K $ subtrees, the interferences among links scheduled in some time slots can still exist in a subtree such that the SINR constraints cannot be satisfied.

    Let $ Q = \left\{l_1, l_2, \cdots, l_q\right\} $ be a subset of links in a subtree and the link number of $ Q $ is $ q $, where $ l_i $ represents the $ i $-th link in $ Q $. Due to the uncertainty of the background noises and the accumulation of interferences, it is a hot problem to determine whether there exists a power assignment vector to simultaneously satisfy the SINR constraints for the link set $ Q $. Nevertheless, we can first consider the special case that the background noises are neglected.

    When the background noises are neglected, for the link $ l_i $ in $ Q $, the SINR constraint in a time slot can be written as

    $ \begin{align*} \eta(l_i) = &\frac {p(l_i)\times g(l_i, l_i)}{\sum\limits_{l_j\in Q, j\neq i}p(l_j)\times g(l_j, l_i)} = \frac {p(l_i)}{\sum\limits_{l_j\in Q, j\neq i}p(l_j)\times G_{i, j}}\geq \lambda \end{align*} $

    where

    $ \begin{align} G_{i, j} = \left\{ \begin{array}{ll} 0, & i = j\\ \dfrac {g(l_j, l_i)}{g(l_i, l_i)}, & i\neq j \end{array} \right.\\[-7mm] \end{align} $

    (13)

    $ p(l_i) $ and $ p(l_j) $ correspond to the transmitting powers of the links $ l_i $ and $ l_j $, respectively. $ g(l_j, l_i) $ denotes the interference gain from the link $ l_j $ to the link $ l_i $ and $ g(l_i, l_i) $ is the channel gain of the link $ l_i $.

    Thus, a gain matrix $ G\in {\bf R}^{q\times q} $ is defined for the link set $ Q $ as

    $ \begin{align*} G = \left[\begin{array}{cccc} 0 & \dfrac{g(l_2, l_1)}{g(l_1, l_1)} & \ldots & \dfrac{g(l_q, l_1)}{g(l_1, l_1)}\\ \dfrac{g(l_1, l_2)}{g(l_2, l_2)} & 0 & \ldots & \dfrac{g(l_q, l_2)}{g(l_2, l_2)}\\ \vdots & \vdots & \vdots & \vdots\\ \dfrac{g(l_1, l_q)}{g(l_q, l_q)} & \dfrac{g(l_2, l_q)}{g(l_q, l_q)} & \ldots & 0 \end{array} \right] \end{align*} $

    where the $ (i, j) $-th element of the gain matrix $ G $ is given by (13). Obviously, $ G $ is a nonnegative square matrix.

    For the case of neglecting the background noises, we have Lemma 2 from the above analysis and the related results in [26, 27].

    Lemma 2. When the background noise is ignored, all the links in $ Q $ can be scheduled simultaneously if and only if the reciprocal of the Perron eigenvalue $ \rho(G) $ of the matrix $ G $ is not less than the SINR threshold $ \lambda $, and the power assignment vector $ P $ for the links in $ Q $ is the Perron eigenvector corresponding to the Perron eigenvalue, where the Perron eigenvalue of a nonnegative square matrix is its largest positive eigenvalue.

    However, for a real-world scenario, the background noises must be considered, further, Lemma 3 is given to determine whether the SINR constraints of the links in $ Q $ can be satisfied by combining with the related results in [26, 27].

    Lemma 3. When the background noise is considered, i.e., $ B = (B_1, B_2, \cdots, B_q)>0 $, $ B_i $ denotes the background noise strength experienced by the link $ l_i $ in $ Q $, for any positive value $ \varepsilon $, there exists a constant $ c $

    $ \begin{equation} c\geq \operatorname*{max}\limits_{1\leq i\leq q}\left\{\frac{B_i}{p(l_i)\times g(l_i, l_i)(\varepsilon^{-1}-\rho(G))}\right\} \end{equation} $

    (14)

    such that the SINR constraint of any link in $ Q $ is not less than $ \frac{1}{\rho(G)}-\varepsilon $. And the corresponding power assignment vector for the links in $ Q $ is $ cP $, where $ \rho(G) $ and $ P $ are the Perron eigenvalue and eigenvetor of the gain matrix $ G $, respectively.

    Hence, in the case of considering the background noises, we can achieve a SINR threshold for any link in $ Q $ that is arbitrarily close to $ \lambda $ when the Perron eigenvalue $ \rho(G) $ of the gain matrix $ G $ satisfies $ \frac{1}{\rho(G)}\geq\lambda $. And the power assignment vector of the links in $ Q $ is $ cP $, where $ \rho(G) $ and $ P $ are Perron eigenvalue and eigenvetor of the gain matrix $ G $, respectively, and $ c $ is a constant that satisfies (14).

    Considering the ranges of transmitting power of sensor nodes and relay nodes (see formulas (8) and (9)), the elements in the Perron eigenvector of $ G $ should lie in $ [\sigma_{\min}, \sigma_{\max}] $, where $ \sigma_{\min} $ and $ \sigma_{\max} $ are given by (15) and (16), respectively.

    $ \begin{align} \sigma_{\min} = \left\{ \begin{array}{ll} \dfrac{p_{\min}}{c} & v\in S\\ \dfrac {p{'}_{\min} }{c} & v\in {\bf R} \end{array} \right.\\[-6mm] \end{align} $

    (15)

    $ \begin{align} \sigma_{\max} = \left\{ \begin{array}{ll} \dfrac{p_{\max}}{c} & v\in S\\ \dfrac {p{'}_{\max} }{c} & v\in {\bf R} \end{array} \right.\\[-6mm] \end{align} $

    (16)

    where $ v $ is the sender of the link whose transmitted power corresponds to the corresponding element in the Perron eigenvector of $ G $.

    2) Power-based interference graph

    For the sake of our investigation on link scheduling, a power-based interference graph is introduced firstly. As stated early, the links sharing a common node cannot be scheduled simultaneously due to the half duplex characteristics of transceivers equipped in nodes. Furthermore, only those links whose senders have the data (sensing from environment or receiving from their children) being transmitted are considered to be scheduled. Meanwhile, the scheduled links in each time slot should satisfy the SINR constraints to achieve the reliability of links, thus, the links that fail to satisfy the SINR constraints cannot be scheduled.

    Based on the above analysis, combining with Lemmas 2 and 3, the power-based interference graph, $ I = \left\{I_1, I_2, \cdots, I_K\right\} $ can be generated for the $ K $ subtrees rooted at the sink node, where $ I_i $ represents the interference graph of the $ i $-th subtree. Fig. 4 shows a power-based interference graph corresponding to the data gathering tree in Fig. 2.

    Figure 4.  Power-based interference graph corresponding to the data gathering tree in Fig. 2

    In Fig. 4, a vertex represents the link that has data packets being transmitted in current time slot, and the neighboring number is the current number of the data packets. The vertices connected by solid line are the links that share some common nodes, while the ones connected by dotted line represent the links which cannot satisfy the SINR constraints simultaneously. Especially, the links whose senders are relay nodes $ b, c, d, e $ and $ f $ are not utilized to generate the interference graph, since these links have no data packets to transmit in the current time slot for the data gathering tree in Fig. 2.

    Definition 2. Traffic load of links

    In the current time slot being allocated to links for data gathering, the sum of data packets being transmitted at the sender $ v_i $ of the link $ (v_i, v_j) $ is defined as the traffic load of the link $ (v_i, v_j) $.

    It is noticed that the traffic loads of links whose senders are relay nodes are null at the beginning of data gathering, since the data packets from sensor nodes are not received by these relay nodes. However, the relay nodes receive the data packets in the subsequent time slots and then the traffic loads of these links are not null. In the power-based interference graph, each vertex denotes a link whose traffic load is not null. The connected vertices represent the corresponding links which cannot be scheduled simultaneously.

    Definition 3. Compatibility of links

    For the links whose traffic load is not null, if they are all on different subtrees or their corresponding vertices in $ I $ are not connected, then these links are called to be compatible.

    The above definition for the compatibility of links is reasonable since the interference-free orthogonal channels are allocated to the links on different subtrees. It can be seen that the SINR constraints of the compatible links are satisfied too. Next, we will schedule the compatible links in each time slot to gather data.

    Algorithm 2. Maximum links scheduling

    Input: The data gathering tree $ T = \cup_{i = 1}^{K}T_i $, set of data packets $ D $.

    Output: Set of links $ M_t $ scheduled and power assignment vector $ P $ of $ M_t $ at each time slot $ t $.

    1) $ t\leftarrow 1 $

    2) Initialize the traffic load of each link on $ T $

    3) Generate power-based interference graph $ I = \{I_1, $ $ I_2, \cdots, I_K\} $ for the $ K $ subtrees on $ T $

    4) $ F\leftarrow 0 $

    5) while $ F = 0 $ then

    6)   for each subtree $ T_i, load(T_i)>0 $ do

    7)      search the maximum compatible set $ m_i $ of links on $ I_i $

    8)      compute Perron eigenvector $ P_i $ for $ m_i $

    9)   end for

    10)    $ M_t\leftarrow \cup_{i = 1}^{K}m_i $

    11)    $ P\leftarrow \cup_{i = 1}^{K}cP_i $

    12)    if $ D $ is not forwarded to sink then

    13)     $ t\leftarrow t+1 $

    14)      update power-based interference graph $ I $

    15)     $ F\leftarrow 0 $

    16)    else

    17)     $ F\leftarrow 1 $

    18)    end if

    19) end while

    3) Maximum link scheduling algorithm

    In this part, a maximum link scheduling algorithm is presented to achieve a lower latency of data gathering, which minimizes the number of time slots allocated to links by scheduling the compatible links as many as possible in each time slot. The pseudo code of the MLS algorithm is given in Algorithm 2.

    In the beginning of the MLS algorithm, the power-based interference graphs $ \left\{I_1, I_2, \cdots, I_K\right\} $ are generated for the $ K $ subtrees. Then, for each subtree, a maximum set of compatible links on subtree $ T_i $ is searched from the interference graph $ I_i $ in current time slot $ t $. The maximum set is denoted as $ m_i $, thus, a set of the links, i.e., $ M_t = \cup_{i = 1}^{K}m_i $, is scheduled to gather data in the time slot $ t $.

    This procedure is repeated until the traffic load of all links on $ T $ is null in a round of data gathering. Meanwhile, in the current time slot being allocated, the power assignment vector for scheduled links of subtree $ T_i $ is $ cP_i $, where $ c $ and $ P_i $ are a constant value and the Perron eigenvector stated in Lemma 2, respectively.

  • Although the traffic load in the network is distributed over the constructed $ K $ subtrees as balanced as possible, the unbalanced load can still exist in each subtree, which leads to the situation that the nodes with heavier loads die earlier due to higher consumption of energy. Moreover, the links that experience worst communication conditions, such as a poor channel or heavier interference, are more inclined to failure. In fact, both dead nodes and failure links can cause the interruption of the data gathering for the corresponding subtrees. Hence, in each round of data gathering, the mechanism of data gathering must be robust to the dead nodes and failure links to guarantee that the sensing data of sensor nodes are forwarded to the sink node to a larger extent.

    A certain available node should be selected as an assistant node to forward the data by the sender of a faulty link when the malfunction of a node or link occurs, and such a node must be in the communication range of the sender. Especially, the assistant nodes exist in most cases since the deployment of nodes is based on redundancy as stated before. Now, let $ u $ and $ V $ denote the sender of the faulty link and the set of available nodes, respectively. To decrease the waiting delay in the queue of data packets being transmitted, the available node $ v_i\in V $ that has a smaller traffic load in current time slot should be the assistant node.

    Meanwhile, the quality of the new link $ (u, v_i) $ should be considered before the assistant node $ v_i $ is selected to forward the data. The quality is defined as the successful probability of delivery (SPD) for the link. More specifically, a packet is correctly delivered if the SINR at a receiver is not less than the threshold $ \lambda $, thus, for a given transmitting power of the sender $ u $, the SPD of the link $ (u, v_i) $ at a distance $ d $ is given by (17)

    $ \begin{align} pro(u, v_i) = pro(q_{u, v_i}\geq \lambda) = \qquad\qquad\qquad\qquad\\1-Q\Big(\lambda +PL_{d_0}^{ {\rm{d}}B}+10\rho {\rm{log}}\frac{d}{d_0}+B^{ {\rm{d}}Bm}-p_{u}^{ {\rm{d}}Bm}\Big) \end{align} $

    (17)

    where $ Q(z) = \frac{1}{\delta \sqrt{2\pi}}\int_{-\infty}^{z} {\rm{e}}^{-\frac{x^2}{2\delta^2}} {\rm{d}}x $.

    For the propagation model (1), the typical values of the loss exponent $ \rho $ and standard deviation $ \delta $ in an outdoor environment are given in Table 1. To estimate the SPD of a link, the corresponding parameters are set according to our practical experience gained after repeated experiments and are shown in Table 2.

    Table 1.  Typical values for $\rho$ and $\delta_{ {\rm{d}}B}$

    Table 2.  Parameter setting

    Fig. 5 depicts the SPD for a link under different distances based on the above parameters. It is noticed that the decline of the SPD is sharp when the distance is about $ 150 $ m. The numerical results in Fig. 5 will be used in the later simulations.

    Figure 5.  Successful probability of delivery of the link

    Hence, the traffic load of an available node $ v_i $ and the quality of the link $ (u, v_i) $ should be considered when selecting an available node as the assistant node to forward the data. Accordingly, a one-hop weight $ W(u, v_i) $ for $ u $ is defined as

    $ \begin{align*} W(u, v_i) = \frac{load(v_i)}{pro(u, v_i)} \end{align*} $

    where $ load(v_i) $ is the traffic load of $ v_i $, $ v_i $ is an available node within the communication range of $ u $. The $ pro(u, v_i) $ is the SPD for the link $ (u, v_i) $ which is given by (17).

    In our robust mechanism, the sender $ u $ of the failure link chooses the available node with the minimum one-hop weight to complete the delivery of data when the malfunction of the nodes or links occurs.

  • The results of our simulation are presented in this Section, which are conducted based on the network simulator NS-$ 2 $. Some similar algorithms are compared to evaluate and analyze the performance of our proposed algorithms.

  • A strip-type field is employed in the simulations, which consists of a $ 300\, \rm{m}\times 200\, \rm{m} $ sensing area and a $ 1\, 300\, \rm{m} $ linear area for forwarding data, and is shown in Fig. 6. Specifically, the sink node is placed at the end of the linear area that stays away from the sensing area, the sensor nodes are deployed randomly in the sensing area, and the relay nodes are uniformly deployed along the linear area every $ 30\, \rm{m} $.

    Figure 6.  Strip-type field employed in the simulations

    It should be noted that the spacing between two adjacent relay nodes is fixed to $ 30\, \rm{m} $ but the number of sensor nodes is variable for comparisons in our simulations. Meanwhile, we assume that the numbers of packets generated by different sensor nodes are 1, 2, 3, 4 and 5 due to the differences of sensor nodes, and the corresponding proportions of the sensor nodes are $ 10\, \%, 20\, \%, 40\, \%, 20\, \% $ and $ 10\, \% $, respectively.

    The adjustable power range of each sensor node is set from $ -24\, \rm{dBm} $ to $ 2\, \rm{dBm} $. Also, the maximum power of each relay node equipped with a high-power amplifier is set to $ 5\, \rm{dBm} $. We assume that the number of available orthogonal channels at $ 2.4\, \rm{GHz} $ is $ 5 $ and each bandwidth is $ 5\, \rm{MHz} $.

    In addition, the physical data rate and the length of a packet transmitted in a time slot are set to $ 250\, \rm{Kbps} $ and $ 125\, \rm{bytes} $, respectively. Hence, the length of each time slot is $ \frac{125\times 8}{250\times 10^3} = 40\, \rm{ms} $. The maximum distance $ d_m $ of reliability is set to $ 150\, \rm{m} $ that guarantees the delivery probability is above $ 0.7 $ according to Fig. 5 when the relay nodes work at $ 5\, \rm{dBm} $. The common SINR threshold value is $ 0\, \rm{dB} $ to $ 30\, \rm{dB} $ and other parameters are given as Table 2.

    The following performance metrics are considered in this paper.

    1) Load balance of subtrees

    The standard deviation of the traffic loads of all subtrees is used to evaluate the load balance among subtrees.

    2) Latency of data gathering

    The product of total number of allocated time slots and the duration of each time slot (i.e., $ 40\, \rm{ms} $) in a round of data gathering.

    3) Reliability of links

    The mean successful probability of delivery (MSPD) of a link set when the links of the set are scheduled to transmit.

    4) Robustness

    As the dead nodes or failure links can prevent the data gathering from corresponding subtrees and reduce the number of data packets arrived at the sink node, the robustness is weighed by the packet arrival rate at the sink node (PARS) in a round of data gathering. Namely

    $ \begin{align*} PARS = \frac{A}{\sum\limits_{v_i\in S}D(v_i)}\times 100\, \% \end{align*} $

    where $ A $ is the number of packets arrived at the sink node, $ D(v_i) $ corresponds to the amount of packets generated by the sensor node $ v_i $, $ v_i\in S $.

  • In this subsection, some joint algorithms of relevant tree constructing methods and link scheduling methods for data gathering are compared with our MCLL-MLS in terms of the above performance metrics. The joint algorithms are LLHC-MWF, LLHCH-MWF and MST-MLS, where LLHC, LLHCH and MWF are proposed in [24] and the MST is a well-known minimum spanning tree algorithm. LLHC and LLHCH are tree constructing algorithms based on the low-latency high-compatibility, and MWF is the maximum weight first algorithm for scheduling links.

    1) Traffic loads of subtrees

    The traffic loads of subtrees and corresponding standard deviations are assessed for the various node numbers, namely, the number of sensor nodes is changed from 50 to 150 in Fig. 7, where the SINR threshold value is set to $ 10\, \rm{dB} $ and the number of available channels is fixed to $ 5 $. In the simulations, the number of subtrees constructed by our MCLL is 5 according to (12), which relates with the distance of adjacent relay nodes, the maximum distance of reliability and the number of available channels.

    Figure 7.  Traffic loads of subtrees and corresponding standard deviations under various node numbers

    Fig. 7 (a) shows that the traffic loads of the 5 subtrees increase with the number of the sensor nodes. Apparently, the traffic loads of the 5 subtrees change in a small scope when the number of sensor nodes is fixed, and the reason is that the total traffic load in the network is distributed over these subtrees as balanced as possible by the MCLL. The corresponding standard deviations of the traffic loads in Fig. 7 (a) are shown in Fig. 7 (b), which present a slight fluctuation (i.e., from 2.3 to 3.5), thus, the traffic loads of the 5 subtrees are relatively balanced.

    In addition, under the same simulation conditions, the maximum queue lengths of data packets at nodes are compared for the joint algorithms MST-MLS, MCLL-MLS, LLHC-MWF and LLHCH-MWF (see Fig. 8). It can be seen from Fig. 8 that the maximum queue lengths of the four algorithms increase with the node number, that is because the number of data packets generated by the sensor nodes increase and the traffic loads of some nodes become heavier.

    Figure 8.  Maximum queue length at nodes under various node numbers

    Meanwhile, the change of the maximum queue length of our MCLL-MLS is the slowest in the four joint algorithms. When the number of sensor nodes is 150, the maximum queue length of our MCLL-MLS is less by $ 70\% $, $ 44\% $ and $ 33\% $ than those of MST-MLS, LLHCH-MWF and LLHC-MWF, respectively. That is because the MCLL achieves a relatively balanced load for each constructed subtree and some common nodes shared by several paths or subtrees are avoided. As a result, the excessive congestion of data packets at nodes is effectively relieved by our MCLL-MLS algorithm.

    2) The latency of data gathering

    Now, we compare the data gathering latencies of the four joint algorithms under various numbers of sensor nodes and different SINR threshold value, respectively. Also, the data gathering latencies under different number of available channels are evaluated for our MCLL-MLS.

    Similarly, the SINR threshold value and the number of available channels are set to $ 10\, \rm{dB} $ and 5, respectively. The data gathering latencies of the four joint algorithms are shown in Fig. 9 when the number of sensor nodes is increased from 50 to 150. As seen from Fig. 9, all the latencies increase with the number of sensor nodes. However, the latency of data gathering conducted by our MCLL-MLS is lower than others all the time. Especially, when the number of sensor nodes increase to 150, the data gathering latency is less by $ 41\, \% $, $ 33\, \% $ and $ 26\, \% $ than the latency of MST-MLS, LLHCH-MWF and LLHC-MWF, respectively. The reason is that the multi-channel-based mechanism of our MCLL-MLS increases the number of schedulable links in each time slot. Furthermore, the balanced traffic load and the less congestion obtained by the MCLL-MLS also lead to the lower data gathering latency compared with the MST-MLS, LLHCH-MWF and LLHC-MWF.

    Figure 9.  Data gathering latency under various node numbers

    When the numbers of sensor nodes and available channels are fixed to 90 and 5, respectively, the data gathering latencies of the four joint algorithms are shown in Fig. 10. With the SINR threshold value increasing from $ 0\, \rm{dB} $ to $ 25\, \rm{dB} $, the links are more sensitive to the interferences, and fewer links can be scheduled to satisfy the SINR constraints in some time slots, thus, all the latencies show a rising trend in Fig. 10. However, for similar reasons, the latency of data gathering conducted by the MCLL-MLS is still lowest in the four algorithms.

    Figure 10.  Data gathering latency under different SINR thresholds

    In the situation that the number of sensor nodes is fixed to 90 and the SINR threshold value is set to $ 10\, \rm{dB} $, Fig. 11 shows the data gathering latency obtained by our MCLL-MLS when the number of available channels are changed from 1 to 5. Clearly, under the condition that the topology of nodes is fixed, the number of subtrees constructed by our MCLL equals to the number of the available channels in the network (according to (12)).

    Figure 11.  Data gathering latency of MCLL-MLS under different number of available channels

    In Fig. 11, with the increase in the number of available channels, the latency of data gathering conducted by our MCLL-MLS becomes more and more small. Especially, when the number of available channels is 5, the data gathering latency is less by $ 67\, \% $ than the latency in one available channel. The reason is that more subtrees can be constructed, and more links can be scheduled in each time slot with the increase in the number of available channels.

    3) Reliability of links and robustness

    In this part, the reliability of links for data gathering conducted by our MCLL-MLS is evaluated based on the mean successful probability of delivery. To evaluate the robustness performance for the proposed robust mechanism (RM), the joint algorithm MCLL-MLS-RM is compared with the MCLL-MLS and LLHC-MWF based on the packet arrival rate at the sink node (PARS).

    Fig. 12 shows the MSPD for the links on each subtree resulting from various number of sensor nodes, where the SINR threshold value and the number of available channels are fixed to $ 10\, \rm{dB} $ and $ 5 $, respectively. The MSPD of the 5 subtrees present a slight decline with the number of sensor nodes. Due to the SINR constraints on the links, the result is satisfactory as a whole and all the MSPD are above 0.8. However, $ 100\, \% $ MSPD of the links on each subtree is failed to achieve, since the SINR is estimated based on the statistical properties of background noises and interferences in the simulations.

    Figure 12.  Reliability of links

    Fig. 13 shows the PARS in the data gathering conducted by the MCLL-MLS-RM, MCLL-MLS and LLHC-MWF, respectively. With the increase in the rounds of data gathering, more-frequent malfunctions of nodes and links occur, and all the PARS present the sustained downward trend. However, the PARS of the MCLL-MLS-RM is largest among the comparable algorithms and the advantage is more obvious when the rounds of data gathering are above 450. Further, the PARS of MCLL-MLS-RM is improved by $ 12\, \% $ and $ 30\, \% $ compared with the MCLL-MLS and LLHC-MWF at the $ 1\, 000 $th round of data gathering, respectively. The reason is that the robustness to the malfunctions of nodes or links is achieved when our MCLL-MLS is performed with the proposed RM.

    Figure 13.  Robustness of data gathering

    In addition, due to the sudden death of vast nodes, a sharp decline of PARS occurs for the three algorithms when the process of data gathering goes into certain stages. The sharp decline of the MCLL-MLS-RM happens at about the $ 550 $th round of data gathering and later than LLHC-MWF that happens at about the $ 450 $th round of data gathering. The reason is that the vertex-disjoint subtrees constructed by our MCLL prevent some nodes from the heavier loads and the subtrees share the traffic load of the network as balanced as possible, thus, the earlier death of nodes is relieved. Moreover, since the robust mechanism is introduced, the PARS of the MCLL-MLS-RM presents a relatively steady decline compared with the MCLL-MLS and LLHC-MWF in the whole process.

  • For the timeliness and reliability of data gathering in HWSNs, the problem of multi-channel-based data gathering with minimum latency has been investigated and formulated as an optimization problem, which has been proved to be NP-hard. Then the MCLL and MLS algorithms have been presented to solve the MCDGML-OP for seeking a suboptimal solution. Furthermore, to deal with the interruption problem of data gathering caused by dead nodes or failure links, a robust mechanism has been proposed based on the defined one-hop weight.

    The simulation results have shown that the excessive congestion of data traffic in HWSNs is avoided by the constructed vertex-disjoint subtrees of our MCLL algorithm. Meanwhile, the traffic loads of the subtrees are relatively balanced and the lower latency of data gathering is achieved. Furthermore, the mean successful probability of delivery of links is satisfactory when the links are scheduled by our MLS. In addition, the simulation results have demonstrated that the proposed robust mechanism for the dead nodes or failure links can achieve a higher packet arrival rate at the sink node.

  • This work was supported by the Natural Science Foundation of China (Nos. U1334210 and 61374059).

Reference (27)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return