Limits...
A Novel Two-Tier Cooperative Caching Mechanism for the Optimization of Multi-Attribute Periodic Queries in Wireless Sensor Networks.

Zhou Z, Zhao D, Shu L, Tsang KF - Sensors (Basel) (2015)

Bottom Line: Usually, certain sensory data may not vary significantly within a certain time duration for certain applications.Leveraging these cooperatively cached sensory data, queries are answered through composing these two-tier cached data.Experimental evaluation shows that this approach can reduce the network communication cost significantly and increase the network capability.

View Article: PubMed Central - PubMed

Affiliation: School of Information Engineering, China University of Geosciences (Beijing), Beijing 100083, China. zhangbing.zhou@gmail.com.

ABSTRACT
Wireless sensor networks, serving as an important interface between physical environments and computational systems, have been used extensively for supporting domain applications, where multiple-attribute sensory data are queried from the network continuously and periodically. Usually, certain sensory data may not vary significantly within a certain time duration for certain applications. In this setting, sensory data gathered at a certain time slot can be used for answering concurrent queries and may be reused for answering the forthcoming queries when the variation of these data is within a certain threshold. To address this challenge, a popularity-based cooperative caching mechanism is proposed in this article, where the popularity of sensory data is calculated according to the queries issued in recent time slots. This popularity reflects the possibility that sensory data are interested in the forthcoming queries. Generally, sensory data with the highest popularity are cached at the sink node, while sensory data that may not be interested in the forthcoming queries are cached in the head nodes of divided grid cells. Leveraging these cooperatively cached sensory data, queries are answered through composing these two-tier cached data. Experimental evaluation shows that this approach can reduce the network communication cost significantly and increase the network capability.

No MeSH data available.


An example of the index tree constructed through Algorithm 1, where 1000 sensor nodes are deployed in the network region, and the skewness degree is set to 60%. The leaf nodes in the index tree correspond to the grid cells (e.g., gc24), and non-leaf nodes (e.g., R5) correspond to sub-regions containing multiple grid cells (e.g., gc22 and gc23).
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4541820&req=5

f3-sensors-15-15033: An example of the index tree constructed through Algorithm 1, where 1000 sensor nodes are deployed in the network region, and the skewness degree is set to 60%. The leaf nodes in the index tree correspond to the grid cells (e.g., gc24), and non-leaf nodes (e.g., R5) correspond to sub-regions containing multiple grid cells (e.g., gc22 and gc23).

Mentions: As previously mentioned, the index tree to be constructed in this article should be a relatively balanced tree for a skewed distribution, rather than an unbalanced tree, as developed in our previous work [33]. The difference lies mainly in the tree node merging strategy As presented in Algorithm 1, after dividing the network region into square grid cells whose side-length is , we firstly get the set of leaf nodes (denoted TNset) with inverted files as presented by Algorithm 1 (Lines 1–13) in our previous work [33] (Line 1). Note that these leaf nodes corresponds to grid cells, rather than sensor nodes in the network. The weight (denoted wgt(nd1, nd2)) between neighboring nodes (denoted nd1 and nd2), which reflects the energy consumption when routing sensory data from one node to another, is calculated using the function calNgbNdWgt(nd1, nd2). As presented by Algorithm 2 in our previous work [33] (Line 4), this function returns the sum of weights among all pairs of neighboring grid cells in the corresponding neighboring sub-regions. If there are neighboring nodes (i.e., nd1 and nd2) in TNset that can be merged, in other words, wgt(nd1, nd2) is the biggest (Line 5), nd1 and nd2 are merged as a newly-generated node tn (Lines 6–7), and the inverted files (denoted tn.IvtF, for instance) are processed accordingly (Line 8). Note that tn corresponds to a sub-region in the network, which is the merger of sub-regions for nd1 and nd2. After this merging procedure, nd1 and nd2 are removed from TNset (Line 9), while tn is inserted into nTNset as a candidate for the next merging procedure (Line 10). This procedure iterates until all neighboring nodes in TNset have been examined and processed. Thereafter, TNset and nTNset are updated accordingly (Lines 12–13). The symbol ∅ in Line 13 means an empty set. This tree construction procedure terminates one there is only one node left in TNset (Line 3), which corresponds to the root node of the index tree (Line 15). An example of the index tree constructed through this algorithm is shown in Figure 3, which is a binary tree and more balanced than the tree as shown in Figure 5 in our previous work [33]. Specifically, 25 grid cells, as shown in Figure 2, correspond to the leaf nodes, and sub-regions composed of multiple grid cells correspond to non-leaf nodes, in the index tree. This index tree construction is to facilitate the popularity-based cooperative caching mechanism to be presented in the following sections. The time complexity of Algorithm 1 is O(n × log2n), where n is the number of leaf nodes in, while log2n is the height of the index tree.


