ABSTRACT
Contents 22.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 22.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527 22.3 w-LLC: Weighted Low-Energy Localized Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
22.3.1 Initial Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 22.3.2 Weighted Localized Clustering Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
22.3.2.1 NLP-Based Approach for w-LLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529 22.3.2.2 VC-Based Approach for w-LLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
22.3.3 Iterative Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 22.4 Effectiveness of w-LLC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
22.4.1 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 22.4.2 Guarantee of Perfect Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
22.5 Adaptability for RFID Reader Collision Arbitration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538 22.5.1 Classification on RFID Reader Collision Arbitration . . . . . . . . . . . . . . . . . . . . . . . . . . 538 22.5.2 Coverage-Aware RFID Reader Collision Arbitration: w-LCR . . . . . . . . . . . . . . . . . 539
22.6 Performance Evaluation of w-LCR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 22.6.1 Possibility of RFID Reader Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 22.6.2 Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
22.7 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
22.A Appendix A: Proof of Corollary 22.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 22.B Appendix B: Proof of Corollary 22.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 22.C Appendix C: Proof of Corollary 22.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
22.1 Introduction In the wireless networking and mobile computing environment, because mobile devices generally are energy-constraints, the power management of mobile devices is an important issue with regard to network lifetime. Due to the limited power source of mobile devices, energy consumption has been considered as the most critical factor in designing network protocols. Facing these challenge and research issues, several approaches to prolong the lifetime of the wireless networking andmobile computing, including clustering schemes and structured schemes with a two-tiered hierarchy, have been investigated [1-5]. The clustering technology facilitates the distribution of control over the network and enables locality of communications [2]. The two-tiered hierarchical structuring method is an energy-efficient scheme for wireless networking [6]. It consists of the upper tier for communicating among cluster heads (CHs) and the lower tier for acquired events and transmitting them to CHs. However, in the clustering scheme and the two-tiered hierarchical structuring scheme, if the cluster range is larger than optimal, a CH consumes more energy than required. On the other hand, a smaller-than-necessary range results in a shortage of covering the entire network field. Therefore, we propose a novel clustering-based algorithm that aims to minimize the energy consumption of CHs under the hierarchical structure [7]. Our proposed clustering scheme, low-energy localized clustering (LLC), is able to regulate the cluster radius by communicating with CHs for energy savings. We extend our basic scheme to weighted low-energy localized clustering (w-LLC) to cope with the case that events occur more frequently in a certain area of the sensor network field. Also when the CHs have different computing power, we need to assign weight factors to each CH. In these cases, w-LLC, therefore, is better than LLC in practical environment to apply the algorithm. The major application areas of w-LLC are “wireless sensor networks” and “RFID networks.” In wireless sensor networks, sensors are deployed over the network sensing fields and perform the specific tasks of processing, sensing, and communicating capacities [8,9]. Because of the limited power source of sensors, energy consumption has been considered as the most critical factor in designing sensor network protocols. To achieve energy-efficiency in wireless sensor networks, clustering schemes and hierarchically structured schemes are proposed [1-6]. RFID network systems, also, have two-tiered hierarchical structure. In the upper tier, there are RFID readers to receive the signals from the RFID tags. In the lower tier, there are RFID tags. In the hierarchical clustering-based two-tiered network architecture, the larger the overlapping areas of clusters that RFID readers form, the higher the collision probability among the readers. We propose weighted localized clustering for RFID networks (w-LCR) as an application area of w-LLC, which minimizes the overlapping areas among clusters by regulating an RFID reader’s cluster radius dynamically to minimize the RFID reader collisions. The basic feature of RFID reader collision arbitration protocol is proposed in [10]. In [10], however, we do not consider energy efficiency but guarantee perfect coverage. This chapter shows energy efficiency via performance evaluations and perfect coverage via theoretical analysis. The remainder of this chapter is organized as follows. In Section 22.2, we investigate previous work on the clustering scheme and the hierarchical structure scheme in wireless sensor networks and RFID networks. In Section 22.3, we propose w-LLC,
a weighted dynamic localized scheme designed for hierarchical clustering protocols. We evaluate the effectiveness of w-LLC with simulations and theorem proving in Section 22.4. In Section 22.5, we apply w-LLC to RFID reader collision arbitration algorithm and, in Section 22.6, we show the performance of the coverage-aware reader collision arbitration. Section 22.7 concludes this chapter and presents the direction of future work.
