Telecommunications – Radiotelephone system – Zoned or cellular telephone system
Reexamination Certificate
2008-11-18
2010-12-28
Appiah, Charles N (Department: 2617)
Telecommunications
Radiotelephone system
Zoned or cellular telephone system
C455S423000, C455S450000, C455S063100, C455S067130, C370S238000, C370S252000, C370S328000, C370S338000, C370S351000
Reexamination Certificate
active
07860506
ABSTRACT:
Disclosed is a general model and method for computing performance bounds in multi-hop wireless networks. Rather than focusing on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, the present invention accommodates any given network, technology, interference model, routing paradigm, and workload. Using a conflict graph to formally characterize the impact of wireless interference on the performance of multi-hop wireless networks, methods for computing upper and lower bounds on the capacity of a given wireless network are detailed. Besides computing network capacity, the model and method disclosed can also enable or benefit other applications including maximizing fairness and minimizing maximum link utilization.
REFERENCES:
patent: 5365571 (1994-11-01), Rha et al.
patent: 5524136 (1996-06-01), Bar-Noy et al.
patent: 6377544 (2002-04-01), Muthukrishnan et al.
patent: 6377551 (2002-04-01), Luo et al.
patent: 6522885 (2003-02-01), Tang et al.
patent: 6542746 (2003-04-01), Dean
patent: 6614762 (2003-09-01), Illiadis et al.
patent: 6631267 (2003-10-01), Clarkson et al.
patent: 6643277 (2003-11-01), Garrison et al.
patent: 6646989 (2003-11-01), Khotimsky et al.
patent: 6771966 (2004-08-01), Chow
patent: 6816585 (2004-11-01), Blatt et al.
patent: 6829216 (2004-12-01), Nakata
patent: 6836467 (2004-12-01), Stanley
patent: 6950418 (2005-09-01), Young et al.
patent: 7251224 (2007-07-01), Ades et al.
patent: 7469143 (2008-12-01), Jain et al.
patent: 2005/0058111 (2005-03-01), Hung et al.
patent: 2006/0240835 (2006-10-01), Jain et al.
Sengoku et al., Cellular Mobile Communication Systems and a Channel assignment using Neural Networks, Aug. 12-14, 1990, Circuits and Systems, 1990, Proceedings of the 33rdMidwest Symposium on, pp. 411-414, ISBN: 0-7803-0081-5.
Bay area wireless users group, http://www.bawug.org.
lp—solve: linear programming code., ftp://ftp.ics.ele.tue.nl/pub/lp—solve/.
Linear Programming. W.H. Freeman and Company, 1983. [book].
De Couto et al.,Performance of Mutlihop Wireless Networks; Shortest Path is Not Enough. MIT Laboratory for Computer Science, 1stWorkshop on Hot Topics in Networks (Oct. 2002), http://www.pdos.lcs.mit.edu/papers/grid:hotnets02/paper.pdf.
Ilog cplex suite, 2003, http://www.ilog.corn/products/cplex/.
Estrin et al.,Next Century Challenges: Scalable Coordination in Sensor Networks, ACM MOBICOM (Aug. 1999). http://citeseer.nj.nec.com/estrin99next.html.
Garey, et al.,Computers and Intractability: A guide to the theory of {NP} completeness. W.H. Freeman and Company, (1979) [book].
Gastpar et al.,On The Capacity of Wireless Networks: The Relay Case, IEEE INFOCOM (Jun. 2002). http://www.ieee-infocom.org/2002/papers/489,pdf.
Grossglauser et al.,Mobility Increases The Capacity Of Ad-Hoc Wireless Networks, IEEE INFOCOM (Apr. 2001), http://citeseer.nj.nec.com/532243.html.
Gupta et al.,The Capacity Of Wireless Networks, IEEE Transactions on Information Theory 46, 2 (Mar. 2000). http://citeseersii.nec.com/gupta99capacitv.html.
Johnson et al.,Dynamic Source Routing In Ad-Hoc Wireless Networks, Mobile Computing (1996), Imielinski et al., Eds., Kluwer Academic Publishers, http://citeseer.nj.nec.com/johnson96dynamic.html.
Kodialam et al.,Characterizing Achievable Rates In Multi-Hop Wireless Networks: The Joint Routing And Scheduling Problem, ACM MOBICOM (Sep. 2003).
Li et al.,Capacity Of Ad Hoc Wireless Networks, ACM MOBICOM, (Jul. 2001). http://citeseer.nj.nec.com/1i01capacity.html.
Matlab version6.1. http://www.matlab.com/.
Nandagopal et al., Achieving MAC Layer Fairness In Wireless Packet Networks, ACM MOBICOM, (Aug. 2000). http://citeseer.nj.nec.com
andagopal00achieving.html.
The Network Simulator—ns-2, (1995) http://www-mash.cs.berkeley.edu
s/.
Park et at,A Highly Adaptive Distributed Routing Algorithm For Mobile Wireless Networks, Proc. Of IEEE Infocom'97, (Apr. 1997) http://citeseer.ni.nec.com/park97highly.html.
Perkins et al.,Highly Dynamic Destination-Sequenced Distance Vector Routing(DSDV)For Mobile Computers, Proc. of ACM SIGCOMM'94, (Sep. 1994). http://citeseer.nj.nec.corn/perkins94highly.html.
Perkins et al.,Ad-Hoc On-Demand Distance Vector Routing, Proc. of IEEE WMCSA '99 (Feb. 1999). http://citeseer.nj.nec.com/549597.html.
Seattle wireless, http://www.seattlewireless.net/.
Yang, et al.,Priority Scheduling In Wireless Ad Hoc Networks, In ACM MobiHoc, (Jun. 2002).
Jain Kamal
Padhye Jitendra D.
Padmanabhan Venkata N.
Qiu Lili
Ajibade Akonai Olumide T
Appiah Charles N
Microsoft Corporation
Wolf Greenfield & Sacks P.C.
LandOfFree
Model and method for computing performance bounds in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Model and method for computing performance bounds in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Model and method for computing performance bounds in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4181789