貪婪轉(zhuǎn)發(fā)
1.局部最優(yōu)選擇
在貪婪周邊無狀態(tài)路由協(xié)議GPSR中，源節(jié)點(diǎn)在發(fā)起數(shù)據(jù)包發(fā)送的時(shí)候拆又，在數(shù)據(jù)包上標(biāo)識(shí)了目的節(jié)點(diǎn)的位置儒旬。在節(jié)點(diǎn)需要轉(zhuǎn)發(fā)數(shù)據(jù)包，而需要選擇下一跳節(jié)點(diǎn)的時(shí)候帖族，作出局部最優(yōu)的貪婪選擇栈源。具體而言，因?yàn)楣?jié)點(diǎn)保存了所有一跳鄰節(jié)點(diǎn)的位置竖般，則在路由表中選擇距離目的節(jié)點(diǎn)最近的鄰節(jié)點(diǎn)作為局部最優(yōu)選擇甚垦，此鄰節(jié)點(diǎn)成為轉(zhuǎn)發(fā)數(shù)據(jù)包的下一跳節(jié)點(diǎn)。遵循尋找局部最優(yōu)選擇的這一方法涣雕，一直到數(shù)據(jù)包送抵目的位置艰亮。
?如圖一所示，圖中節(jié)點(diǎn)x需要轉(zhuǎn)發(fā)目的節(jié)點(diǎn)為D的數(shù)據(jù)包挣郭，節(jié)點(diǎn)X為圓心的虛線圓圈則代表節(jié)點(diǎn)x的通訊范圍迄埃。因?yàn)楣?jié)點(diǎn)y到節(jié)點(diǎn)D的距離，是在節(jié)點(diǎn)X的所有一跳鄰節(jié)點(diǎn)中離節(jié)點(diǎn)D的距離最小的兑障，所以在節(jié)點(diǎn)X向目的節(jié)點(diǎn)D轉(zhuǎn)發(fā)數(shù)據(jù)包的貪婪轉(zhuǎn)發(fā)過程中侄非，節(jié)點(diǎn)Y成為下一跳路由的局部最優(yōu)選擇伶棒。節(jié)點(diǎn)y會(huì)作為節(jié)點(diǎn)x向目的節(jié)點(diǎn)D轉(zhuǎn)發(fā)數(shù)據(jù)包的下一跳節(jié)點(diǎn)。這個(gè)過程隨著數(shù)據(jù)包不斷被轉(zhuǎn)發(fā)下去會(huì)被一直持續(xù)彩库，直到數(shù)據(jù)包到達(dá)節(jié)點(diǎn)D。
貪婪轉(zhuǎn)發(fā)的最大優(yōu)勢(shì)是先蒋，只需要保存節(jié)點(diǎn)的一跳鄰居的信息骇钦。網(wǎng)絡(luò)狀態(tài)（繁忙程度、到達(dá)率等等）由網(wǎng)絡(luò)中的節(jié)點(diǎn)密度決定竞漾，而不是網(wǎng)絡(luò)規(guī)模
這與按需（后置式）路由協(xié)議不一樣眯搭。通常，在一個(gè)使用多跳路由的網(wǎng)絡(luò)业岁，一個(gè)節(jié)點(diǎn)的無線范圍內(nèi)的鄰居的數(shù)目基本上遠(yuǎn)遠(yuǎn)低于在網(wǎng)絡(luò)中的節(jié)點(diǎn)的總數(shù)鳞仙。
2. 貪婪轉(zhuǎn)發(fā)的困境
只使用一跳鄰節(jié)點(diǎn)位置的貪婪轉(zhuǎn)發(fā)，會(huì)帶來一個(gè)天生的問題笔时。如圖二所示：節(jié)點(diǎn)x離目的節(jié)點(diǎn)D的距離棍好，比節(jié)點(diǎn)w和節(jié)點(diǎn)y距離目的節(jié)點(diǎn)D的距離都要更近。從路由節(jié)點(diǎn)X轉(zhuǎn)發(fā)數(shù)據(jù)包到目的節(jié)點(diǎn)D允耿，存在兩條路徑：X→y→z→D和X→w→v→D借笙。可是由于貪婪轉(zhuǎn)發(fā)的策略较锡，節(jié)點(diǎn)x比所有其它一跳鄰節(jié)點(diǎn)都接近目的節(jié)點(diǎn)D业稼，x是轉(zhuǎn)發(fā)數(shù)據(jù)包的局部最優(yōu)節(jié)點(diǎn)。在貪婪轉(zhuǎn)發(fā)里蚂蕴，節(jié)點(diǎn)x不會(huì)轉(zhuǎn)發(fā)數(shù)據(jù)包給節(jié)點(diǎn)y或節(jié)點(diǎn)w低散。
?這就是貪婪轉(zhuǎn)發(fā)所面臨的困境：存在一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，向目的節(jié)點(diǎn)數(shù)據(jù)包的過程中骡楼，需要選擇距離目的節(jié)點(diǎn)非最近的節(jié)點(diǎn)作為下一跳路由熔号。這種情況稱作為路由空洞現(xiàn)象。
?遇到路由空洞的時(shí)候鸟整，將由周邊轉(zhuǎn)發(fā)模式來處理這種情況跨嘉。
