靈敏混合自適應路由協定（Sharp Hybrid Adaptive Routing Protocol,SHARP）自動調整主動路由域大小和按需路由域大小，尋找主動式路由協定和反映式路由協定之間的平衡點。
基本介紹
- 中文名：靈敏混合自適應路由協定
- 外文名：Sharp Hybrid Adaptive Routing Protocol
- 外語縮寫：SHARP
- 類型：路由協定
SHARP概述,SHARP路由協定,主動路由組成部分,反應式路由組成部分,SHARP自適應,自適應機制,自適應策略,總結,
SHARP概述
SHARP在主動式路由策略和反應式路由策略之間高效、無縫的自適應。通過網路屬性驅動這種自適應，用於引導最佳化用戶定義的性能參數（例如丟失率、路由開銷、時延抖動）。
SHARP通過動態改變主動路由共享信息數量自適應主動式路由和反應式路由。SHARP圍繞一些節點定義主動域。一個特定節點的域半徑決定給主動域內的節點數量。距離小於或等於域半徑的每個節點成為該節點主動域的成員節點。不在給定目的節點主動域內的所有節點採用反應式路由協定建立到達該目的節點的路由。在主動域內使用節點特定的主動式路由協定。主動域內的節點只主動維護到達其中心節點的路由。
SHARP自動在熱點目的節點周圍建立主動域，熱點目的節點接收很多源節點的數據。一旦分組傳遞到達主動域外圍節點，那么主動域就立即接收分組，然後將其有效轉發給目的節點。維護所有源節與主動域中一個給定目的節點的通信路由，其維護開銷又SHARP逐步補償。因此，SHARP非常適用於在網路通信中表現出空間位置的套用。例如，在感測器網路中，經過精心選擇的一些節點進行數據累積，作為熱點目的節點，收集負極感測器產生的數據。
圖1-1表示一種典型展開的SHARP拓撲。SHARP維護以熱點目的節點A、B、C為中心的主動路由域。SHARP根據輸入數據流和移動性自動適應每個目的節點的域半徑。因此圍繞熱點目的節點建立相對較大的主動域，而圍繞流量甚小的節點建立相對較小的主動域。因此在圖1-1中，沒有數據流量或者數據流量甚小的節點D、E、F沒有主動域，只採用反應式路由。
圖1-1 SHARP主動域
圖1-1 SHARP主動域SHARP提供3個屬性：①自適應：SHARP能夠適應廣闊的網路特徵，在面對流量模式變化、節點移動，以及其他網路特徵時能夠自動調整期操作。②靈活性：SHARP能夠使套用最佳化不同的、套用特定的路由層性能。最佳化目標不是由網路設計者來設定，而是處於網路參與者控制之下。③高效而實用：SHARP的性能優於非混合的純路由策略，不需要調用高代價的低級原語（例如，分散式協商或可靠廣播）。
域半徑是每個目的節點主動式路由和反應式路由的混合控制按鈕。增大域半徑，則SHARP能夠降低分組丟失率和減輕時延抖動，但是路由維護開銷增大（因為域增大，要求主動更新的節點增多）。減小域半徑，則SHARP能夠降低路由開銷（因為域變小，要求主動更新的節點較少），但是可能時延抖動變大、分組丟失率增大。若將所有節點的域半徑設為零，則SHARP完全採用反應式路由協定；若將所有節點的域半徑設為大於或等於網路直徑，則SHARP完全採用主動式路由協定。
設計混合協定面臨的主要挑戰是如何確定各個混合成分的最佳組合。理想情況下，混合細腰應該對最佳組合實現紋理細密的控制，利用信息位置實現最大效率，自適應開銷低。
SHARP路由協定
SHARP由主動式路由協定和反應式路由協定組成。
主動路由組成部分
SHARP主動路由（SHARP Proactive Routing,SPR）協定是高效協定。可以借鑑TORA等路由技術來實現SPR。SPR在每個主動域中維護至其目的節點的路由，能夠利用低開銷機制建立和維護路由，具有若干良好特性（路由開銷可預測、數據分組丟失率低、分組到達時延變化小）。
SPR通過建立和維護定向非循環圖（Directed Acyclic Graph,DAG）來執行主動式路由，DAG的根部為目的節點。目的節點周期性初始化構建協定（Construction Protocol）,建立起DAG，並且將DAG限制在其主動域範圍內的節點。DAG重構周期為reconstruction_interval。在重構DAG之前，利用更新協定（Upadate Protocol）維護DAG。更新協定採用周期性更新交換機制和本地恢復機制來處理鏈路中斷問題。
構建協定用於周期性生成DAG。目的節點初始化產生一個DAG構建分組，初始化DAG構建進程。DAG構建分組包含域半徑、序列號、壽命（Time-To-Live,TTL）、高度（Height）等信息。域半徑和序列號用於識別新舊DAG。初始化時將TTL設為域半徑，並採用廣播方式將其傳輸給整個主動域。建立DAG，給每個節點分配一個高度值。高度用於路由，其初始值相當於節點與目的節點之間的距離。節點B接收到節點A傳送的DAG構建分組後，就地在DAG上增加A->B鏈，並將其高度加一，然後重新廣播這個DAG構建分組。一個節點可能接收到多個相鄰節點沿著不同鏈路轉發來的同一個DAG構建分組，此時存儲所有相鄰節點的高度信息，而將自己的高度設為所收高度中的最小值。
若採用簡單泛洪分發DAG構建分組，則會發生碰撞而引起分組丟失。為了避免廣播泛洪，每個節點等待一段隨機時延T後再重傳DAG構建分組。由於節點可能先接收到離目的節點較遠節點的DAG構建分組而後接收到離目的節點較近節點的DAG構建分組，因此在構建DAG時，存在不平衡問題。為了彌補這個不足，每個節點接收到第一個DAG構建分組後等待W秒，並在此期間收集所收的所有DAG構建分組，將其高度設為所收高度中的最小值，若TTL為正數則只轉發一個DAG構建分組。W秒之後到達的DAG構建分組不影響節點所選擇的高度值。儘管這個算法不能保證所有節點能檢測到至目的節點的最短距離，但是保守選擇W能確保DAG不會明顯偏離最佳DAG。更重要的是，每個節點每次最多轉發一個DAG構建分組，因此一個主動域中的DAG構建分組數量受到該域中節點數的限制。
更新協定用於傳送信標和維護DAG。主動域中每個節點以周期beacon_interval廣播一個更新分組，更新分組包含其當前高度值和TTL（設為1）。每個節點接收到其相鄰節點的更新分組後，存儲各個相鄰節點的高度。更新分組同時作為“hello”信標，用於檢測新鏈路的建立和當前鏈路的終端。若第一次接收到某個相鄰節點的更新分組，則認為與這個相鄰節點之間建立了一條新鏈路；若至少連續沒有接收到某個相鄰節點的beacon_loss個更新分組，則認為與這個相鄰節點之間的鏈路已經中斷。
更新協定採用TORA恢復機制回響鏈路中斷事件，恢復DAG。當連續丟失更新分組或者MAC層不能將數據分組傳送給某個相鄰節點時，則檢測出鏈路中斷。只有當一個節點的所有下行鏈路全部中斷後才調用中斷恢復機制。節點選擇一個新高度大於其相鄰節點的高度，初始化一個新的更新分組，從而將其上行鏈路方向反轉。採用基於TORA的中斷恢復機制提供三個特性：①使SPR能夠在主動域中從鏈路中斷中恢復DAG，而不必等到下一次重構DAG；②將鏈路中斷的影響限制在本地小範圍內；③SPR可預測開銷低，從而使得分析模型易於處理。需要注意的是，由於不再知道至目的節點的確切距離，因此進行本地恢復可能會誤用DAG的最優性。這個問題對TORA的性能有明顯影響。SHARP利用構建協定彌補這個問題，構建協定周期性從頭開始重構DAG。因此，SPR的DAG在大部分時間包含相對較短的至目的節點的路徑。
SPR按照如下方法執行數據分組的傳輸路由。一個節點接收到一個數據分組後，沿著下行鏈路將其傳送給高度最小的相鄰節點。若由於鏈路中斷而使得數據分組無法傳送給高度最小的相鄰節點，則將數據分組傳送給下一個最佳相鄰節點。以此類推。若所有下行鏈路已經中斷，則將鏈路反轉。恢復DAG，然後將數據分組轉發給新的最佳下行節點。若數據分組比更新分組先傳遞到達新的下行節點，則會發生短暫路由閉環。為了防止發生這個問題，利用數據分組攜帶該節點的新高度信息，這樣下行節點在轉發數據分組前就能夠更新新高度。
多徑路由、本地鏈路恢復、構建協定使得SPR是一個強壯而高效的路由協定，分組丟失率低，可預測開銷低。
反應式路由組成部分
SHARP無縫綜合主動式路由和反應式路由，沒有額外開銷。若源節點位於主動域內，則執行主動式路由；若源節點位於主動域外，則利用AODV廣播路由請求。目的節點主動域內的節點回響源節點的路由請求，做出路由應答。主動域內的應答節點將至目的節點的距離設為零。因此，主動域有效作為源節點數據分組的集合目的地。數據分組進入主動域後立即按照主動式路由來傳遞。按需維護源節點和主動域邊界節點之間的路由。
總之，SHARP是一個通用的路由協定混合體系架構，可以使用主動式路由和反應式路由的任意組合，其開銷分析易控制。
SHARP自適應
SHARP通過動態調整整個目的節點的主動域半徑來控制路由協定的性能。每個目的節點根據網路特點（例如，移動速率、節點密度）和數據流特徵（例如，源節點數量、源節點與目的節點之間的距離）改變其主動域的大小。每個目的節點就地獨立做出改變其當前主動域大小的決策，與其他目的節點無關。因此，SHARP能夠控制不同套用的性能參數（例如，路由開銷、分組丟失率、時延抖動），不同網路節點能夠同時最佳化不同的性能參數。
自適應機制
為了進行高效操作和頻繁自適應，SHARP需要網路監視機制和主動域半徑更改機制，特別是需要低級網路特點（例如，平均鏈路壽命、平均節點密度）估計機制和流量特徵（例如，分組丟失率、時延抖動）估計機制，需要主動域半徑信息高效傳播機制和基於各種性能和分析模型的主動域更改機制。
SHARP節點連續不停地監視網路特點。特別是主動域內節點測試和維護其直接鏈路的平均鏈路壽命，測試平均節點密度（即直接相鄰節點的數量），累積所測得的和從其他上行節點接收到的平均鏈路壽命和平均節點密度（這是更新協定的一個組成部分），周期性利用更新分組廣播累積結果。在正更新過程中組合累積結果，不考慮重複計數的數據，直到其傳遞到達DAG中心的目的節點為止。
自適應策略
SHARP採用前述高效機制動態管理主動式路由和反應式路由之間的綜合平衡。SHARP提供一個通用體系架構，可用於實現不同的套用特定目標。下面介紹利用SHARP通用體系架構來實現最低分組開銷、有限分組丟失率、可控時延抖動三個目標。
1、 最低分組開銷（SHARP-PO）
路由開銷是選擇路由協定時的一個重要考慮問題。在移動環境中，節點通常依靠電池供電，因此通信開銷過高的路由算法會大大縮短系統的壽命。
為此，以SHARP主動式路由和反應式路由之間的綜合平衡為基礎，自適應主動域半徑，以降低路由開銷。SHARP主動路由開銷與源節點數量無關，因此在多個源節點給同一個目的節點傳送數據分組的過程中能夠逐步得到補償。由於SPR就地恢復中斷路由，所以SHARP主動路由開銷很大程度上與移動速率無關。而反應式路由協定的開銷與源節點數量和移動速率密切相關。隨著網路移動性的增強，反應式路由協定不得不以更高的總開銷尋找路由。因此，依據網路參數的瞬時值，並選擇一種路由體制，存在最佳化機會。
以SHARP自適應體系架構為基礎最佳化每個分組的路由算法開銷。SHARP-PO(SHARP-Packet Overhead)協定在可預測高開銷SPR協定與AODV可變開銷之間進行動態自適應，以找出路由開銷的最佳組合。SHARP-PO協定的目標是動態尋找主動域半徑、最佳化總路由開銷。根據前述分析模型，SHARP能夠按照路由開銷量化主動式路由和反應式路由之間的平衡。
2、 有限丟失率（SHARP-LR）
分組丟失率是網路層路由協定的一個重要參數。高層協定（如TCP）對底層分組丟失非常敏感。路由協定分組丟失率高，則TCP吞吐量會大幅度下降。其他套用（如壓縮視頻）相對能夠容忍低分組丟失率。
在主動式路由和反應式路由之間存在基本的開銷和可靠性的綜合平衡。SPR總是維護指向目的節點的DAG，DAG中存在多條冗餘路徑，因此SPR在回響鏈路中斷時能夠迅速找到其他路由，所以分組丟失率低。反應式路由檢測鏈路中斷相對緩慢：只有當嘗試傳送數據分組時，在中斷鏈路處理遇到分組丟失後才會檢測出鏈路中斷問題。節點低速移動時，反應式路由協定分組丟失率低且開銷低，而主動式路由協定開銷總是恆定的。據此得到一個自適應策略，選擇最小限度的、大小足夠的主動域半徑，既保證預定的分組丟失率性能，同時又不會引入過高的控制開銷。
利用套用特定的路由協定SHARP-LR（SHARP-Loss Rate）實現用戶規定的目標分組丟失率，同時使分組開銷最低。SHARP-LR回響目的節點檢測到的分組丟失事件（作為自適應驅動因素）時調整主動域大小：如所檢測到的分組丟失率是規定分組丟失率的up_thresh倍以上，則將主動域半徑加1；若所檢測到的分組丟失率是規定分組丟失率的down_thresh倍以下，則將主動域半徑減1.然後根據所選擇的主動域半徑值擴大或者縮小主動域。因此所發生的分組丟失率不會大於規定的分組丟失率。
3、 時延抖動可控（SHARP-DJ）
時延抖動（兩個連續分組之間到達間隔時間的變化）是許多實時套用的重要性能參數。例如，周期性傳送感測器感知數據的套用（如目標跟蹤）和多媒體套用（非壓縮語音）對分組到達間隔時間的變化非常敏感。
在各種網路條件下，需要折衷考慮主動式路由協定和反應式路由協定的路由開銷和時延。SPR在高速行動網路中的時延變化小；反應式路由協定在發生路由中斷後重構路由，引起數據流傳輸短暫中斷，因此頻繁的路由中斷導致時延抖動增強。在低速移動條件下，反應式路由協定以極低開銷提供所需要的時延抖動性能。由此得到一種自適應策略，利用這些折衷考慮，以低開銷提供各種網路條件下的良好時延抖動性能。
SHARP-DJ（SHARP-Delay Jitter）協定就是以最低開銷實現套用特定的時延抖動，其目標是選擇最小限度的、大小足夠的主動域半徑，既保證預定的時延抖動性能，同時又不會引入過高的控制開銷。SHARP-DJ採用類似於SHARP-LR的方法改變主動域大小：目的節點跟蹤所收數據分組的到達間隔時間；若所檢測到的時延抖動是規定時延抖動的up_thresh倍以上，則將主動域半徑加1；若所檢測到的時延抖動是規定時延抖動的down_thresh倍以下，則將主動域半徑減1。
總結
在反應式路由協定和主動式路由協定之間存在基本的折衷平衡，不存在適用於甚寬網路條件的固定路由策略（不論是主動式路由協定，還是反應式路由協定）。這種基本折衷平衡迫使我們需要基於網路條件的動態自適應協定。SHARP動態尋找主動式路由協定和反應式路由協定之的可行平衡點，其在網路條件變化下的性能均優於主動式路由協定和反應式路由協定，能夠使網路中多個節點同時最佳化路由層不同的特定套用性能參數。