A Novel Two-Tier Cooperative Caching Mechanism for the Optimization of Multi-Attribute Periodic Queries in Wireless Sensor Networks.

Zhou Z, Zhao D, Shu L, Tsang KF - Sensors (Basel) (2015)

An example of the index tree constructed through Algorithm 1, where 1000 sensor nodes are deployed in the network region, and the skewness degree is set to 60%. The leaf nodes in the index tree correspond to the grid cells (e.g., gc24), and non-leaf nodes (e.g., R5) correspond to sub-regions containing multiple grid cells (e.g., gc22 and gc23).
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4541820&req=5

f3-sensors-15-15033: An example of the index tree constructed through Algorithm 1, where 1000 sensor nodes are deployed in the network region, and the skewness degree is set to 60%. The leaf nodes in the index tree correspond to the grid cells (e.g., gc24), and non-leaf nodes (e.g., R5) correspond to sub-regions containing multiple grid cells (e.g., gc22 and gc23).
Mentions: As previously mentioned, the index tree to be constructed in this article should be a relatively balanced tree for a skewed distribution, rather than an unbalanced tree, as developed in our previous work [33]. The difference lies mainly in the tree node merging strategy As presented in Algorithm 1, after dividing the network region into square grid cells whose side-length is , we firstly get the set of leaf nodes (denoted TNset) with inverted files as presented by Algorithm 1 (Lines 1–13) in our previous work [33] (Line 1). Note that these leaf nodes corresponds to grid cells, rather than sensor nodes in the network. The weight (denoted wgt(nd1, nd2)) between neighboring nodes (denoted nd1 and nd2), which reflects the energy consumption when routing sensory data from one node to another, is calculated using the function calNgbNdWgt(nd1, nd2). As presented by Algorithm 2 in our previous work [33] (Line 4), this function returns the sum of weights among all pairs of neighboring grid cells in the corresponding neighboring sub-regions. If there are neighboring nodes (i.e., nd1 and nd2) in TNset that can be merged, in other words, wgt(nd1, nd2) is the biggest (Line 5), nd1 and nd2 are merged as a newly-generated node tn (Lines 6–7), and the inverted files (denoted tn.IvtF, for instance) are processed accordingly (Line 8). Note that tn corresponds to a sub-region in the network, which is the merger of sub-regions for nd1 and nd2. After this merging procedure, nd1 and nd2 are removed from TNset (Line 9), while tn is inserted into nTNset as a candidate for the next merging procedure (Line 10). This procedure iterates until all neighboring nodes in TNset have been examined and processed. Thereafter, TNset and nTNset are updated accordingly (Lines 12–13). The symbol ∅ in Line 13 means an empty set. This tree construction procedure terminates one there is only one node left in TNset (Line 3), which corresponds to the root node of the index tree (Line 15). An example of the index tree constructed through this algorithm is shown in Figure 3, which is a binary tree and more balanced than the tree as shown in Figure 5 in our previous work [33]. Specifically, 25 grid cells, as shown in Figure 2, correspond to the leaf nodes, and sub-regions composed of multiple grid cells correspond to non-leaf nodes, in the index tree. This index tree construction is to facilitate the popularity-based cooperative caching mechanism to be presented in the following sections. The time complexity of Algorithm 1 is O(n × log2n), where n is the number of leaf nodes in, while log2n is the height of the index tree.

Bottom Line: Usually, certain sensory data may not vary significantly within a certain time duration for certain applications.Leveraging these cooperatively cached sensory data, queries are answered through composing these two-tier cached data.Experimental evaluation shows that this approach can reduce the network communication cost significantly and increase the network capability.

View Article: PubMed Central - PubMed

Affiliation: School of Information Engineering, China University of Geosciences (Beijing), Beijing 100083, China. zhangbing.zhou@gmail.com.

ABSTRACT
Wireless sensor networks, serving as an important interface between physical environments and computational systems, have been used extensively for supporting domain applications, where multiple-attribute sensory data are queried from the network continuously and periodically. Usually, certain sensory data may not vary significantly within a certain time duration for certain applications. In this setting, sensory data gathered at a certain time slot can be used for answering concurrent queries and may be reused for answering the forthcoming queries when the variation of these data is within a certain threshold. To address this challenge, a popularity-based cooperative caching mechanism is proposed in this article, where the popularity of sensory data is calculated according to the queries issued in recent time slots. This popularity reflects the possibility that sensory data are interested in the forthcoming queries. Generally, sensory data with the highest popularity are cached at the sink node, while sensory data that may not be interested in the forthcoming queries are cached in the head nodes of divided grid cells. Leveraging these cooperatively cached sensory data, queries are answered through composing these two-tier cached data. Experimental evaluation shows that this approach can reduce the network communication cost significantly and increase the network capability.

No MeSH data available.