Broadcast latency optimization in multihop wireless networks

Details Broadcast latency optimization in multihop wireless networks Broadcast latency optimization in multihop wireless networks

2011-03-08

2011-03-08

Yao, Kwang B (Department: 2473)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

Reexamination Certificate

active

07903653

ABSTRACT:
A system and methodology that can optimize practical performance by reducing broadcast latency and collisions in a multihop wireless network is provided. The system includes an optimization component that determines a schedule for transmitting and/or receiving messages at nodes in the network during one-to-all broadcasting, all-to-all broadcasting, and/or all-to-one collection. The schedule enables each node in wireless network to participate in broadcasting as soon as possible, such that, when a node transmits a message to its parent to deliver the message to a source node, the children of the node also receive the message and initiate broadcasting the message in their subtrees in parallel. Further, during data collection, the schedule for messages to be transmitted to a sink node is determined based in part on a priority associated with the message. Additionally, the generated schedule does not affect a set of theoretical bounds associated with a broadcast algorithm employed by the network.

REFERENCES:
patent: 5926101 (1999-07-01), Dasgupta
patent: 2003/0174701 (2003-09-01), Angle et al.
patent: 2008/0013501 (2008-01-01), Keshavarzian et al.
patent: 2009/0147723 (2009-06-01), Fang et al.
C. Ho, K. Obraczka, G. Tsudik, and K. Viswanath, “Flooding for reliable multicast in multi-hop ad hoc networks,” in Proc. of the Int. Work. on Disc. Alg. and Meth. for Mobile Comp. and Comm., 1999, pp. 64-71. http://citeseerx.ist.psu.ed/viewdoc/summary?doi=10.1.1.22.7204. Last accessed on Mar. 9, 2009—pages.
J. Jetcheva, Y. Hu, D. Maltz, and D. Johnson, “A simple protocol for multicast and broadcast in mobile ad hoc networks,” Jul. 2001.
S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proc. of the 5th Ann. ACM/IEEE Int. Conf. on Mobile Comp. and Net., 1999, pp. 151-162.
R. Gandhi, S. Parthasarathy, and A. Mishra, “Minimizing broadcast latency and redundancy in ad hoc networks,” in Proceedings of the 4th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2003, 2003, pp. 222-232. http://www.sigmobile.org/mobihoc/2003/papers/p222-gandhi.pdf. Last accessed on Mar. 9, 2009, 11 pages.
S. C.-H. Huang, P.-J. Wan, C. T. Vu, Y. Li, and F. F. Yao, “Nearly constant approximation for data aggregation scheduling in wireless sensor networks,” in INFOCOM, 2007, pp. 366-372. http://www.cs.gsu.edu/˜cscysl/papers/infocom07.pdf. Last accessed on Mar. 9, 2009, 7 pages.
V. Annamalai, S. Gupta, and L. Schwiebert, “On tree-based convergecasting in wireless sensor networks,” in IEEE Wireless Communications and Networking, 2003. [Online]. Available: citeseer.ist.psu.edu/annamalai03treebased.html http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1200684&isnumber=27030. Last accessed on Mar. 9, 2009, 6 pages.
S. Huang, P. Wan, X. Jia, H. Du, and W. Shang, “Minimum-latency broadcast scheduling in wireless ad hoc networks,” in Proceedings of the 26th IEEE Interational Conference on Computer Communications, INFOCOM 2007, 2007, pp. 733-739. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4215673&isnumber=4215582. Last accessed on Mar. 9, 2009, 7.
H. Lim and C. Kim, “Multicast tree construction and flooding in wireless ad hoc networks,” in Proc. of the 3rd ACM Int. Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Sys, 2000, pp. 61-68. http://delivery.acm.org/10.1145/350000/346865/p61-lim.pdf?key1=346865&key2=4927066321&coll=GUIDE&dl=GUIDE&CFID=25927695&CFTOKEN=98922399. Last accessed.
W. Peng and X.-C. Lu, “On the reduction of broadcast redundancy in mobile adhoc networks,” in Proceedings of First Annual Workshop on Mobile Ad Hoc Networking Computing. MobiHOC, Aug. 11, 2000. http://delivery.acm.org/10.1145/520000/514171/p129-peng.pdf?key1=514171&key2=5767066321&coll=GUIDE&dl=GUIDE&CFID=25928371&CFTOKEN=64486354. Last accessed.
A. Qayyum, L. Viennot, and A. Laouiti, “Multipoint relaying: An efficient technique for flooding in mobile wireless networks,” INRIA, Tech. Rep. Research Report RR-3898, Feb. 2000. http://hal.inria.fr/docs/00/07/27/56/PDF/RR-3898.pdf. Last accessed on Mar. 9, 2009, 19 pages.
W. Peng and X. Lu, “Ahbp: An efficient broadcast protocol for mobile adhoc networks,” J. of Science and Tech.—Beijing, China, 2000.
J. Sucec and I. Marsic, “An efficient distributed network-wide broadcast algorithm for mobile adhoc networks,” Rutgers U., Tech. Rep., 2000. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.2683. Last accessed on Mar. 9, 2009, 11 pages.
W. Peng and X. Lu, “Efficient broadcast in mobile ad hoc networks using connected dominating sets,” J. Of Software—Beijing, China, 1999. www.jos.org.cn/ch/reader/download—pdf.aspx?file—no=20010407&year—id=2001&quarter—id=4&falg=1. Last accessed on Mar. 9, 2009, 8 pages.
I. Stojmenovic, M. Seddigh, and J. Zunic, “Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks,” IEEE Trans. on Parallel and Distributed Systems, pp. 14-25, Jan. 2002. http://ieeexplore.ieee.org/ielx5/71/21109/00980024.pdf?arnumber=980024. Last accessed on Mar. 9, 2009, 12 pages.
L. Orecchia, A. Panconesi, C. Petrioli, and A. Vitaletti, “Localized techniques for broadcasting in wireless sensor networks,” in DIALMPOMC '04: Proceedings of the 2004 joint workshop on Foundations of mobile computing, New York, NY, USA, 2004, pp. 41-45 1. http://www.eecs.berkeley.edu/˜orecchia/pubs/dialM.pdf. Last accessed on Mar. 9, 2009, 11 pages.
H. F. Salama, D. S. Reeves, and Y. Viniotis, “The delay-constrained minimum spanning tree problem,” in Second IEEE Symp. on Comp. and Comm. IEEE Computer Society, 1997, pp. 699-704. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=616089&isnumber=13414. Last accessed on Mar. 9, 2009, 5 pages.
I. Chlamtac and S. Kutten, “On broadcasting in radio networks—problem analysis and protocol design,” IEEE Trans. on Comm., vol. 33, No. 12, pp. 1240-1246, 1985. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1096245&isnumber=23991. Last accessed on Mar. 9, 2009, 7 pages.
Imrich Chilamtac and Shay Kutten, “Tree-based broadcasting in multihop radio networks,” IEEE Trans. on Comp., vol. 36, No. 10, pp. 1209-1223, 1987. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.8931. Last accessed on Mar. 9, 2009, 15 pages.
S. Basagni, I. Chlamtac, and D. Bruschi, “A mobility-transparent deterministic broadcast mechanism for ad hoc networks,” IEEE/ACM Trans. on Networking (TON), vol. 7, No. 6, pp. 799-807, 1999. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00811446. Last accessed on Mar. 9, 2009, 9 pages.
Z. Chen, C. Qiao, J. Xu, and T. Lee, “A constant approximation algorithm for interference aware broadcast in wireless networks,” in Proceedings of the 26th IEEE International Conference on Computer Communications, INFOCOM 2007, 2007, pp. 740-748. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4215674&isnumber=4215582. Last accessed on Mar. 9, 2009, 9.
P.-K. Hung, J.-P. Sheu, and C.-S. Hsu, “Scheduling of broadcasts in multihop wireless networks,” in European Wireless, 2002. http://www2.ing.unipi.it/ew2002/proceedings/086.pdf. Last accessed on Mar. 9, 2009, 7 pages.
B. Williams and T. Camp, “Comparison of broadcasting techniques for mobile ad hoc networks,” in Proc. of the 3rdACMInt. Symp. on Mobile Ad hoc Net. and Comp., 2002, pp. 194-205. http://www.cs.jhu.edu/˜dholmer/600.647/papers/Comparison%20of%20Broadcasting%20Techniques%20-%20Mobihoc%202002.pdf. Last accessed on Mar. 9, 2009, 16 pages.
P. Bateman and P. Erd..os, “Geometrical extrema suggested by a lemma of besicovitch,” The American Mathematical Monthly, pp. 306-314, May 1951.

Affiliated with

Also associated with

Rating

Broadcast latency optimization in multihop wireless networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Broadcast latency optimization in multihop wireless networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Broadcast latency optimization in multihop wireless networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2634603