# Two FCA-Based Methods for Reducing Energy Consumption of Sensor Nodes in Wireless Sensor Networks

Authors: Yuxia Lei; Meiyan Qu; Chen Lei; Zhiqiang Kong; Jingying Tian; Shi Wang
Journal: Scientific Programming
 (2022)

---

## Abstract

In the design of wireless sensor networks (WSNs), it is important to reduce energy consumption and extend the service life of the sensors. Selecting one of the minimum sensor combinations (MSCs) that can monitor all areas, while the other MSCs are asleep, can effectively extend the lifetime of WSNs. This paper proposes two algorithms based on Formal Concept Analysis (FCA) for extracting some MSCs, to minimize the energy consumption and meet the coverage requirement. These two methods firstly extract the concept lattice from a monitor-areas context, and then it is simple to extract sensor nodes monitoring the overlapping area from the concept lattice. The algorithms consist of three steps as follows: the first step is to transform sensors and monitoring areas into a context, the second is to extract the concept lattice and implications among areas, and the third is to extract some different MSCs that can monitor all areas. Thus, some strategies are designed to awaken different MSCs to achieve the purpose of reducing energy consumption. Experimental results show that these methods have played a positive effect on extracting different MSCs and extending the lifetime of sensor networks.


---

## Body

## 1. Introduction

With the popularity and rapid development of the fields of Internet of Things, there are many meaningful research directions such as point of interest recommendation [1], reducing the energy consumption of WSNs [2, 3], dynamic task offloading [4], and admission control for edge computing [5]. In recent years, WSNs have been more and more widely used in economic life, which are usually made up of a large number of sensor nodes, and are scalable [6, 7]. But because of their limited power and computing power, they are often placed in areas that are hard for people to reach [2]. Energy is a valuable resource in WSNs, and the energy consumption of sensor nodes is the main energy consumption. Therefore, sensor power supply capability is the main obstacle that limits the application of sensor network technology [8]. However, the power of sensor nodes is limited and difficult to replace [9–11], how to reduce the energy consumption of sensor nodes becomes the core problem of WSNs [12–14].FCA is proposed by Wille R. in 1982, which focuses on the lattice structure induced by a binary relation between a pair of sets (respectively called objects and attributes), known as the Galois lattice or the concept lattice of the relation [15–18]. A node of concept lattice is a pair of objects and attributes, called a formal concept. It consists of two parts: the extent and the intent. The extent is the set of objects which have all attributes in the intent. Similarly, the intent is the set of attributes common to the objects in the extent. A process of generating the concept lattice from a binary relation is a process of clustering, and the line diagram corresponding to a concept lattice vividly shows the generalization and specialization relationship among formal concepts. FCA can be combined with techniques in many fields like big data [19], Internet of Things [20–22], data mining [23], and social computing. If it is combined with deep learning methods to apply to the field of big data and edge computing [24–26], the accuracy of data mining and resource allocation will be optimized. If it is applied to social networks [27, 28], the relationship between nodes can be strengthened to a certain extent and the structure of social networks can be improved. To reduce the energy consumption of WSNs and achieve optimal deployment of nodes [29], this paper uses FCA to extract the minimum sensor combinations to monitor the entire area.According to the research of existing methods, this paper proposes two algorithms based on FCA for extracting some MSCs. One is called implications-based algorithm for extracting MSCs. This method can find the minimum sensor combination, but the number of rules affects the efficiency of this algorithm. To reduce the rule set, we propose the second method for extracting the stem base of region implications from the concept lattice. The implementation process of these two algorithms can be roughly divided into three parts. Firstly, transform sensors and monitoring areas into a context. Secondly, extract the concept lattice from the context and implications among areas. Lastly, extract sensor nodes that monitor the overlapping area from the concept lattice. Thus, some strategies are designed to awaken different MSCs to reduce energy consumption and extend the lifetime of the network. Experimental results show that different MSCs can be extracted. These two methods have achieved good results in practical applications.At present, the mechanisms for reducing energy consumption are broadly classified into the following three categories:(1)
Sleeping mechanism: This mechanism mainly solves the problem of energy waste caused by idle monitoring [30]. When there is no event of interest occurring around the node, the computing and communication module will be in the idle module, turning them off or turning them to a lower power, that is, the dormant state [31]. This mechanism is important for extending the lifetime of sensor nodes. For example, dynamic voltage scaling (DVS) and dynamic power management (DPM) manage system power in a power-aware manner to reduce energy consumption and extend the lifetime of the nodes.(2)
Data compression and data fusion mechanism: In WSNs with high coverage, there is redundancy in the information passed by neighbor nodes. And each node consumes too much energy to transmit data alone, shortening the lifetime of the network accordingly [32]. Data compression and fusion can effectively reduce the amount of raw data and the number of transmissions of sensor nodes. The data compression method reduces the energy consumption of nodes by compressing the transmitted data in advance [33]. Data fusion technology can merge the data information collected by multiple sensors and eliminate redundant and useless information [34, 35].(3)
Self-contained energy replenishment device: The sensor node is equipped with the energy harvesting and conversion device to collect energy like solar energy [36–38]. However, renewable energy fluctuates with the environment and the energy density is low. Therefore, this energy supplementation method has great limitations in practical applications. To solve these problems, the relevant research proposes to add the rechargeable sensor node of the wireless charging device to form a wireless rechargeable sensor network [39, 40]. And wireless power transmission (WPT) is used to replenish energy for rechargeable sensor nodes [41, 42].However, there are still many disadvantages in the existing mechanisms. The sleeping mechanism requires an effective scheduling algorithm, and unreasonable arrangement of the dormant and working state of nodes will lead to idle waste. Besides, the transition between the dormant and working state of nodes also consumes some energy. Thus, frequent state transitions can also lead to excessive energy consumption. The data compression process requires more powerful processing power to handle compression algorithms [43]. Although data fusion can substantially reduce energy consumption, it usually needs specific nodes to collect data before proceeding to the next stage of transmission, which increases the network delay. Moreover, the process of data compression and fusion may cause the loss of detailed information and reduce the quality of data transmission. For wireless rechargeable networks, the current wireless charging technologies are mostly used in a short range. The farther the transmission distance, the lower the energy transmission efficiency. And the charging speed and efficiency of wireless charging still need to be further improved.The main contributions of our work in this paper are summarized as follows: we propose two algorithms based on FCA for extracting some MSCs and waking up a group of sensor nodes by periodic loop mechanism and prediction mechanism to minimize the energy consumption on condition that the sensors monitor all areas. The specific idea is to extract MSCs by proposed algorithms and sort the combinations, and then put a group of sensor nodes in quasi-wake state by using the periodic loop mechanism. Finally, wake up the sensor nodes that are predicted to have a task schedule. The motivation diagram of this study is shown in Figure1.Figure 1
The framework of this study.The remainder of this paper is organized as follows. Section2 presents the related work, followed by some basic notations in formal concept analysis in Section 3. Section 4 provides two FCA-based algorithms called implications-based algorithm and the stem base-based algorithm for extracting different MSCs. Section 5 provides some experimental results to verify the validity and feasibility of the algorithms. Finally, we conclude and present the future work in Section 6.


