{'fraction_non_alphanumeric': 0.02695800227014756, 'fraction_numerical': 0.0044457056375331065, 'mean_word_length': 4.699460916442049, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
QPP-MAC: A Greener Algorithm for Single Sink Wireless Sensor Networks

Major sources for energy wastage in wireless sensor networks (WSN) are Idle-listening, overhearing, collision, energy-hole and the transmission of unnecessarily large control-overheads. These issues cause fast energy drainage and low throughput that result in reduced network functionality. The idle-listening phenomenon occurs when the sensor nodes continue to listen although no data is expected to arrive [1]. Previous research shows that the idle:receive:send power ratios for a sensor can be typically 1:1.05:1.4 [2]. That means a receiving node may consume close to 95% of the energy needed to transmit. In addition, during the idle listening period, the sensors may pick up data packets not intended for them, resulting in the overhearing phenomenon consuming even more energy.


Introduction
Major sources for energy wastage in wireless sensor networks (WSN) are Idle-listening, overhearing, collision, energy-hole and the transmission of unnecessarily large control-overheads. These issues cause fast energy drainage and low throughput that result in reduced network functionality. The idle-listening phenomenon occurs when the sensor nodes continue to listen although no data is expected to arrive [1]. Previous research shows that the idle:receive:send power ratios for a sensor can be typically 1:1.05:1.4 [2]. That means a receiving node may consume close to 95% of the energy needed to transmit. In addition, during the idle listening period, the sensors may pick up data packets not intended for them, resulting in the overhearing phenomenon consuming even more energy.
There have been many synchronous protocols developed by authors to reduce the idle-listening and overhearing problems. These techniques typically reduce the energy usage by scaling down the time the sensors are awake. Figure 1 illustrates a very basic Sensor MAC (S-MAC) protocol where the sensor node periodically sleeps to conserve energy [1]. It can be readily seen this is a very basic static arrangement.
The T-MAC algorithm was introduced [3] to improve the performance further. In T-MAC, if no incoming data is found within a predetermined threshold period during sensing, then the sensors will go to sleep. Although the T-MAC is an adaptive scheme that reduces the energy consumption, still the nodes have to periodically wake-up. More protocols have been suggested to address the shortcomings of the S-MAC and T-MAC [4][5][6]. Most of them have high latency and bulky synchronization overhead.
Many asynchronous protocols have also been suggested by researchers in order to reduce the synchronization overhead [7-9]. These asynchronous protocols use preambles to detect free channels. These preambles generally introduce longer latency.
Collision happens when multiple nodes try to use a single channel simultaneously. Collision requires re-transmission, resulting in wastage of energy and bandwidth. Many of the above mentioned protocols also try to solve the collision issue. Good scheduling is the key to avoid collision. Note that over-scheduling will waste bandwidth and energy while under-scheduling will limit throughput.
The P-MAC algorithm was proposed [10] as an attempt to handle variable traffic loads effectively. The PMAC is an adaptive pattern based scheduling scheme where, the wireless sensors dynamically create sleep/ wake-up schedules based on their expected traffic loads. In P-MAC, the central sink can also override the scheduling commanding particular nodes to be more or less active. The P-MAC system performs very well in variable traffic load; however, it may not outperform synchronous protocols due to added overhead when the expected traffic load is constant.
Given the above background, it is obvious that a protocol performing well in both the steady and variable traffic conditions is necessary. In addition, in a WSN with a central data collection sink, the energy depletion rate for the sensors closer to the sink is much higher than sensors far away from the sink. This is because the closer nodes have to relay additional traffic coming from outer nodes. This issue is known as the energy-hole problem. There have been efforts to resolve the energy-hole problem by introducing number of distribution techniques that increase the number of nodes closer to sink [11][12][13]. However, these methods may not be suitable for all network scenarios.
A Quorum based MAC (Q-MAC) algorithm is a superior distributed scheduling protocol, which uses a grid-quorum approach as shown in Figure 2. This grid based scheduling algorithm reduces the energy-hole problem along with some other issues discussed above

Abstract
Wireless sensor networks (WSN) with a single data collection node or 'sink' play major role in data acquisition (DAQ) and control systems such as smart buildings. These 'many-to-one' networks have unique challenges in addition to regular energy concern issues. For example, nodes closer to the sink experience high traffic and drain faster. In this paper, a priority based, distributed, quasi-planned Medium Access Control (MAC) scheduling algorithm is suggested for such network architectures. The proposed Quorum-Pattern-Priority (QPP) MAC approach reduces energy wastage due to idle-listening, overhearing and transmission of unnecessary overhead. The algorithm is tested with multiple sensor classes each with a different data trans-mission pattern. The proposed protocol shows significantly low energy consumption while providing almost ideal throughput for steady traffic. The algorithm also better handles varying traffic compared to many conventional fixed scheduling algorithms. Class B: Data acquisition (DAQ) sensors [15] that wake-up less frequently than Class A and generate constant traffic. There are more class B sensors than class A sensors.
Class C: DAQ sensors for collecting slowly varying data. These wake-up even less frequently. The majority sensors in the network belong to class C. These have the lowest in transmission activity.
We consider different quality of service (QoS) requirements too [16]. For example, class A sensors need rapid data transfer without delay while, class B sensors can tolerate more delay and require less data transfer. Class C sensors are even more patient and slow than class B sensors.
It is also assumed that time is divided into equal length timeframes and all the nodes are time synchronized. We assume the simple synchronization technique described in S-MAC [1] with little overhead. All the sensor nodes have the same transmission range of 'R' meters. The area of a corona is C i where 'i' stands for corona number [14].

Protocol Design
We take three steps for the protocol design; planning the sensor and time distributions, sensor classification, and planning the scheduling. The first step ensures proper geo-graphic distribution of sensors and the appropriate distribution of time-frames to them. Sensor classification is self-explanatory. Finally we develop the adaptive scheduling protocol that ensures optimal sleep/wake-up timings for a given data transmission pattern that maximizes the performance.

Planning the sensor distribution
In this stage, the network area is divided into multiple coronas as follows. During the network initialization, the sink node sends a counter packet called 'NET INIT' to find the lowest number of hops to reach each node. After this initialization step the sink will be able to estimate the corona (number of hops) of each node along with the total number of coronas present in the network. The sink will then broadcast this message to all the nodes. Therefore, all the nodes will know all other nodes' locations. Especially each node will identify its single hop neighbours toward the direction of the sink.
If a corona C i has a total 'n' nodes, then the system will generate an 'n n' grid quorum for that corona and each sensor will have n 2 time- [14]. In the Q-MAC protocol, the total time frames are arranged in a grid form and each sensor node is assigned to a row and a column. Two nodes can communicate only when the row and the column is intersecting. For example, in the given figure, time-frames 0, 1, 2, 3 and 6 are designated for node A and time-frames 2, 5, 6, 7 and 8 are assigned for node B. Therefore, nodes A and B can communicate only during the common time frames 2 and 6. The sensors will sleep during the other time-frames to conserve energy. The detail of the grid quorum protocol is described [14], this protocol performs very effectively in steady traffic. However, the performance degrades with time varying traffic because the quorum assignments are static.
Another drawback in all the above mentioned protocols is that they only consider a single sensor type (same data rate, traffic pattern and QoS requirements etc.). For a more general study, different classes of sensors with varying service attributes need to be considered. Some sensors may transfer periodic data steadily while other nodes might emit bursty traffic on-demand basis. Therefore, in this paper, a distributed, quasi-planned scheduling algorithm with priority control is developed. The proposed QPP-MAC algorithm is uses the grid approach from the Q-MAC, algorithm. However, the proposed algorithm dynamically optimizes the scheduling based on the expected traffic considering multiple classes of sensors. The protocol performs much better than Q-MAC and S-MAC and designed to handle both steady and time varying traffic loads effectively. It shows good energy efficiency, high throughput, low latency with minimal increase in complexity.

Network Model
Our network model is similar to this system [14], there is a central sink and uniformly distributed immobile sensor nodes. The nodes transmit data to the sink node in a unidirectional manner. The entire network is divided into multiple coronas (or concentric circles) based on the transmission range of the nodes. Sensors in one corona can typically transmit to the nodes in the immediate inward corona with one hop. The area of the i th corona C i depends on the range of a sensor within the i th corona. Each hop distance creates a new corona in the system (i.e. if there are 5 hops in the shortest path to any sensor node from the sink, then the sensor is located in the 5 th corona). Figure 3 illustrates the corona distribution concept. This corona architecture helps scheduling the network better.
The protocol design is based on the different traffic patterns of the different classes of sensors. Let each sensor node has a unique name and location identifier. Three classes of sensors are considered as follows to begin with. More classes can be added to the algorithm as required.
Class A: Small number of nodes that produce bursty traffic.  frames. Note that each corona will have to use at least 'n' time-frames for its own (self-generated) traffic. The rest of the time-frames can be used for forwarding on-going traffic or may be unused (i.e. sleeping). For example, in Figure 2 host A and B only communicate with each other during 2 nd and 6 th time-frames only and the remaining timeframes can be used for ongoing traffic. Therefore, the outermost corona will require only 'n' time frames.
At this stage, let us assume initially all the nodes are fully loaded. This means all the sensor nodes always use their allocated time frames irrespective of its class. Each node of an outer level corona is assigned to the time-frames in such a way that it can communicate to multiple next hop nodes (known as the next hop (n h ) group) of inner corona during their wake-up times. This ensures less delay. The time cycle C y can be distributed among the nodes based on the grid quorum system. The traffic loads can be calculated for a node in C i as The nodes in a lower level corona will always have higher traffic than the nodes in outer level corona because; they have to transmit both their own traffic and traffic from upper level coronas. Hence, if the time-frame duration is t R , then receive, transmit and total active durations can be calculated as follows Total active duration = Receive duration + Transmit duration Therefore, active ratio for C i becomes From the calculation of active ratio (AR i ) and next hop group, the probability of finding a next hop neighbour in C i-1 awake as seen from C i corona can be estimated as Here, n h stands for the number of next hop neighbours in the designated group. This type of planned distribution ensures that all the nodes will have allotted time-frames for data transmission and the collision and retransmission will be minimal. This allocation is optimal for steady state traffic. However, the system needs to be adjusted further for varying traffic situation.

Sensor classification
Let us define three priority constants, δ A , δ B , δ C for nodes of class A, B, and C respectively. This classification is merely a way to differentiate between the nodes which will be used for scheduling the next section. The reason behind this assignment is to enhance planned distribution method described in section III-A to multi classes of sensors.

Planned schedulingε
A planned scheduling scheme is generated to ensure the nodes are following wake/sleep schedule according to the priority constant. The scheme follows basic algorithm of pattern generation of P-MAC as described in [10]. The nodes will generate the patterns based on their traffic load and priority constants. A node can increase its priority constants value to make it more energy efficient or decrease its priority constants value to transmit more data. The nodes will train themselves using the neighbour's traffic load and previous traffic history. Figure  4 shows the pattern generation method. A basic difference of the new protocol from P-MAC is that the priority constant δ x ; x Є A, B, C is determined directly from the traffic history and time-frame distribution information of section III-A. Diverse classes of sensors with dissimilar priority constants will generate the scheduling plans differently. Also, the new protocol generates the patterns based on the scheduling information of quorum. Thus, the pattern is generated only for the time-frames when there is a possible free next hop neighbour available in the network.
Hence, in this new scheme, the sensors will generate a tentative sleep/wake plan for the node and broadcast a pattern repeat time-frame (PRTF) packets [10]. The initial PRTF will be generated based on the next hop neighbour's availability and free channel in the network. The sensors will use the δ x ; x Є A; B; C value from the sensor classification to set its own wake-up sequence. It mainly determines how aggressively a sensor will be saving energy. When a sensor receives similar PRTFs from the next hop neighbours, it adjusts the sleep/wake schedule accordingly and transmits a pattern exchange time-frame (PETF). The neighbours will save the final wake-up schedule of this node as PETF.
The illustration in Figure 5 shows the actual wake/sleep schedule based on planned distribution information. The grey overlay is the new sleep time-frame which will otherwise be idle-listen period in a quorum based system without priority control.
In Figure 5, each grey overlaid time-frame is a measure of saved energy by the sensors. The energy saving is really high for any class B or class C sensors. This protocol can effectively increase the network lifetime to a great extent. In this pattern generation scheme, only large time scales (in order of hundred milliseconds) is involved [10]. Hence, the system can perform very well with the simple synchronization method derived in S-MAC [1]. This ensures reduced complexity and control overhead of the network. The total active duration of sensor nodes in corona C i and probability of a node awake can be found from  proposed algorithm. It can be observed that the new protocol has lower active ratio as compared to Q-MAC protocol. The low active ratio will result in high energy conservation. Figure 7 illustrates the average activity levels by various classes of sensors over multiple cycles. It is evident that class A sensors are more active than class B or C. However, the number of class A sensors are the lowest in the system. The simulation results show, the class A sensors will deplete energy faster if the priority scheduling is not deployed. In such a case, the network manager can change the priority constant for class B or class C sensors to facilitate the forwarding traffic. Hence, all the forwarding traffic only flows through 'B' or 'C' class sensors. This will reduce the potential energy-hole issue to some extent.
It can be observed from Figure 8 that class A sensors consumed the highest amount of energy as compared to other classes. This figure also indicates the importance of the sensor classification. If there were no classification, then class B and C sensors would wake-up at the same frequency as class A sensors. Hence, they will have the same energy consumption as class A. This shows the use of sensor classification and priority based scheduling manage the energy consumption better. Figure 9 shows per node energy consumption for the proposed QPP-MAC protocol is much lower compared to QMAC and SMAC protocols. This proves the effectiveness of the new algorithm. The per node energy consumption shown in the figure is based on the highest energy consuming node (class A) in each corona. Similarly, nodes from other sensor classes will also eventually consume less amount of (3) and (4) of section III-A. The active ratio with pattern generation can be calculated using, Tc n n δ δ + + = (5) and the probability of a next hop node awake for a node in C i will be, This type of pattern generation scheme permits data aware network, where the networking nodes can choose their energy efficiency based on the traffic requirements. This planned scheduling scheme, combined with previously discussed planned distribution and sensor classification steps, can potentially provide high confidence data aware network with high energy performance. The nodes or the sink can change the x value anytime to manage network's energy efficiency.

Energy Savings
The conserved energy for this algorithm can be calculated from sleeping duration. The length of sleeping interval for any time-frame with t R duration is (1-wake time )t R . In the proposed system, the nodes will be sleeping the entire time when there is no data to send or receive. The average number of sleep scheduled frames in a pattern is calculated in [10] Here, E(0) is the average sleep due to pattern. If C y is the cycle duration and d is the duty cycle length, then the time interval becomes In effect, the additional energy saving by each node in the new system can be given by, Here, P idle is the idle power consumption for any node. For a total 'n' number of nodes in the network, the total energy saving is,

Simulation Results
A simulation model is developed to validate the performance of the new protocol. Table 1 shows the parameters used in the simulation. Most parameters used in the simulation are based on the actual data from smart homes. The scheduling scheme is generated according to the pattern generation algorithm outlined in section III-C. The simulation results in Figure 6 show the change in a node's wake-up ratio with the   The Figure 10 shows receive and transmit duration of a node during a duty cycle. It shows that the receive duration is lower than the transmit duration, due to the fact that the node need to transmit both its own traffic and forwarding traffic. Hence, total duration is increased. The new protocol shows a reduction in both transmit and receive durations as compared to QMAC. The overall simulation results show the proposed algorithm has performance improvement over S-MAC, QMAC and P-MAC.

Conclusion
An energy efficient MAC layer protocol named QPP-MAC is proposed in this paper for a central sink based wireless sensor networks. This new protocol reduces the total energy requirement by each node using adaptive scheduling. The quorum based distribution of nodes ensures confirmed communication for steady traffic. The pattern based scheduling gives adaptive control during time varying traffic. Combination of quorum and pattern approaches improves the overall performance of the network. The ability to control energy saving adaptively by changing δ x gives extended flexibility without increasing complexity. The sensors are trained to wake-up only when necessary. This traffic aware scheduling can be altered for any part of the network without affecting the whole system.
The novel classification method of the sensor nodes also gives options for new adaptive control and data acquisition methods. All these features make the algorithm robust and usable in most central sink based sensor network with fixed node distribution.
The proposed QPP-MAC algorithm has distributed nodes with planned scheduling. Therefore, theoretically the new system should perform well in both static and variable traffic load situation.