Hierarchal Grouping Strategy with Adaptive Power Tuning in ZigBee Wireless Sensor Networks
Subject Areas : Sensor Networks
Mehran Pourmohammad Abdollahi
1
(University of Tabriz)
Javad Musevi Niya
2
(University of Tabriz)
Payman Mahmoudi Biroun
3
(University of Tabriz)
Keywords:
Abstract :
[1] B. Krishnamachari, Networking Wireless Sensors, Cambridge University Press, 2005.
[2] ZigBee Specifications, Sponsored by: ZigBee Alliance, 2008.
[3] A. Koubâa, R. Severino, M. Alves, and E. Tovar, "Improving Quality-of-Service in Wireless Sensor Networks by Mitigating Hidden-Node Collisions" IEEE Trans. on Industrial Informatics, vol. 5, No. 3, 2009.
[4] OPNET Tech. [Online]. Available: http://www.opnet.com, 2006
[5] S. Ray, D. Starobinski, and J. B. Carruthers, “Performance of wireless networks with hidden nodes: A queuing-theoretic analysis,” Comput, Commun., vol. 28, pp. 1179–1192, 2005.
[6] S. Ray, J. Carruthers, and D. Starobinski, “Evaluation of the masked node problem in ad-hoc wireless LANs,” IEEE Trans. Mobile Comput., vol. 4, pp. 430–442, 2005.
[7] F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part II—The hidden terminal problem in carrier sense multiple-accessand the busy-tone solution" IEEE Trans. Commun., vol. 23, pp.1417–1433, 1975.
[8] F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part III—Polling and (dynamic) split channel reservation multiple access" IEEE Trans. Comput., vol. 24, no. 7, pp. 832–845, 1976.
[9] P. Karn, "MACA—A new channel access method for packet radio" in Proc.9thARRL/CRRL Amateur Radio Comput. Netw. Conf. pp. 134–140, 1990.
[10] K. Sohraby, D. Minoli, T. Znati, Wireless Sensor Networks Technology, Protocols, and Applications, John Wiley & Sons Inc. 2007.
[11] J. Deng, B. Liang, and P. K. Varshney, "Tuning the carrier sensing range of IEEE 802.11 MAC," in Proc. IEEE Global Telecomm. Conf. (GLOBECOM), 2004, vol. 5, pp. 2987–2991.
[12] H. Zhai and Y. Fang, “Physical carrier sensing and spatial reuse in multirate and multihop wireless ad hoc networks,” in Proc. IEEE INF OCOM, Apr. 2006, pp. 1–12.
[13] L. Hwang, "Grouping strategy for solving hidden node problem in IEEE802.15.4 LR-WPAN" in Proc. IEEE 1st Int. Conf. Wireless Internet (WICON’05), Budapest, Hungary, pp. 26–32, 2005.
[14] Sh. Farahani, ZigBee Wireless Networks and Transceivers, Newnes, Elsevier Ltd. Chapter 1,2,3. 2008.
[15] K. Sohraby, D. Minoli, T. Znati, Wireless Sensor Networks Technology, Protocols, and Applications John Wiley & Sons Inc. 2007.
Hierarchal Grouping with Adaptive Power Tuning in ZigBee Wireless Sensor Networks
|
Mehran Pour Mohammad Abdollahi, Javad Musevi Niya, Payman Mahmoudi Biroun
|
Abstract—Designing wireless sensor networks should meet appropriate parameters such as quality of service (QoS) defined by different users. The variable physical conditions of the environment, processing and transmission power limitations and limited communication capabilities are the most important obstacles that influence QoS parameters such as throughput, delay, reliability and network lifetime. The most important problems that directly have destructive effects on these parameters are hidden and exposed node problems. These problems extremely decrease throughput and increase delay and power consumption in the network. This paper proposes a new and efficient method to decrease the mentioned problems that relies on clustering, grouping and subgrouping strategy. Then different transmission powers are allocated to different nodes depending on their hierarchy level to communicate in their active time slots to decrease power consumption. This mechanism has been simulated by OPNET on IEEE802.15.4/Zigbee.
Index Terms— Hidden node problem, exposed node problem, quality of service (QoS), power consumption
I. INTRODUCTION
A. Research context
D
ailly increasing of monitoring and controlling systems and gathering information from hardly accessible places, have led to design cost-effective devices with processing and communicating abilities and have formed new networks named Wireless Sensor Networks (WSNs). Wireless sensor networks provide bridges between the virtual world of information technology and the real physical world [1]. Due to wide variety of WSN applications from ecological habitat monitoring to Military surveillance and target tracking, the quality of service (QoS) may differ from one to another, but all of them will demonstrate better performance with higher throughput, lower delay and longer lifetime. Achieving high QoS in WSNs is one of the most important keys and challenged due to specific problems and limitations of these networks. Therefore, many protocols and methods have been proposed about the communicating process, accessing to the common media and the energy consumption to improve the QoS metrics. It is obvious that improving some metrics may influence another metrics and decrease system performance. Thus, achieving the best trade-off in the network depends on the applications that are needed by users and the aims of projects. In this paper a new method with acceptable results is proposed for many applications of Zigbee networks [2].
B. Problem Statement
Zigbee wireless sensor networks like the other WSNs, use CSMA family in their Medium Access Control (MAC) to access the common channel. Actually, this is some kind of a
contention between the nodes to obtain a time slot and guarantee their data transmission. The most important drawbacks of these networks are hidden-node and exposed-node problems. The problems get more serious by increasing the number of nodes and traffic load and cause a great reduction in network performance. A hidden-node problem occurs when two wireless nodes -not in range of each other or due to the existence of some barriers- cannot receive any signal from each other and begin to communicate with a node that is commonly visible to both of them at the same time. Thus, the collision happens (See figure 1). Likewise, the exposed node problem occurs when two nodes which are in range of each other want to communicate with different nodes which are commonly visible to none of them (See figure 2). Both problems dramatically affect the QoS parameters explained below
1) Throughput, which denotes the amount of traffic
successfully received by the destination node. This parameter decreases by increasing collisions.
2) Delay, which is the time duration between generation of a packet and its reception by the destination node. This parameter increases due to the high number of retransmissions and waiting for accessing channel while an exposed-node problem occurs.
3) Power consumption, which represents the average network power consumed by all nodes and increases due to retransmissions.
Figure 1) Hidden-Nodes problem
Figure 2) Exposed-Nodes
The hidden node problem can be decreased by changing the cover range of the nodes. So far several works but not effective enough have been presented to overcome the hidden nodes problem. In [3] a method called H-NAMe, has been introduced and simulated in different statuses by OPNET [4]. It shows that increasing the cover range of nodes can increase the throughput; The problem is that this is only accomplished by a significant raise in the transmission power or a decrease in receiving threshold in the receiver side, which both result in generating more exposed nodes and more power consumption. In this paper, a new method is presented based on grouping theory and using the hierarchy for MAC protocol in order to overcome the problems. This hierarchy leads in forming Groups consisting of a Group-head (GH) and Subgroups. Several simulations have been achieved by OPNET on ZigBee networks which show that this method is an effective way to increase throughput.
C. Contributions
Section II provides an overview on previous works. Section III proposes a new hybrid method based on clustering, grouping and hierarchy which can decrease the hidden and exposed nodes efficiently. The simulation is performed and the results are depicted and compared in section IV, and finally a conclusion is represented based on the simulation results in section V.
II. Previous Works
So far, some solutions have been proposed to solve the hidden node problem. Mathematical analysis in [5, 6] has been used to show its effect in small-scale networks. Some practical methods have been introduced to eliminate the hidden nodes in wireless networks and have been categorized as below
1) Busy Tone Mechanism; introduced by F. A. Tobagi and L. Kleinrock, provides a solution called busy tone multiple access (BTMA) for star networks [7, 8] and uses separate radio to transmit busy tone for notifying the other nodes.
2) Request To Send/Clear To Send (RTS/CTS) mechanism; the method introduced in [9, 10] reserves the channel by communicating nodes before starting a transmission via sending RTS message and waiting for CTS response.
3) Carrier Sense Tuning Mechanism: the idea was proposed by J. Deng and his colleagues in [11] to increase the sensitivity of receiver by reducing the receiver threshold so that the node could extend the radio coverage and hear farther nodes. This mechanism has been simulated for different carrier senses to analyze the network performance. In [12], the optimal value has been obtained under strict consideration.
4) Node Grouping Strategy: This idea is an effective way to reduce the hidden nodes in the network [13]. It separates the nodes to different groups in which all the nodes in each groups are visible to each other and can hear the transmissions occurring in that group radio range. The grouping process begins when a hidden node collision occurs. The cluster head detects the collisions by distinguishing between hidden node collisions and contend collisions regarding the start time of collision. After this stage, CH broadcasts a pulling message in the network. The grouping process begins by gathering data via nodes using their neighbors’ response to pulling message. After grouping process, different time slots are allocated to each group to content for accessing to the channel.
5) The H-NAMe: The Hidden Node Avoidance Mechanism (H-NAMe) introduced in [3] is based on grouping strategy, separate the nodes in the network to different groups and allocates a given time slot to each group. The difference between the H-NAME and the previous grouping strategy is the process of group formation and the joining as a member. A four-stage process is done to sort the nodes. At first stage, each node which wants to join a group, sends a Group-Join.request message to CH; This message is heard by the neighbor nodes. At the second stage, the requesting node waits for aGroupRequestTimer message. During this time, the neighbors who have heard this message send a message called Neighbor.notify to CH and this is heard by the requesting node. At the third stage, the requesting node sends its report to the CH. This reply includes some information about the neighbors that have sent a notification. At the last stage, after considering the reply, CH attaches this node to one of these groups. If there is not any group in the network in which all of its members does not have bidirectional link with the requesting node, the CH forms a new group and if the number of groups are equal to aMaxGroupNumber, the node has to request later or stay as a single node and communicate in CAP instead of GAP. The Group Access Period (GAP) is the part of the CAP which is allocated to the groups.
These methods help to avoid cited problems but still is ineffective against the growth of number of nodes in the network and need complex or additional hardware which leads in more energy consuming and more costs.
III. Hierarchal Grouping with Adaptive Power Tuning
A. Network Model
A cluster-based wireless network with a number of randomly distributed nodes is considered where in the cluster there is a Full Functional Device (FFD) with capability of communicating with all of the nodes bi-directionally called cluster head (CH). CH can perform all of the instructions needed in the network. CSMA family is used to contend for medium access and communicate during Group-Time-Slot (GTS) allocated to them. The contention is achieved during a time interval called Contention Access Period (CAP). The nodes wake up and inter the CAP procedure after receiving the beacon message; Then, the Contention Free Period (CFP) begins containing GTS for some of nodes. By end of the active time, the inactive time starts and all the nodes go to asleep to save their battery power consumption [14]. The transmission power is the same for all nodes. Now, we are proposing the Hierarchal Grouping with Adaptive Power Tuning which is based on grouping and hierarchy applying different powers for different nodes.
Hierarchy: In proposal method, data may reach CH directly or after passing several nodes depending on its distance from CH. This way of communication has been exploited in LEACH [1] and D-MAC [15] protocols. The protocols use hierarchy and transfer the messages from lower hop to the upper hop. We use these protocols and S-MAC protocol [15] basically used in ZigBee WSNs, to obtain new hybrid method (See figure 3).
Cluster and Group Formation Algorithm: A number of randomly distributed nodes are considered. The nodes wake up after a random waiting time and they begin to communicate. In ZigBee/IEEE802.15.4 always a coordinator is needed. One of the FFD nodes must become a coordinator. The FFD node that wakes up sooner than the others can be the coordinator which in cluster based networks is called cluster head. The proposed algorithm is demonstrated in figure 4.
When a node wakes up, swap to receiving mode as long as two beacon interval in order to hear any beacon sent by the other nodes. If it does not receive any beacon it introduces itself as CH, then sets its power and sends the CH beacon at first of each period to synchronize the other nodes. If a node receives any beacon either a CH beacon or a Group Head (GH) beacon, the node will find out that another node has already been CH. Therefore, the node has four options: 1) the node must associate to one of the groups, 2) the node must become a subgroup of one of groups formed before, 3) the node must request the CH to form a new group, 4) the node must associate to the cluster as a single node.
1) Associating to the Group: When a node receives a CH beacon, it waits to hear GH beacon probably located in the neighborhood. Now, if the node receives a GH beacon, it will send a GroupMember.Request to GH to join the group. In response, the GH will send an Ack. message. The requesting node will wait for macResponseWaitTime. During this time the GH will check to see if the number of its members is smaller than the aMaxGroupMember or not. After this duration, the node will send a data request to the GH and if the number of members is smaller than the aMaxGroupMember GH will accept the node request and will send a GM.Association.Response message to the node to confirm it. This process is shown in figure 5.
2) Associating as a Subgroup: If a node does not receive any GH beacon or cannot join that group due to completion of the GH capacity it will broadcast a request by the name of SubGroupMember.Request to the nodes which have already become members of a group. On condition that any of these nodes does not have any subgroup, it can accept the node as a subgroup and reply it by SubGM.Association.Response. This process is similar to associating to a group.
3) Associating as a GH or a Single Node: If a node cannot be a group member or subgroup it can form a new group and become a GH providing CH permission. In this condition the node sends a GH.Association.Response to the CH and requests to be a GH. The CH checks if the number of nodes is smaller than aMaxGroupNumber or not. If so, the CH sends a response to confirm the group formation. But, if CH is overloaded by GHs, the node must try later.
4) Associating as a Single Node: This process is as the same as third process just considering that a field named Association Type is defined to distinguish between the requests.
B. Superframe Structure
In ZigBee WSNs, the superframe has two parts: 1) active period; 2) inactive period. The active period is combination of CAP and CFP. The H-NAMe proposed a new structure for the superframe so that it used some part of CAP for groups
START
|
Listen to the channel for CH Beacon
|
Receives CH Beacon
|
Yes
|
No
|
Associate to the network
|
Introduce itself as a CH
|
Listen to GH Beacon
|
Yes
|
Receives GH Beacon
|
No
|
Associate to a Group
|
Associate as a SubGroup
|
Associate as a GH & Form a new group
|
Associate as a Single
|
Figure 4) Cluster and group formation algorithm
Figure 5) Associating to the Group
and separated the groups time slots. Therefore, each group could content in its own time slot instead of contenting in CAP. The time slots allocated for groups are called Group Access Period (GAP).
In this paper, the superframe structure has been changed and the GAP has been used for communication between the group members and their group heads. CAP is divided into three parts (see figure 6): 1) Contention Access Period (CAP), 2) Group Access Period (GAP) and 3) Contention Free Period (CFP). The first part itself has two parts: a) Group Head Contention Access Period (GHCAP) which is used by GHs to get GTS, b) Single Access Period (SCAP) which is used by single nodes to get GTS. The second part is divided into two parts: a) SubGroup Communication Period (SGCP) which is allocated for subgroups to communicate with their subgroup heads, b) Group Communication Period (GCP) which is allocated for group members to communicate with their group heads. Each group communicates only in its allocated time slots. The third part containing GTS is allocated to GHs or single nodes to communicate with the CH.
C. Network Management
After establishing network, all nodes synchronize themselves with time-table regulated by CH. They wake up when beacon is broadcasted at the beginning of each period and go to sleep at the beginning of inactive period. Likewise, each node will be in asleep or awake mode during the active period depending on the level of hierarchy.
After receiving beacon, Subgroups go to sleep and wake up in SGCP to communicate with their subgroup heads. Then they go to sleep until next beacon. Group Members go to sleep after receiving beacon and wake up in SGCP if they are subgroup heads else they wake up in their group time slots (in GCP interval). They receive GH beacon and get some information about their functions; that is a GH wakes up two times: 1) in GHAP duration in which they content for the channel allocation, 2) in GCP duration in their time slots. At the beginning of second interval, the GHs broadcast a beacon frame with lower energy, which is similar to CH beacon including GCP specifications.
GCP field can specify a group ID, transceiver power and group end time slot. The second field determines the nodes with data pending in GH. Thus, by receiving this beacon, the member node sets its power and send the data request to its GH if it has data pending. A duplex communication can be done between a GH and a member using CSMA-CA. After the group time slots period, the members go to sleep until next beacon to cut off energy consumption.
The cluster head wakes up at the beginning of each beacon interval and sends the main beacon to synchronize all the cluster nodes. This node will stay awake during the CAP to communicate with the GHs and single nodes if they request GTS. During GAP, CH can go to sleep to decrease the energy consumption. Then during CFP, CH has to wake up and communicate with GHs and single nodes that have already obtained time slots. The CH beacon specifies all start and end time slots for all groups.
D. Adaptive power Tuning Algorithm
In all previous works, the proposed methods tried to decrease power consumption due to retransmissions caused by the hidden node collisions. For instance, the H-NAMe reduced power consumption in comparison with the node grouping strategy during the grouping process but did not propose any plan to reduce power consumption after grouping stage.
Suppose that the CH broadcasts the beacon with a determined transmission power and communicate with all nodes with the same power. In proposed method, each node changes its transmission power depending on its hierarchy in the cluster shown in figure 7. Assume that the CH radio coverage is equal to R which is the cluster range. Assume that the receiver threshold (Prx) is determined and same for all nodes and the central frequency is equal to 2.4GHz. It is considered that both transmitter and receiver antennas are isotropic. Apart from the fading, the path loss ([λ2/16π2R2]-1) determines the radio coverage for each node. This range is obviously proportionate to the transmission power (R2=K.Ptx, K=9.4873×10-5/Prx). The radio coverage for GHs with transmission power P'tx and for group members with transmission power P''tx are respectively as follows
R'2=K.P'tx , R"2=K.P"tx (1)
We consider that P"tx=Ptx/4. Therefore, R" is calculated as below
(2) |
(3) |
Figure 6) New Superframe Structure
Figure 7) Cluster and Groups and Members Radio Coverage
Therefore, CH broadcasts its beacon with transmission power of Ptx and the GH broadcasts its beacon with one sixteenth of transmission power of a CH. On the other hand, GH communicates with CH with power Ptx and with power Ptx/16 with its members. The members communicate with GH only with one fourth of this power. This method will save a great amount of energy and increase battery lifetime.
IV. Simulation Results
In this paper, OPNET ver. 14.5 is used for simulations. The nodes are distributed randomly in a 100x100m2 square area and the scenario is simulated in different cases as follows
Case 1) This is the standard mode in which all nodes communicate with PAN Coordinator with the same transmission power and same receiver threshold. Thus, there is not any hidden node while exposed nodes grow. By reducing the receiver threshold, the radio coverage and exposed nodes reduce but hidden nodes appear in the network. These two situations have been simulated and had the same results which are shown in figure 8.
Figure 8) Simulation Results of Case 1 for
Ptx = 0.05w/packet,
-85dbm < Prx < -60dbm,
68.8m < r < 1250m
The results show that throughput reaches nearly 3600bit/sec at the presence of hidden and exposed nodes problems and delay is equal to nearly 0.023sec.
Case 2) In this case, the grouping is so that members send their data into a node similar to GH and GH sends the collected data to the CH. The transmission power and receiver threshold have been changed, the network has been simulated for both situations and the results have been demonstrated in figure 9 and figure 10.
The results of cases 1 and 2 show that the hierarchy has caused a significant raise in delay and throughput parameters. Delay has reached approximately 0.15sec and throughput has reached approximately 29000bit/sec.
Figure 9) Simulation Results of Case 2 for
Ptx = 0.05w/packet,
Prx ≈ -85dbm,
r ≈ 1250m
Case 3) In this case which represents the proposed method, the grouping process has achieved and subgroups and single nodes have been considered with different transmission powers. Due to limitations of simulation, the transmission power of GHs has been considered constant and equal to the power which is used to communicate with the CH. The results are shown in figure 11.
Figure 10) Simulation Results of Case 2 for
Ptx=0.05w/packet, P"tx=0.0125w/packet
Prx≈-60dbm,
r≈68.8m , r"≈68.8m
The results of proposed method show that although delay has increased nearly 5 times, the throughput has increased approximately 10 times, so QoS has improved totally.
We use the traffic-sent chart illustrated in figure 12 to calculate the power consumption in the network. The diagram is the same for all cases. In case (1) all 58 nodes transmit with 0.05w/packet. Thus, the average power for the network is equal to 0.05w/packet. Considering that the traffic sent equals to 1packet/sec, the consumed power in 1 hour is calculated:
(4)
In case (3) only 9 nodes (CH, GHs and single nodes) transmit with 0.05w/packet and the other 49 nodes transmit with 0.0125w/packet. Thus, the average power for the network is calculated as follows:
(5)
Figure 11) Simulatin Results of Case 3 for
Ptx=0.05w/packet, P"tx=0.0125w/packet
Prx≈-60dbm,
r≈68.8m , r"≈34.4m
Figure 12) Traffic Sent in All Conditions
and the consumed power during 1 hour will be equal to:
(6)
Although there is an increment in delay parameter which is a destructive effect, the power consumption has reduced approximately 63.4% and the throughput has increased to desirable amounts. Actually, the reduction in the power consumption could be more than the simulated scenario because in real test bed, sensors could go to sleep in some part of active mode but it has not been considered due to limitations in the simulation.
V. Conclusion
This paper proposes a new hybrid MAC that relies on clustering and grouping strategy used in D-MAC and LEACH protocols. This network has been simulated by OPNET software. Using hierarchy structure and different time slots for different groups causes the reduction of hidden and exposed node problems. Likewise, different transmission powers are considered for different nodes so that power consumption can be reduced in the cluster based networks. Although the message transfer delay increases due to the hierarchy, retransmissions reduces and as a result, throughput and network reliability increases. Therefore, in some applications that delay is not a critical parameter, this method can exhibit better performance in comparison with the other methods. The results demonstrate total improvement in QoS. Calculations for different transmission power for different nodes based on their distances from the group head or cluster head still remain an open problem.
REFERENCES
[1] B. Krishnamachari, Networking Wireless Sensors, Cambridge
University Press, 2005.
[2] ZigBee Specifications, Sponsored by: ZigBee Alliance, 2008.
[3] A. Koubâa, R. Severino, M. Alves, and E. Tovar, "Improving Quality-
of-Service in Wireless Sensor Networks by Mitigating Hidden-Node
Collisions" IEEE Trans. on Industrial Informatics, vol. 5, No. 3, 2009.
[4] OPNET Tech. [Online]. Available: http://www.opnet.com, 2006
[5] S. Ray, D. Starobinski, and J. B. Carruthers, “Performance of wireless
networks with hidden nodes: A queuing-theoretic analysis,” Comput,
Commun., vol. 28, pp. 1179–1192, 2005.
[6] S. Ray, J. Carruthers, and D. Starobinski, “Evaluation of the masked
node problem in ad-hoc wireless LANs,” IEEE Trans. Mobile Comput.,
vol. 4, pp. 430–442, 2005.
[7] F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part
II—The hidden terminal problem in carrier sense multiple-accessand the
busy-tone solution" IEEE Trans. Commun., vol. 23, pp.1417–1433,
1975.
[8] F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part
III—Polling and (dynamic) split channel reservation multiple access"
IEEE Trans. Comput., vol. 24, no. 7, pp. 832–845, 1976.
[9] P. Karn, "MACA—A new channel access method for packet radio" in
Proc.9thARRL/CRRL Amateur Radio Comput. Netw. Conf. pp. 134–
140, 1990.
[10] K. Sohraby, D. Minoli, T. Znati, Wireless Sensor Networks
Technology, Protocols, and Applications, John Wiley & Sons Inc.
2007.
[11] J. Deng, B. Liang, and P. K. Varshney, "Tuning the carrier sensing
range of IEEE 802.11 MAC," in Proc. IEEE Global Telecomm. Conf.
(GLOBECOM), 2004, vol. 5, pp. 2987–2991.
[12] H. Zhai and Y. Fang, “Physical carrier sensing and spatial reuse in
multirate and multihop wireless ad hoc networks,” in Proc. IEEE INF
OCOM, Apr. 2006, pp. 1–12.
[13] L. Hwang, "Grouping strategy for solving hidden node problem in
IEEE802.15.4 LR-WPAN" in Proc. IEEE 1st Int. Conf. Wireless
Internet (WICON’05), Budapest, Hungary, pp. 26–32, 2005.
[14] Sh. Farahani, ZigBee Wireless Networks and Transceivers, Newnes,
Elsevier Ltd. Chapter 1,2,3. 2008.
[15] K. Sohraby, D. Minoli, T. Znati, Wireless Sensor Networks
Technology, Protocols, and Applications John Wiley & Sons Inc.
2007.