## 2. Related Work

In recent years, with the rapid transformation and development of wireless communications in various fields [44, 45], a large number of researchers have been committed to studying various technologies that reduce the energy consumption of WSNs to extend the service life. In [46], the authors studied a data compression algorithm that determines the compression level of each sensor node to reduce total energy consumption based on the average energy level of neighboring sensor nodes. This technique reduces the energy consumption to transmit and receive packets and ultimately extends the entire network life. The literature [47] proposed a mean filtering algorithm based on node data images, which divides nodes into active and inactive nodes. This method clusters nodes and analyzes data obtained from sensor networks to eliminate data redundancy of sleep nodes. In [3], the authors introduced an area segmentation model based on optimal energy-saving constraints. According to the energy attribute of the sensor nodes, it optimally segments the coverage area of the wireless sensor network to improve its coverage, reduce the energy cost of a single node and realize the optimal networking of WSNs. To fully balance the energy, the literature [48] proposed to use power supply lines to connect nodes. Based on energy balance, a data transmission method with optimal hop count is proposed, which fully reduces the power consumption of data transmission. To determine the optimal monitoring sensor nodes and the information flow paths to the destination and receivers to reduce the energy consumption between the node and the receiver, Bat algorithm (BA) is proposed in literature [49]. In [2], the authors developed two different system models that use optimal node placement strategies compared with traditional equidistant placement strategies to minimize energy consumption in linear wireless sensor networks (LWSNs). Based on improved sparrow search algorithm (ISSA) optimized self-organizing maps (SOM), a cluster head selection strategy used in heterogeneous wireless sensor network (HWSN) is proposed in the literature [7]. This strategy comprehensively considers the residual energy, distance, and the times the node becomes a cluster head. It uses the adaptive learning of improved competitive neural networks to optimize the cluster head node and extend the life cycle of the network. The literature [50] proposed a power management method to reduce energy consumption in an idle state. Moreover, they studied a fine-grained power mode (FGPM) with five states. This mode can adjust the power consumption according to the communication state of the sensor nodes, reducing the power consumption of each node.The strategies to wake up nodes will also affect the energy consumption of the sensor nodes, and an effective wake-up strategy can reasonably switch the sleep and working state of the sensors and reduce the energy loss of each sensor. In [51], a low duty cycle energy-efficient MAC protocol is proposed, which can adaptively update based on the prediction wake-up time of nodes. In this method, each node has a neighbor node information table including the target node address. By this table, the sending node will predict the wake-up time of receiving node. In [52], the authors proposed a self-adaptive sleep/wake-up scheduling approach based on the reinforcement learning technique. Each node can decide its working state independently in each time slot. The literature [53] found a multitarget sensing wake-up control method based on swarm intelligence, which studies the optimization of the wake-up strategy of dynamic targets to reduce the number of wake-up nodes when multiple targets are crossing. This method avoids waking up excessive nodes and extends the service life of WSNs.


## 3. Basic Notations in Formal Concept Analysis

