78:. Greedy forwarding tries to bring the message closer to the destination in each step using only local information. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view. The most suitable neighbor can be the one who minimizes the distance to the destination in each step (Greedy). Alternatively, one can consider another notion of progress, namely the projected distance on the source-destination-line (MFR, NFP), or the minimum angle between neighbor and destination (Compass Routing). Not all of these strategies are loop-free, i.e. a message can circulate among nodes in a certain constellation. It is known that the basic greedy strategy and MFR are loop free, while NFP and Compass Routing are not.
87:
100:
113:
message can be delivered to the destination. The combination of greedy forwarding and face routing was first proposed in 1999 under the name GFG (Greedy-Face-Greedy). It guarantees delivery in the so-called unit disk graph network model. Various variants, which were proposed later , also for non-unit disk graphs, are based on the principles of GFG .
112:
Greedy forwarding can lead into a dead end, where there is no neighbor closer to the destination. Then, face routing helps to recover from that situation and find a path to another node, where greedy forwarding can be resumed. A recovery strategy such as face routing is necessary to assure that a
124:
Although originally developed as a routing scheme that uses the physical positions of each node, geographic routing algorithms have also been applied to networks in which each node is associated with a point in a virtual space, unrelated to its physical position. The process of finding a set of
92:
Greedy forwarding variants: The source node (S) has different choices to find a relay node for further forwarding a message to the destination (D). A = Nearest with
Forwarding Progress (NFP), B = Most Forwarding progress within Radius (MFR), C = Compass Routing, E =
105:
Face routing: A message is routed along the interior of the faces of the communication graph, with face changes at the edges crossing the S-D-line (red). The final routing path is shown in blue.
54:
can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the
116:
Face routing depends on a planar subgraph in general; however distributed planarization is difficult for real wireless sensor networks and does not scale well to 3D environments.
50:
networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each
224:
278:
Stojmenovic, Ivan; Lin, Xu (2001). "Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks".
351:
Djenouri, Djamel; Balasingham, Ilangko (2011). "Traffic-Differentiation-Based
Modular QoS Localized Routing for Wireless Sensor Networks".
125:
virtual positions for the nodes of a network such that geographic routing using these positions is guaranteed to succeed is called
138:
328:
Proc. of the 3rd international workshop on discrete algorithms and methods for mobile computing and communications (DIALM '99)
167:
42:
and based on the idea that the source sends a message to the geographic location of the destination instead of using the
466:
456:
186:
Takagi, H.; Kleinrock, L. (March 1984). "Optimal transmission ranges for randomly distributed packet radio terminals".
461:
451:
418:
287:
250:
195:
323:
143:
292:
200:
35:
255:
368:
67:
175:. Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols. Bentham Science.
51:
399:
360:
331:
297:
260:
205:
126:
86:
55:
39:
387:
70:-based strategies (see for a survey). Most single-path strategies rely on two techniques:
43:
99:
445:
422:
391:
372:
47:
426:
264:
209:
403:
319:
225:"Routing and Addressing Problems in Large Metropolitan-Scale Internetworks"
336:
396:
Proceedings of the 2005 Joint
Workshop on Foundations of Mobile Computing
364:
315:
326:(1999). "Routing with guaranteed delivery in ad hoc wireless networks".
241:
Stojmenovic, Ivan (2002). "Position based routing in ad hoc networks".
31:
301:
66:
There are various approaches, such as single-path, multi-path and
429:(2003), "Geographic routing without location information",
431:
Proc. 9th ACM Mobile
Computing and Networking (MobiCom)
394:(2005). "On the Pitfalls of Geographic Face Routing".
280:
IEEE Transactions on
Parallel and Distributed Systems
230:. University of Southern California, ISI/RR-87-180.
166:Ruehrup, Stefan (2009). Liu; Chu; Leung (eds.).
8:
335:
291:
254:
199:
169:Theory and Practice of Geographic Routing
161:
159:
16:Routing methodology for wireless networks
155:
38:information. It is mainly proposed for
353:IEEE Transactions on Mobile Computing
7:
188:IEEE Transactions on Communications
14:
417:Rao, Ananth; Ratnasamy, Sylvia;
139:List of ad hoc routing protocols
98:
85:
223:Finn, Gregory G. (March 1987).
1:
243:IEEE Communications Magazine
58:or a prior route discovery.
483:
419:Papadimitriou, Christos H.
265:10.1109/MCOM.2002.1018018
210:10.1109/TCOM.1984.1096061
34:principle that relies on
404:10.1145/1080810.1080818
28:position-based routing
337:10.1145/313239.313282
365:10.1109/TMC.2010.212
144:Backpressure Routing
467:Geographic position
457:Wireless networking
322:; Stojmenovic, I.;
36:geographic position
462:Routing algorithms
398:. pp. 34–43.
330:. pp. 48–55.
20:Geographic routing
452:Routing protocols
433:, pp. 96–108
302:10.1109/71.963415
286:(10): 1023–1032.
72:greedy forwarding
46:. In the area of
40:wireless networks
474:
436:
434:
414:
408:
407:
383:
377:
376:
348:
342:
341:
339:
312:
306:
305:
295:
275:
269:
268:
258:
238:
232:
231:
229:
220:
214:
213:
203:
183:
177:
176:
174:
163:
127:greedy embedding
120:Greedy embedding
102:
89:
56:network topology
482:
481:
477:
476:
475:
473:
472:
471:
442:
441:
440:
439:
416:
415:
411:
390:; Karp, Brad.;
388:Ramesh Govindan
385:
384:
380:
350:
349:
345:
314:
313:
309:
277:
276:
272:
240:
239:
235:
227:
222:
221:
217:
185:
184:
180:
172:
165:
164:
157:
152:
135:
122:
110:
109:
108:
107:
106:
103:
95:
94:
90:
64:
44:network address
17:
12:
11:
5:
480:
478:
470:
469:
464:
459:
454:
444:
443:
438:
437:
423:Shenker, Scott
409:
378:
359:(6): 797–809.
343:
307:
293:10.1.1.67.7527
270:
249:(7): 128–134.
233:
215:
201:10.1.1.64.9747
194:(3): 246–257.
178:
154:
153:
151:
148:
147:
146:
141:
134:
131:
121:
118:
104:
97:
96:
91:
84:
83:
82:
81:
80:
63:
60:
15:
13:
10:
9:
6:
4:
3:
2:
479:
468:
465:
463:
460:
458:
455:
453:
450:
449:
447:
432:
428:
424:
420:
413:
410:
405:
401:
397:
393:
392:Scott Shenker
389:
382:
379:
374:
370:
366:
362:
358:
354:
347:
344:
338:
333:
329:
325:
321:
317:
311:
308:
303:
299:
294:
289:
285:
281:
274:
271:
266:
262:
257:
256:10.1.1.6.6012
252:
248:
244:
237:
234:
226:
219:
216:
211:
207:
202:
197:
193:
189:
182:
179:
171:
170:
162:
160:
156:
149:
145:
142:
140:
137:
136:
132:
130:
128:
119:
117:
114:
101:
88:
79:
77:
73:
69:
61:
59:
57:
53:
49:
45:
41:
37:
33:
29:
25:
22:(also called
21:
430:
412:
395:
381:
356:
352:
346:
327:
310:
283:
279:
273:
246:
242:
236:
218:
191:
187:
181:
168:
123:
115:
111:
76:face routing
75:
71:
65:
48:packet radio
27:
23:
19:
18:
427:Stoica, Ion
324:Urrutia, J.
446:Categories
150:References
62:Approaches
24:georouting
320:Morin, P.
288:CiteSeerX
251:CiteSeerX
196:CiteSeerX
386:Kim, Y;
373:11139687
316:Bose, P.
133:See also
68:flooding
32:routing
30:) is a
371:
290:
253:
198:
93:Greedy
369:S2CID
228:(PDF)
173:(PDF)
74:and
52:node
400:doi
361:doi
332:doi
298:doi
261:doi
206:doi
26:or
448::
425:;
421:;
367:.
357:10
355:.
318:;
296:.
284:12
282:.
259:.
247:40
245:.
204:.
192:32
190:.
158:^
129:.
435:.
406:.
402::
375:.
363::
340:.
334::
304:.
300::
267:.
263::
212:.
208::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
