Effective Algorithm for Placement of Directional Wireless Chargers
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [36]
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Traditional sensor nodes are powered by batteries. The limited battery capacity, however, constrains the lifetime of the wireless sensor networks. Wireless power transfer technology allows energy transfers from a charger to sensor nodes via wireless, and thus solves the problem completely. One fundamental issue in wireless rechargeable sensor networks is the wireless charger placement problem, i.e., how to effectively place the chargers to maximize the overall charging utility of the network. Existing works mainly focus on the deployment issues of omnidirectional chargers, which are confined to positions such as the end point of triangles or lattice point in a grid. These works inevitably have their limitations. This study is to consider the general placement problem in which the charging area of chargers is a sector and the charger can be deployed at any position in the field with arbitrary orientation. First, a charging model for directional chargers is constructed based on trace data. Then, a series of novel techniques is proposed to transform the problem to develop an effective algorithm, CDG (charger deployment-greedy), with approximation ratio (1-1/e)/(1+e) to solve this problem. The simulation results demonstrate the effectiveness of the CDG algorithm. Compared with other two random algorithms, the CDG algorithm has performance gains of nearly 300% and 100%, respectively.

    Reference
    [1] Anastasi G, Conti M, Di Francesco M, Passarella A. Energy conservation in wireless sensor networks: A survey. Ad Hoc Networks, 2009,7(3):537-568. [doi: 10.1016/j.adhoc.2008.06.003]
    [2] Fafoutis X, Vuckovic D, Di Mauro A, Dragon N, Madsen J. Energy-Harvesting wireless sensor networks. In: Proc. of the 9th European Conf. on Wireless Sensor Networks (EWSN). Trento: University of Trento, 2012. 84-85. http://forskningsbasen.deff.dk/ Share.external?sp=See26122e-f4de-47d8-a73b-0da9d064071f&sp=Sdtu
    [3] Kurs A, Karalis A, Moffatt R, Joannopoulos JD, Fisher P, Soljacic M. Wireless power transfer via strongly coupled magnetic resonances. Science, 2007,317(5834):83-86. [doi: 10.1126/science.1143254]
    [4] Smith J. WISP Wiki. 2014. http://www.seattle.intel-research.net/wisp/
    [5] Shearer JG. Powercast. 2014. http://www.powercastco.com
    [6] Heins T. Powermat. 2014. http://www.powermat.com
    [7] Dell M. Laptopmag. 2014. http://www.laptopmag.com/reviews/laptops/dell-latitude-3330.aspx
    [8] Greene C, Harrist D, Kalp D, Tauche W. Making wireless sensor networks truly wireless using RF power. 2010. http://www. sensormgmt.com/Articles/Powered%20By%20FireFly60614.pdf
    [9] Shearer JG. Powercast. 2014. http://www.powercastsensors.com/category/applications/page/2/
    [10] Yoo J, Jeong E. Wireless charging technology. 2012. http://equity.co.kr/upfile/issue/2012/05/10/1336611859340.pdf
    [11] Dai HP, Wu XB, Xu LJ, Chen GH. Practical scheduling for stochastic event capture in wireless rechargeable sensor networks. In: Proc. of the Wireless Communications and Networking Conf. (WCNC). Shanghai: IEEE, 2013. 986-991. [doi: 10.1109/WCNC. 2013.6554698]
    [12] Dai HP, Xu LJ, Wu XB, Dong C, Chen GH. Impact of mobility on energy provisioning in wireless rechargeable sensor networks. In: Proc. of the Wireless Communications and Networking Conf. (WCNC). Shanghai: IEEE, 2013. 962-967. [doi: 10.1109/WCNC. 2013.6554694]
    [13] Dai HP, Wu XB, Xu LJ, Chen GH, Lin S. Using minimum mobile chargers to keep large-scale wireless rechargeable sensor networks running forever. In: Proc. of the Computer Communications and Networks (ICCCN). Nassau: IEEE, 2013. 1-7. [doi: 10. 1109/ICCCN.2013.6614207]
    [14] Dai HP, Jiang L, Wu XB, Yau DK, Chen GH, Tang S. Near optimal charging and scheduling scheme for stochastic event capture with rechargeable sensors. In: Proc. of the Mobile Ad-Hoc and Sensor Systems (MASS). Hangzhou: IEEE, 2013. 10-18. [doi: 10. 1109/MASS.2013.60]
    [15] Shearer JG. Powercast. 2014. http://www.powercastco.com/products/powercaster-transmitters/
    [16] He SB, Chen JM, Jiang FC, Yau DKY, Xing GL, Sun YX. Energy provisioning in wireless rechargeable sensor networks. In: Proc. of the Int'l Conf. on Computer Communications (INFOCOM). Shanghai: IEEE, 2011. 2006-2014. [doi: 10.1109/INFCOM.2011. 5935007]
    [17] Chiu T, Shih Y, Pang A, Jeng J, Hsiu P. Mobility-Aware charger deployment for wireless rechargeable sensor networks. In: Proc. of the Asia-Pacific Network Operations and Management Symp. (APNOMS). Seoul: IEEE, 2012. 1-7. [doi: 10.1109/APNOMS. 2012.6356102]
    [18] Liao JH, So WT, Jiang JR. Optimized charger deployment for wireless rechargeable sensor networks. 2013. http://in1.csie.ncu.edu. tw/~jrjiang/publication/wasn2013_submission_77.pdf
    [19] Shearer JG. Wireless power for battery-free wireless sensors. 2009. http://powercastco.com/PDF/2009SensorsExpo2.pdf
    [20] Horster E, Lienhart R. Approximating optimal visual sensor placement. In: Proc. of the Int'l Conf. on Multimedia and Expo. Melbourne: IEEE, 2006. 1257-1260. [doi: 10.1109/ICME.2006.262766]
    [21] Hörster E, Lienhart R. On the optimal placement of multiple visual sensors. In: Proc. of the 4th ACM Int'l Workshop on Video Surveillance and Sensor Networks. Santa Barbara: ACM Press, 2006. 111-120. [doi: 10.1145/1178782.1178800]
    [22] Zhao J, Cheung SS. Multi-Camera surveillance with visual tagging and generic camera placement. In: Proc. of the 1st ACM/IEEE Int'l Conf. on Distributed Smart Cameras (ICDSC). Vienna: IEEE, 2007. 259-266. [doi: 10.1109/ICDSC.2007.4357532]
    [23] Han XF, Cao X, Lloyd EL, Shen CC. Deploying directional sensor networks with guaranteed connectivity and coverage. In: Proc. of the 5th Annual IEEE Communications Society Conf. on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). IEEE, 2008. 153-160. [doi: 10.1109/SAHCN.2008.28]
    [24] Fusco G, Gupta H. Selection and orientation of directional sensors for coverage maximization. In: Proc. of the 6th Annual IEEE Communications Society Conf. on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). Rome: IEEE, 2009. 1-9. [doi: 10.1109/SAHCN.2009.5168968]
    [25] Osais YE, St-Hilaire M, Fei RY. Directional sensor placement with optimal sensing range, field of view and orientation. Mobile Networks and Applications, 2010,15(2):216-225. [doi: 10.1007/s11036-009-0179-0]
    [26] Ai J, Abouzeid AA. Coverage by directional sensors in randomly deployed wireless sensor networks. Journal of Combinatorial Optimization, 2006,11(1):21-41. [doi: 10.1007/s10878-006-5975-x]
    [27] Dai HP, Liu YH, Chen GH, Wu XB, He T. Safe charging for wireless power transfer. Technical Report, 2014. http://gps.nju.edu.cn/ ~hpdai/dh/SCP-TR.pdf
    [28] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979. 187-288.
    [29] Fu LK, Cheng P, Gu Y, Chen JM, He T. Minimizing charging delay in wireless rechargeable sensor networks. In: Proc. of the Int'l Conf. on Computer Communications (INFOCOM). Turin: IEEE, 2013. 2922-2930. [doi: 10.1109/INFCOM.2013.6567103]
    [30] De Berg M, Cheong O, van Kreveld M, Overmars M. Computational Geometry: Algorithms and Applications. Berlin: Springer- Verlag, 2008. 66-443.
    [31] Fujishige S. Submodular Functions and Optimization. 2nd ed., Amsterdam: Elsevier, 2005. 21-280.
    [32] Ai J, Abouzeid AA. Coverage by directional sensors in randomly deployed wireless sensor networks. Journal of Combinatorial Optimization, 2006,11(1):21-41. [doi: 10.1007/s10878-006-5975-x]
    [33] Cai YL, Lou W, Li ML, Li XY. Energy efficient target-oriented scheduling in directional sensor networks. IEEE Trans. on Computers, 2009,58(9):1259-1274. [doi: 10.1109/TC.2009.40]
    [34] Cai YL, Lou W, Li ML, Li XY. Target-Oriented scheduling in directional sensor networks. In: Proc. of the Int'l Conf. on Computer Communications (INFOCOM). Alaska: IEEE, 2007. 1550-1558. [doi: 10.1109/INFCOM.2007.182]
    [35] Cheng WF, Liao XK, Shen CX. Maximal coverage scheduling in wireless directional sensor networks. Ruan Jian Xue Bao/Journal of Software, 2009,20(4):975-984 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3240.htm
    [36] Tao D, Ma HD. Coverage control algorithms for directional sensor networks. Ruan Jian Xue Bao/Journal of Software, 2011,22(10): 2317-2334 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4080.htm [doi: 10.3724/SP.J.1001.2011.04080]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

戴海鹏,陈贵海,徐力杰,刘云淮,吴小兵,何田.一种高效有向无线充电器的布置算法.软件学报,2015,26(7):1711-1729

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:October 24,2013
  • Revised:April 03,2014
  • Online: July 02,2015
You are the first2032367Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063