In FCA [15], a (formal) context is defined as a triple K=G,M,I, where G and M are sets and I⊆G×M is a binary relation. The elements of G and M are respectively called objects and attributes. For any r∈G and m∈M, r,m∈IorrIm implies that the object r possesses the attribute m. For a set X′IG of objects, X′ is the set of attributes common to the objects in X. It is defined as fd1.(1)X′=m∈M:∀r∈XrIm.Similarly, for a setY′IM, Y′ is the set of objects having all attributes in Y. It is defined as fd2.(2)Y′=r∈G:∀m∈YrIm.Given a contextK=G,M,I, for any XG and Y M, the pair X,Y is called a (formal) concept if X′=Y and Y′=X, where X and Y are respectively called the extent and the intent of the concept. There are two kinds of special concepts: object concept and property concept. Given an object r∈G, the pair r′′,r′ is a concept, called the object concept of r. The object concept is the smallest concept having r in its extent. Correspondingly, given an attribute a∈M, the pair a′,a′′ is also a concept, called the attribute concept of a, which is the greatest concept having a in its intent.The set of all concepts in the contextK is represented as LK. If X1,Y1, X2,Y2∈LK are concepts, then X1,Y1 is called a subconcept of X2,Y2, provided that X1⊆X2 (which is equivalent to Y2⊆Y1). The comparison expression is represented as X1,Y1≤X2,Y2. In this case, X2,Y2 is a superconcept of X1,Y1. Therefore, we can get fd3.(3)X1,Y1≤X2,Y2⇔X1⊆X2⇔Y2⊆Y1.The relation ‘≤’ is an order on LK, which is called the hierarchical order of the concepts. The hierarchical order produces a lattice structure in LK called the concept lattice of the context K=G,M,I, which is also represented as LK. LK is also a complete lattice in which infimum and supremum are given by: if T is an index set and for every t∈T, At,Bt is a concept, then the infimum of the set At,Bt:t∈T is defined as ∧t∈TAt,Bt, which represents the largest common subconcept of the concept At,Btt∈T. Accordingly, the supremum of the set At,Bt:t∈T represents the smallest common subconcept.The labelling can be simplified considerably by putting down each object and attribute only once, namely at the circle for the respective object or attribute concept. Thus, the concept of lattices can be described by the line diagrams with reduced labelling. In a line diagram, the name of an objectg is always attached to the circle that represents the smallest concept with g in its extent. And the name of an attribute a is always attached to the circle that represents the largest concept with a in its intent. This allows us to read the map I from the diagram: an object g has an attribute a if and only if there is an ascending path from the circle labeled by g to the circle labeled by a. The extent of a concept consists of all tuples whose labels are below in the diagram. The intent consists of all properties attached to the concepts above in the hierarchy. For example, in Figure 2 in section 5, the intent of the concept labeled by the attribute h is MSC, and its extent is sensor−4. Similarly, the extent of the concept labeled by the sensor−1 is sensor−1,sensor−2,sensor−3, and its intent is a,f.Figure 2
(a) Concept lattice for Table1. (b) Line diagram with reduced objects labelling. (c) Line diagram with reduced attributes labelling. (d) Line diagram with reduced labelling.
(a)(b)(c)(d)


## 4. FCA-Based Algorithms for Extracting Different MSCs

In this section, we propose two FCA-based algorithms for extracting MSCs. Moreover, we will explain the specific algorithm flow of these two algorithms and strategies to reduce the energy consumption of sensors in detail. The algorithms consist of three steps as follows: the first step is to transform sensors and monitoring areas into a context, the second is to extract the concept lattice and implications among areas, and the third is to extract the minimum sensor combinations that can monitor all areas. The core idea of these two algorithms is that when the sensor set we have found covers all areas, end loop and output the minimum sensor set.


### 4.1. Transforming Sensors and Their Coverage Areas into a Context

In a wireless sensor network with many nodes, each sensor node can be considered as an object, and each area monitored by sensors can be considered as an attribute of the corresponding object. Assuming that some sensors are scattered in one area, we divide the area into some smaller areas. According to the positioning and operating radius of these sensors, the areas that can be monitored by each sensor can be obtained. Thus, we can transform sensors and monitoring areas into a table. The row represents the sensor number, the column represents the divided monitoring area, and the symbol “+” at the intersection indicates that the sensors can monitor the corresponding areas. For example, there are eight sensors, and the area is divided into eight smaller areas. Each sensor and corresponding monitoring area are as shown in Table1, which is a context.Table 1
Monitoring area of each sensor.
abcdefghSensor-1++Sensor-2+++Sensor-3++++Sensor-4++++Sensor-5+++Sensor-6++++Sensor-7+++Sensor-8+++By constructing a concept lattice from the context, it is simple to see which sensor nodes are monitoring the overlapping area. Each sensor can perceive and record the surrounding sensors. Communication between sensors is achieved by finding all the sensor nodes that can be reached through the path on the concept lattice. Then we can make some strategies to awaken the corresponding sensors to achieve the purpose of reducing energy consumption and extending network life.


### 4.2. Implications-Based Algorithm for Extracting MSCs

The basic idea of this algorithm is to extract the region implications among regions from the concept lattice, and then extract different minimum sensor sets according to the rules. To describe this algorithm, we provide several definitions such as implication [15–18].Definition 1.
Given a contextK=G,M,I, for any A,B⊆M, if every object with attributes in A also has the attributes in B, then A⟶B is called an implication of K. A and B are respectively called antecedent and consequence of the implication.Definition 2.
Given a conceptC, if A⊆IntentC, it matches an implication A⟶B.Definition 3.
Given a conceptC, if C is both an attribute concept and an object concept, then it is called 1−concept.Definition 4.
Given a conceptC, if C is only an attribute concept, then it is called 2−concept.
Then we describe the algorithm flow of implications-based Algorithm 1 for extracting MSCs as below.
Algorithm 1: Implications-based algorithm for extracting MSCs.
Input: a contextK=G,M,I, where G and M is a set of sensors and domains respectively.Output: the minimum sensor combinations that monitor all areas inM.(1)
Generate the concept lattice with reduced labelling ofK and implications in K(2)
LetKC be the set of 1/2−concept of K, KI be the set of implications in K, MSC=., CE=.(3)
IfM≠.(4)
Then For the first conceptC in KC(5)
If it matches the implicationA⟶B(6)
thenM←M−A​∪​B(7)
KR←KR−A⟶B(8)
KC←KC−1or2−concept generated froma|a∈A​∪​B(9)
IfC is a 1−concept(10)
thenMSC←MSC​∪​x // x is a sensor in the reduced extent of C(11)
else for a sensorx in ExtentC(12)
ifx∈CE(13)
thenMSC←MSC∪x(14)
CE←CE​∪​ExtentC(15)
Return 3(16)
Output MSC


### 4.3. The Stem Base-Based Algorithm for Extracting MSCs

The basic idea of this algorithm is to extract thestem base of region implications from concept lattice, and then extract different minimum sensor sets according to the rules. To describe this algorithm, we provide several definitions such as the stem base of the attribute implications [15–18].Definition 5.
If each subset ofM respects C also respects A⟶B, then the implication A⟶B follows from a set C of implications between attributes.Definition 6.
If every implication follows fromC, then a set of implications of a context is called complete.Definition 7.
If none of the implications follows from the others, then a set of implications of a context is called nonredundant.Definition 8.
P⊆M is called the pseudointent of G,M,I if and only if P≠P'′ and Q'′≠P holds for every pseudointent Q⊂P.Theorem 1.
The set of implicationsC=P⟶P″|Pis a pseudo−intent is nonredundant and complete, which is called the stem base of the attribute implications.Then we define the stem base-based Algorithm 2 as follows:Algorithm 2: The stem base-based algorithm for extracting MSCs.
Input: a contextK=G,M,I, where G and M is a set of sensors and domains, respectively.Output: the minimum sensor combinations that monitor all areas inM.(1)
Generate the concept lattice with reduced labelling ofK and the stem base of implications(2)
LetKC be the set of 1/2−concept MScs. Standalone K, KI be the stem base in K, MSC=, CE=(3)
IfM≠(4)
Then if there is an implicationA⟶B satisfying M⊆A∪​B(5)
thenMSC←MSC∪x // x is a sensor in the support set of A⟶B(6)
M=(7)
else for the first conceptC in KC(8)
if it matches the implicationA⟶B(9)
thenM←M−A​∪​B(10)
KR←KR−A⟶B(11)
KC←KC−1or2−concept generated froma|a∈A​∪​B(12)
IfC is a 1 −concept(13)
thenMSC←MSC​∪​x // x is a sensor in reduced extent of C(14)
else for a sensorx in ExtentC(15)
ifx∉CE(16)
thenMSC←MSC​∪​x(17)
CE←CE​∪​ExtentC(18)
Return 3(19)
Output MSC


### 4.4. Strategies for Reducing Sensor Energy Consumption

There are several ways to reduce the energy consumption of sensor nodes [54, 55], such as periodic awakening. One way is to make one node run out of its energy and then make the other overlapping nodes wake up. Another way is to calculate the size of the overlapping area of the nodes and decide whether they’re awake or not.In wireless sensor networks, there are the following ways to wake up the nodes:(1)
Full wake-up mode: In this mode, all nodes in the wireless sensor network wake up at the same time to detect and track targets in the network. Although this mode can obtain high tracking accuracy, it is at the cost of huge network energy consumption.(2)
Random wake-up mode: In this mode, the nodes in the wireless sensor network are randomly awakened by a given wake-up probabilityp.(3)
Select the wake-up mode by the prediction mechanism: In this mode, the nodes that have a greater return on tracking accuracy can be selectively awakened according to the needs of tracking tasks. Then predict the state of the target at the next moment through the information of this beat and wake up the nodes.(4)
Task cycle wake-up mode: In this mode, the nodes in the wireless sensor network are in the awake state periodically. Nodes in this mode can coexist with nodes in other working modes and assist these nodes to work.In this study, we choose the period loop mechanism and prediction mechanism to wake up nodes. After the processing of the proposed algorithms, we can obtain different MSCs. Then sort the sensor combinations and use the period loop mechanism to put each group of nodes into quasi-wake state in order. The quasi-wake state is a state between wake-up and sleep, which means the node is ready to be awakened. The principle of the period loop mechanism is that only one group of sensor nodes is put into the quasi-wake state in each cycle until each group of nodes has been processed once, and then start again with the first set of nodes and repeat this process. Lastly, wake up the sensor nodes that may have a task arrangement by using a prediction mechanism. In this mechanism, the sending node calculates and predicts the wake-up time of receiving node by retaining the address of the target node in the neighbor node information table [51]. This step ensures the receiving nodes wake up timely and avoid the problems like collision caused by waking up all nodes simultaneously.


## 4.1. Transforming Sensors and Their Coverage Areas into a Context

In a wireless sensor network with many nodes, each sensor node can be considered as an object, and each area monitored by sensors can be considered as an attribute of the corresponding object. Assuming that some sensors are scattered in one area, we divide the area into some smaller areas. According to the positioning and operating radius of these sensors, the areas that can be monitored by each sensor can be obtained. Thus, we can transform sensors and monitoring areas into a table. The row represents the sensor number, the column represents the divided monitoring area, and the symbol “+” at the intersection indicates that the sensors can monitor the corresponding areas. For example, there are eight sensors, and the area is divided into eight smaller areas. Each sensor and corresponding monitoring area are as shown in Table1, which is a context.Table 1
Monitoring area of each sensor.
abcdefghSensor-1++Sensor-2+++Sensor-3++++Sensor-4++++Sensor-5+++Sensor-6++++Sensor-7+++Sensor-8+++By constructing a concept lattice from the context, it is simple to see which sensor nodes are monitoring the overlapping area. Each sensor can perceive and record the surrounding sensors. Communication between sensors is achieved by finding all the sensor nodes that can be reached through the path on the concept lattice. Then we can make some strategies to awaken the corresponding sensors to achieve the purpose of reducing energy consumption and extending network life.


## 4.2. Implications-Based Algorithm for Extracting MSCs

The basic idea of this algorithm is to extract the region implications among regions from the concept lattice, and then extract different minimum sensor sets according to the rules. To describe this algorithm, we provide several definitions such as implication [15–18].Definition 1.
Given a contextK=G,M,I, for any A,B⊆M, if every object with attributes in A also has the attributes in B, then A⟶B is called an implication of K. A and B are respectively called antecedent and consequence of the implication.Definition 2.
Given a conceptC, if A⊆IntentC, it matches an implication A⟶B.Definition 3.
Given a conceptC, if C is both an attribute concept and an object concept, then it is called 1−concept.Definition 4.
Given a conceptC, if C is only an attribute concept, then it is called 2−concept.
Then we describe the algorithm flow of implications-based Algorithm 1 for extracting MSCs as below.
Algorithm 1: Implications-based algorithm for extracting MSCs.
Input: a contextK=G,M,I, where G and M is a set of sensors and domains respectively.Output: the minimum sensor combinations that monitor all areas inM.(1)
Generate the concept lattice with reduced labelling ofK and implications in K(2)
LetKC be the set of 1/2−concept of K, KI be the set of implications in K, MSC=., CE=.(3)
IfM≠.(4)
Then For the first conceptC in KC(5)
If it matches the implicationA⟶B(6)
thenM←M−A​∪​B(7)
KR←KR−A⟶B(8)
KC←KC−1or2−concept generated froma|a∈A​∪​B(9)
IfC is a 1−concept(10)
thenMSC←MSC​∪​x // x is a sensor in the reduced extent of C(11)
else for a sensorx in ExtentC(12)
ifx∈CE(13)
thenMSC←MSC∪x(14)
CE←CE​∪​ExtentC(15)
Return 3(16)
Output MSC


## 4.3. The Stem Base-Based Algorithm for Extracting MSCs

The basic idea of this algorithm is to extract thestem base of region implications from concept lattice, and then extract different minimum sensor sets according to the rules. To describe this algorithm, we provide several definitions such as the stem base of the attribute implications [15–18].Definition 5.
If each subset ofM respects C also respects A⟶B, then the implication A⟶B follows from a set C of implications between attributes.Definition 6.
If every implication follows fromC, then a set of implications of a context is called complete.Definition 7.
If none of the implications follows from the others, then a set of implications of a context is called nonredundant.Definition 8.
P⊆M is called the pseudointent of G,M,I if and only if P≠P'′ and Q'′≠P holds for every pseudointent Q⊂P.Theorem 1.
The set of implicationsC=P⟶P″|Pis a pseudo−intent is nonredundant and complete, which is called the stem base of the attribute implications.Then we define the stem base-based Algorithm 2 as follows:Algorithm 2: The stem base-based algorithm for extracting MSCs.
Input: a contextK=G,M,I, where G and M is a set of sensors and domains, respectively.Output: the minimum sensor combinations that monitor all areas inM.(1)
Generate the concept lattice with reduced labelling ofK and the stem base of implications(2)
LetKC be the set of 1/2−concept MScs. Standalone K, KI be the stem base in K, MSC=, CE=(3)
IfM≠(4)
Then if there is an implicationA⟶B satisfying M⊆A∪​B(5)
thenMSC←MSC∪x // x is a sensor in the support set of A⟶B(6)
M=(7)
else for the first conceptC in KC(8)
if it matches the implicationA⟶B(9)
thenM←M−A​∪​B(10)
KR←KR−A⟶B(11)
KC←KC−1or2−concept generated froma|a∈A​∪​B(12)
IfC is a 1 −concept(13)
thenMSC←MSC​∪​x // x is a sensor in reduced extent of C(14)
else for a sensorx in ExtentC(15)
ifx∉CE(16)
thenMSC←MSC​∪​x(17)
CE←CE​∪​ExtentC(18)
Return 3(19)
Output MSC


## 4.4. Strategies for Reducing Sensor Energy Consumption

There are several ways to reduce the energy consumption of sensor nodes [54, 55], such as periodic awakening. One way is to make one node run out of its energy and then make the other overlapping nodes wake up. Another way is to calculate the size of the overlapping area of the nodes and decide whether they’re awake or not.In wireless sensor networks, there are the following ways to wake up the nodes:(1)
Full wake-up mode: In this mode, all nodes in the wireless sensor network wake up at the same time to detect and track targets in the network. Although this mode can obtain high tracking accuracy, it is at the cost of huge network energy consumption.(2)
Random wake-up mode: In this mode, the nodes in the wireless sensor network are randomly awakened by a given wake-up probabilityp.(3)
Select the wake-up mode by the prediction mechanism: In this mode, the nodes that have a greater return on tracking accuracy can be selectively awakened according to the needs of tracking tasks. Then predict the state of the target at the next moment through the information of this beat and wake up the nodes.(4)
Task cycle wake-up mode: In this mode, the nodes in the wireless sensor network are in the awake state periodically. Nodes in this mode can coexist with nodes in other working modes and assist these nodes to work.In this study, we choose the period loop mechanism and prediction mechanism to wake up nodes. After the processing of the proposed algorithms, we can obtain different MSCs. Then sort the sensor combinations and use the period loop mechanism to put each group of nodes into quasi-wake state in order. The quasi-wake state is a state between wake-up and sleep, which means the node is ready to be awakened. The principle of the period loop mechanism is that only one group of sensor nodes is put into the quasi-wake state in each cycle until each group of nodes has been processed once, and then start again with the first set of nodes and repeat this process. Lastly, wake up the sensor nodes that may have a task arrangement by using a prediction mechanism. In this mechanism, the sending node calculates and predicts the wake-up time of receiving node by retaining the address of the target node in the neighbor node information table [51]. This step ensures the receiving nodes wake up timely and avoid the problems like collision caused by waking up all nodes simultaneously.


## 5. Simulation Results and Analysis

### 5.1. Extraction of Implications Rules from Table1

In this section, we conduct some experiments with specific example to verify the effectiveness of the proposed algorithms. By using lattice-miner or ConExp, we can obtain the following concept lattices in Table1, as shown in Figure 2. The concept lattice tools can be downloaded from the websites https://sourceforge.net/projects/lattice-miner/ and https://sourceforge.net/projects/conexp/.From Figure2(a), we can obtain the intents and extents of concepts in the concept lattice constructed according to the example. Furthermore, we conduct several experiments to simplify the labelling. Therefore, the concept of lattices can be described by the line diagrams with reduced labelling. By reducing objects labelling, the corresponding line diagram is shown as Figure 2(b). Likewise, the line diagram in Figure 2(c) is built by reducing attributes labelling. And the line diagram in Figure 2(d) is built by reducing labelling.According to the concept lattices in Figure2, we can obtain the concepts including the intents and extents of nodes in Table 2.Table 2
Concepts in the obtained concept lattice.
NumberExtentIntent1Sensor-12345678Null2Sensor-12356a3Sensor-34678b4Sensor-1234f5Sensor-5678c6Sensor-123af7Sensor-234fg8Sensor-568ce9Sensor-678bc10Sensor-23afg11Sensor-34bfg12Sensor-36ab13Sensor-56ace14Sensor-68bce15Sensor-4bfgh16Sensor-3abfg17Sensor-7bcd18Sensor-6abce19Nullabcdefgh


### 5.2. Extracting MSCs from Table1 by Implications-Based Algorithm

We find out the implications and do some experiments to verify its effectiveness. The results including support and confidence are shown in Table3.Table 3
Implications in Table1.
Min. Support: 10%Min. Confidence: 100%IDImplicationSupport (%)Confidence (%)1{g}⟶ {f}37.51002{a, c}⟶ {e}251003{a, e}⟶ {c}251004{b, f}⟶ {g}251005{b, g}⟶ {f}251006{e}⟶ {c}37.51007{a, g}⟶ {f}251008{a, b, f}⟶ {g}12.51009{a, b, g}⟶ {f}12.510010{a, b, c}⟶ {e}12.510011{a, b, e}⟶ {c}12.510012{h}⟶ {b, f, g}12.510013{b, e}⟶ {c}2510014{d}⟶ {b, c}12.5100From Figure2(d), we can know that (sensor-4, h) and (sensor-7, d) are 1/2 concepts, and (a′, a″), (b′, b″), (c′, c″), (e′, e″), (f′, f″), (g′, g′′) are 2 concepts. The specific steps of the implications-based algorithm are as follows:Step 1.
Initialization.
Let the concept set C = {(sensor-4, h), (sensor-7, d), (a′, a″), (b′, b″), (c′, c″), (e′, e″), (f′, f″), (g′, g′′)}, W = {rule set}, MWZ = empty.Step 2.
Cycle.(1)
First cycle: Select the first concept (sensor-4, h) fromC. If h matches the 12th rule in W, then let C = C/{sensor-4, h}, M = M – {b, f, g, h} = {a, c, d, e}, MWZ = {sensor-4};(2)
Second cycle: Select the first concept (sensor-7, d) from C. If d matches the 14th rule inW, then let C = C/{sensor-7, d}, M = M – {b, c, d} = {a, e}, MWZ = {sensor-4, sensor-7};(3)
Third cycle: Select the first concept (e′, e″). If e matches the 6th rule in W, then let C = C/{(e′, e″)}, M = M – {e, c} = {a}. It is necessary to select one sensor from sensor-5, sensor-6 and sensor-8 covering e and put it into MWZ;(4)
Fourth cycle: Select the first concept (a′, a″). If there is no matching rule, then let C = C/{(a′, a″)}, M = M – {a} = empty set. We just need to select one sensor from sensor-1, sensor-2, sensor-3, sensor-5 and sensor-6 covering a and put it into MWZ. If it has covered the area covered by the sensors in MWZ, then MWZ remains unchanged, otherwise the sensor will be added to MWZ;Step 3.
LetM = empty set. End loop and output MWZ. According to the analysis of the example, MWZ can be expressed by the following combination of sensor nodes:MWZ = {sensor-4, sensor-7, sensor-5} or{sensor-4, sensor-7, sensor-6} or{sensor-4, sensor-7, sensor-8, sensor-1} or{sensor-4, sensor-7, sensor-8, sensor-2} or{sensor-4, sensor-7, sensor-8, sensor-3}.
The implications-based algorithm can find the minimum-maximum sensor combination, but a constant comparison is made between the selection and the rules. The number of rules affects the efficiency of the algorithm. Therefore, we will further reduce the number of rules in the rule set.


### 5.3. Extracting MSCs from Table1 by Stem Base-Based Algorithm

In the same way, we conduct some experiments on the second algorithm. The implications and experimental results including support and confidence are shown in Table4.Table 4
The implications in Table3.
Min. Support: 10%Min. Confidence: 100%IDImplicationSupport (%)Confidence (%)1{g}⟶ {f}37.51002{a, c}⟶ {e}251003{b, f}⟶ {g}251004{e}⟶ {c}37.51005{h}⟶ {b, f, g}12.51006{d}⟶ {b, c}12.5100The specific steps of the stem base-based algorithm are as follows:Step 4.
Let the concept KC = {(sensor-4, h), (sensor-7, d), (a′, a″), (b′, b″), (c′, c″), (e′, e″), (f′, f″), (g′, g′′)}, KI = {The rules set}, MWS = {}, M = {a, b, c, d, e, f, g, h}.Step 5.
Cycle.(1)
The first cycle: For any implication in Table4, there is not M ⊆ A∪B. Select the first concept ((sensor-4, h), h) from KC and h matches the fifth rule in W; Then let KC = KC\ {(sensor-4, h), (b′, b″), (f′, f″), (g′, g′′)} = {(sensor-7, d), (a′, a″), (c′, c″), (e′, e″)}, M = M – {b, f, g, h} = {a, c, d, e}, KI = {1, 2, 3, 4, 6}, MWZ = {sensor-4};(2)
The second cycle: For any implication inKI, there is not M ⊆ A∪B. Select the first concept ((sensor-7, d), d) from KC, and d matches the sixth rule in Table 4; Then let KC = KC\ {(sensor-7, d), (b′, b″), (c′, c″)} = {(a′, a″), (e′, e″)}, M = M – {b, c, d} = {a, e}, KI = {1, 2, 3, 4}, MWZ = {sensor-4, sensor-7};(3)
The third cycle: There is an implication (a, c)⟶{e}, which satisfies {a, e}⊆{a, c, e}. MWZ = {sensor-4, sensor-7, sensor-5} or {sensor-4, sensor-7, sensor-6}.


## 5.1. Extraction of Implications Rules from Table1

In this section, we conduct some experiments with specific example to verify the effectiveness of the proposed algorithms. By using lattice-miner or ConExp, we can obtain the following concept lattices in Table1, as shown in Figure 2. The concept lattice tools can be downloaded from the websites https://sourceforge.net/projects/lattice-miner/ and https://sourceforge.net/projects/conexp/.From Figure2(a), we can obtain the intents and extents of concepts in the concept lattice constructed according to the example. Furthermore, we conduct several experiments to simplify the labelling. Therefore, the concept of lattices can be described by the line diagrams with reduced labelling. By reducing objects labelling, the corresponding line diagram is shown as Figure 2(b). Likewise, the line diagram in Figure 2(c) is built by reducing attributes labelling. And the line diagram in Figure 2(d) is built by reducing labelling.According to the concept lattices in Figure2, we can obtain the concepts including the intents and extents of nodes in Table 2.Table 2
Concepts in the obtained concept lattice.
NumberExtentIntent1Sensor-12345678Null2Sensor-12356a3Sensor-34678b4Sensor-1234f5Sensor-5678c6Sensor-123af7Sensor-234fg8Sensor-568ce9Sensor-678bc10Sensor-23afg11Sensor-34bfg12Sensor-36ab13Sensor-56ace14Sensor-68bce15Sensor-4bfgh16Sensor-3abfg17Sensor-7bcd18Sensor-6abce19Nullabcdefgh


## 5.2. Extracting MSCs from Table1 by Implications-Based Algorithm

We find out the implications and do some experiments to verify its effectiveness. The results including support and confidence are shown in Table3.Table 3
Implications in Table1.
Min. Support: 10%Min. Confidence: 100%IDImplicationSupport (%)Confidence (%)1{g}⟶ {f}37.51002{a, c}⟶ {e}251003{a, e}⟶ {c}251004{b, f}⟶ {g}251005{b, g}⟶ {f}251006{e}⟶ {c}37.51007{a, g}⟶ {f}251008{a, b, f}⟶ {g}12.51009{a, b, g}⟶ {f}12.510010{a, b, c}⟶ {e}12.510011{a, b, e}⟶ {c}12.510012{h}⟶ {b, f, g}12.510013{b, e}⟶ {c}2510014{d}⟶ {b, c}12.5100From Figure2(d), we can know that (sensor-4, h) and (sensor-7, d) are 1/2 concepts, and (a′, a″), (b′, b″), (c′, c″), (e′, e″), (f′, f″), (g′, g′′) are 2 concepts. The specific steps of the implications-based algorithm are as follows:Step 1.
Initialization.
Let the concept set C = {(sensor-4, h), (sensor-7, d), (a′, a″), (b′, b″), (c′, c″), (e′, e″), (f′, f″), (g′, g′′)}, W = {rule set}, MWZ = empty.Step 2.
Cycle.(1)
First cycle: Select the first concept (sensor-4, h) fromC. If h matches the 12th rule in W, then let C = C/{sensor-4, h}, M = M – {b, f, g, h} = {a, c, d, e}, MWZ = {sensor-4};(2)
Second cycle: Select the first concept (sensor-7, d) from C. If d matches the 14th rule inW, then let C = C/{sensor-7, d}, M = M – {b, c, d} = {a, e}, MWZ = {sensor-4, sensor-7};(3)
Third cycle: Select the first concept (e′, e″). If e matches the 6th rule in W, then let C = C/{(e′, e″)}, M = M – {e, c} = {a}. It is necessary to select one sensor from sensor-5, sensor-6 and sensor-8 covering e and put it into MWZ;(4)
Fourth cycle: Select the first concept (a′, a″). If there is no matching rule, then let C = C/{(a′, a″)}, M = M – {a} = empty set. We just need to select one sensor from sensor-1, sensor-2, sensor-3, sensor-5 and sensor-6 covering a and put it into MWZ. If it has covered the area covered by the sensors in MWZ, then MWZ remains unchanged, otherwise the sensor will be added to MWZ;Step 3.
LetM = empty set. End loop and output MWZ. According to the analysis of the example, MWZ can be expressed by the following combination of sensor nodes:MWZ = {sensor-4, sensor-7, sensor-5} or{sensor-4, sensor-7, sensor-6} or{sensor-4, sensor-7, sensor-8, sensor-1} or{sensor-4, sensor-7, sensor-8, sensor-2} or{sensor-4, sensor-7, sensor-8, sensor-3}.
The implications-based algorithm can find the minimum-maximum sensor combination, but a constant comparison is made between the selection and the rules. The number of rules affects the efficiency of the algorithm. Therefore, we will further reduce the number of rules in the rule set.


## 5.3. Extracting MSCs from Table1 by Stem Base-Based Algorithm

In the same way, we conduct some experiments on the second algorithm. The implications and experimental results including support and confidence are shown in Table4.Table 4
The implications in Table3.
Min. Support: 10%Min. Confidence: 100%IDImplicationSupport (%)Confidence (%)1{g}⟶ {f}37.51002{a, c}⟶ {e}251003{b, f}⟶ {g}251004{e}⟶ {c}37.51005{h}⟶ {b, f, g}12.51006{d}⟶ {b, c}12.5100The specific steps of the stem base-based algorithm are as follows:Step 4.
Let the concept KC = {(sensor-4, h), (sensor-7, d), (a′, a″), (b′, b″), (c′, c″), (e′, e″), (f′, f″), (g′, g′′)}, KI = {The rules set}, MWS = {}, M = {a, b, c, d, e, f, g, h}.Step 5.
Cycle.(1)
The first cycle: For any implication in Table4, there is not M ⊆ A∪B. Select the first concept ((sensor-4, h), h) from KC and h matches the fifth rule in W; Then let KC = KC\ {(sensor-4, h), (b′, b″), (f′, f″), (g′, g′′)} = {(sensor-7, d), (a′, a″), (c′, c″), (e′, e″)}, M = M – {b, f, g, h} = {a, c, d, e}, KI = {1, 2, 3, 4, 6}, MWZ = {sensor-4};(2)
The second cycle: For any implication inKI, there is not M ⊆ A∪B. Select the first concept ((sensor-7, d), d) from KC, and d matches the sixth rule in Table 4; Then let KC = KC\ {(sensor-7, d), (b′, b″), (c′, c″)} = {(a′, a″), (e′, e″)}, M = M – {b, c, d} = {a, e}, KI = {1, 2, 3, 4}, MWZ = {sensor-4, sensor-7};(3)
The third cycle: There is an implication (a, c)⟶{e}, which satisfies {a, e}⊆{a, c, e}. MWZ = {sensor-4, sensor-7, sensor-5} or {sensor-4, sensor-7, sensor-6}.


## 6. Conclusion

In wireless sensor networks, the energy storage and power supply capabilities of sensors are the main problems that limit the application of sensor network technology. Therefore, how to extend the service life of sensor networks and reduce the energy consumption of sensor nodes is a key issue in the research of wireless sensor networks. To solve this problem, this paper proposes two FCA-based methods to reduce the energy consumption of nodes, which are different from other commonly used methods. One is an implications-based algorithm for extracting MSCs. This method can find the minimum-maximum sensor combination, but it has to constantly compare the selection and the rules. The number of rules affects the efficiency of this algorithm. Therefore, we need to reduce the rule set. The second method is stem base-based algorithm, which can find the base of rules. These two methods are based on FCA, and both help solve the following problems. The first is how to choose a sensor. The second is how to optimize the sensor layout. And the third is how to wake up the corresponding sensors. According to experimental results, these two methods have achieved good results in practical applications.The methods proposed in this paper are aimed at the research and discussion of the energy consumption of WSNs. The concept lattice of nodes in the wireless sensor network can express the relationship between nodes more effectively, and it is more helpful to choose nodes. With the deepening of research, we will propose more algorithms with concept lattice methods for other fields like radar sensor networks [56]. We believe there will be better effective solutions to such problems.



---

*Source: 8520447-2022-07-05.xml*