Reporter: Wu, Cheng-Xuan Teacher： Horng, Gwo-Jiun

Presentation on theme: "Reporter: Wu, Cheng-Xuan Teacher： Horng, Gwo-Jiun"— Presentation transcript:

1 Reporter: Wu, Cheng-Xuan Teacher： Horng, Gwo-Jiun
An Efficient Cost-based Location Service Protocol for Vehicular Ad Hoc Networks Chih-Shun Hsu, Shen-Wen Wu, Department of Info. Management Shih Hsin University Reporter: Wu, Cheng-Xuan Teacher： Horng, Gwo-Jiun

2 Outline Introduction Research Situation Preliminaries
Cost-based Location Service Protocol Simulation Results Conclusions 改善方法

3 1. Introduction Vehicular ad hoc networks (VANETs) have attracted lots of attentions recently. How to provide efficient location services has become an important issue in VANETs.

4 When location servers with densely deployed:
It has lower cost of location query, but higher cost of location update. When location servers with sparsely deployed: It has lower cost of location update, but higher cost of location query. That generated a question: How to deploy proper number of location servers at proper locations, to reduce the total cost of location update and query ?

5 2. Research Situation Many location service protocols have been proposed: Hierarchical location service divided to hexagonal cells. (level, cluster head) Salable quorum-based location service location packets transmitted along node’s quorum. Cache-based routing protocol exchange information with neighborhood at intersection. Map-based vehicle location service 𝑀𝑥𝑁 grid, each grid contains a LS, communicate with coordinate.

6 Existing location service protocols are either incurring high location update costs or long location query delay. We propose a novel location service protocol which tries to achieve the lowest total cost of location update and query by deploying proper number of location servers at proper locations to improve existing works,

7 3. Preliminaries A. System Model B. Motivations and Contributions

8 A. System Model This protocol is designed for VANETs in city environment. Each vehicle has a GPS, an electronic map, and a wireless transceiver. To get own location: from own GPS and send the location update packet to LS. To get other vehicle’s location: from the location servers through V2V or V2R communications. The communication is based on IEEE p protocol.

9

10 LLS LLS DLS DLS Flow of Packet Location query Location update packet
If no information of queried Forwarded to nearest DLS DLS

11 B. Motivations and Contributions
Three mechanisms must be considered when designed : (1) namely the delegation of location servers. (2) location update mechanisms. (3) location query mechanisms. Existing location service protocols are either incurring high location update costs or long location query delay. In this paper the cost functions of the location service protocol are defined.

12 4. Cost-based Location Service Protocol
A. Cost Functions B. Deployment of Location Servers C. Location Update Mechanism

13 A. Cost Functions 𝑚 𝑘 𝑑 𝑢𝑝𝑑𝑎𝑡𝑒
Average cost of location update for m different cases: , = 𝑖=1 𝑚 + /𝑚 𝑢 𝑙𝑖 𝑢 𝑡𝑖𝑘 𝐶 𝑢𝑝𝑑𝑎𝑡𝑒 𝑚 𝑘 𝑑 𝑢𝑝𝑑𝑎𝑡𝑒 𝑟 𝑟 𝐶𝑢𝑝𝑑𝑎𝑡𝑒: Average cost of a location update. 𝑘: Number of dedicated location servers in each group. 𝑟: Communication range of a vehicle. 𝑢𝑙𝑖: Path length of the i-th update from the updating vehicle to the LLS. 𝑢𝑡𝑖𝑘: Total edge length of the minimum spanning tree (connects the local and k DLS.) 𝑑𝑢𝑝𝑑𝑎𝑡𝑒: Packet size of an update packet.

14 Average cost of location query for n different cases:
𝑛, = 𝑖=1 𝑛 − ( )/𝑛 𝑞 𝑙𝑖 𝑞 𝑑𝑖 𝑞 𝑙𝑖 𝐶 𝑞𝑢𝑒𝑟𝑦 𝑝𝑙 𝑝𝑙 𝑑 𝑞𝑢𝑒𝑟𝑦 𝑑 𝑟𝑒𝑝𝑙𝑦 𝑟 𝑟 𝑟 𝐶𝑞𝑢𝑒𝑟𝑦: Average cost of a location query. 𝑝𝑙: Probability that the queried vehicle’s location can be got from the LLS. 𝑟: Communication range of a vehicle. 𝑞𝑙𝑖: Path length of the i-th query from the querying vehicle to the LLS. 𝑞𝑑𝑖: Path length of the i-th query from the LLS to the nearest DLS. 𝑑𝑞𝑢𝑒𝑟𝑦: Packet size of an query packet. 𝑑𝑟𝑒𝑝𝑙𝑦: Packet size of an reply packet.

15 𝑘 𝑝𝑙 𝐶 𝑢𝑝𝑑𝑎𝑡𝑒 𝑘 𝑓 𝑢𝑝𝑑𝑎𝑡𝑒 𝐶 𝑞𝑢𝑒𝑟𝑦 𝑝𝑙 𝑓 𝑞𝑢𝑒𝑟𝑦
Total cost of location update and query: 𝐶 𝑡𝑜𝑡𝑎𝑙 𝑚,𝑛, , = 𝑚, 𝑛, 𝑘 𝑝𝑙 𝐶 𝑢𝑝𝑑𝑎𝑡𝑒 𝑘 𝑓 𝑢𝑝𝑑𝑎𝑡𝑒 𝐶 𝑞𝑢𝑒𝑟𝑦 𝑝𝑙 𝑓 𝑞𝑢𝑒𝑟𝑦 𝑘: Number of dedicated location servers in each group. 𝑝𝑙: Probability that the queried vehicle’s location can be got from the LLS. 𝐶𝑢𝑝𝑑𝑎𝑡𝑒: Average cost of a location update. 𝐶𝑞𝑢𝑒𝑟𝑦: Average cost of a location query. 𝑓𝑢𝑝𝑑𝑎𝑡𝑒: Frequency of location update . 𝑓𝑞𝑢𝑒𝑟𝑦: Frequency of location query.

16 We can find that the cost of location update and query is greatly affected by the number and location of location servers. To reduce the total cost of location update and query, should try to reduce the frequency of location update and query.

17 B. Deployment of Location Servers
Assume： 𝑛 level 2 grids in the service area. a LS in each level 2 grid. 𝑘 DLS (where k ≤ n) 𝑘 DLS and a LLS which record the location information of a vehicle. n location servers can be divided into 𝒏 𝒌 group. each group contains k location servers. Dedicated location servers, use vehicle id to decide. 𝐷𝐿𝑆 𝐺𝑟𝑜𝑢𝑝 𝑖=(𝑣𝑒ℎ𝑖𝑐𝑙𝑒 𝑖𝑑) 𝑚𝑜𝑑 𝑛 𝑘 +1

18 Example

19 The cost functions can be used to decide the number and the grouping of DLS so as to achieve the lowest total cost of location update and query. The deployment of dedicated location servers works as follows. Generate all the possible groupings. each group contains k location servers, where 1 ≤ k ≤ n. Calculate the total cost for each grouping. For each k, find the grouping with the minimum total cost. From all possible k, output the k and its grouping whose total cost is minimum.

20 Every vehicle sends a location query (𝒇𝒒𝒖𝒆𝒓𝒚)
Every vehicle sends a location query (𝒇𝒒𝒖𝒆𝒓𝒚) and update packets (𝒇𝒖𝒑𝒅𝒂𝒕𝒆) times per minute. Every vehicle sends the same amount of update packets, the average location update cost are the same. The average query cost from left to right are 154 bytes, 114 bytes, bytes. The rightmost grouping is the cost-less group.

21 Assume: 𝑓 𝑢𝑝𝑑𝑎𝑡𝑒 =1, 𝑓𝑞𝑢𝑒𝑟𝑦 = 4, 𝑝𝑙= 1 9 , 𝑑𝑢𝑝𝑑𝑎𝑡𝑒 = 𝑑𝑞𝑢𝑒𝑟𝑦 = 𝑑𝑟𝑒𝑝𝑙𝑦 = 20 𝑏𝑦𝑡𝑒𝑠 we can calculate total cost of location update and query for different k. Number of LS in each group Update cost Query Total 2 250.6 bytes 147.6 bytes 841.0 bytes 3 371.8 bytes 112.4 bytes 821.4 bytes 4 506.6 bytes 90.8 bytes 869.8 bytes

22 C. Location Update Mechanism
Location update packet is transmitting to the LLS and DLS along the minimum spanning tree. location update packet : location information moving speed moving direction of the vehicle moving path location of the destination

23 To reduce the total cost of location update, reduce the frequency of location update is a possible approach. Moving patterns of vehicles are more predictable. Vehicle should send its location update packet: Changed its moving direction. Does not follow the planned.

24 D. Location Query Mechanism
packet The DLS of the queried vehicle can be found by the id of the queried vehicle and a mapping table. (maps the group id to the grid id) When the location query packet is sent to the LS, any vehicle along the query path, which has the location information of the queried vehicle, may reply immediately so as to reduce the cost of location query. LLS If no information of queried Forwarded to nearest DLS DLS

25 5. Simulation Results To evaluate the performance of the proposed protocol: The cache-based routing protocol [3] The map-based vehicle location service [4] (VLS) The proposed protocol (denoted as ECB) Simulated by NS-2 and SUMO.

26 A. Total cost of location update: 𝐶𝑢𝑝𝑑𝑎𝑡𝑒×𝑓𝑢𝑝𝑑𝑎𝑡𝑒×𝑇𝑠×𝑉 .
The performance metrics being observed in the simulation are shown as follows: A. Total cost of location update: 𝐶𝑢𝑝𝑑𝑎𝑡𝑒×𝑓𝑢𝑝𝑑𝑎𝑡𝑒×𝑇𝑠×𝑉 . (Tso: simulation interval. V: number of vehicles in the service area. ) B. Total cost of location query: 𝐶𝑞𝑢𝑒𝑟𝑦 × 𝑓𝑞𝑢𝑒𝑟𝑦 × 𝑇𝑠. C. Total cost: total cost of location update and query.

27 The simulation parameters are:
Communication Range Service area Moving speed Vehicle density Simulation interval Packet size of location update Packet size of location query Packet size of location reply 200 m 1800 × 1800 ∼ 3000 × 3000m2 30 ∼ 60 km/h 50 ∼ 200 vehicles/km2 5 minutes. 20 bytes. 8 bytes. 19 bytes.

28 A. Location Update Cost (bytes)
VLS scheme > ECB > cache-based schemes. service area is 1800 × 1800m2 , vehicle density=50 vehicles/km2 (bytes)

29 B. Location Query Cost VLS scheme < ECB < Cache-based schemes. 𝑓𝑞𝑢𝑒𝑟𝑦 = 2queries/min., service area is 1800 × 1800m2 , moving speed=40km/h

30 C. Total Cost The total cost of the ECB scheme is the lowest . vehicle density=50 vehicles/km2 , 𝑓𝑞𝑢𝑒𝑟𝑦 = 2/queries/min., moving speed=40km/h

31 6. Conclusion We propose a novel cost-based location service protocol.
Cost functions for the location service protocol have been proposed so as to guide the deployment of location servers. By deploying proper number of location servers at proper locations, the cost of location update and query can be reduced. Simulation results have shown that the proposed protocol performs better than existing protocols in terms of total location update and query cost.

32 7. 改善方式 透過上述論文提出的cost-based location service protocol ，能有效降低車輛位 置查詢與更新的成本以提高效率。 但未提及傳輸過程中封包的傳送方式，在VANET環境中，無線通訊的脆弱性和車 輛高速移動的性質，車輛往往不能穩定正確的接收廣播封包，容易發生封包遺失 的情形。 因此必須結合網路編碼技術，降低封包遺失造成的重送、錯誤等問題。 以下提出Index Coding技術，作為此Protocol更新和查詢過程中，封包傳輸效 能的改進方式。 Research on Index Coding Technology in Vehicular Network, XIA Bin, WANG Guanghao, WU Yue. Computer Engineering, 2015, 41(6): 1-5.

33 7.1 Vehicular Mobile Opportunistic Network
車載行動機會網路 由傳統VANET發展而來，專門用在VANET這種容易發生連線中斷的網路環境。 車載行動機會網路中，安全方面的應用是關鍵和重要的問題之一。 透過車輛間的通訊，週期性廣播安全訊息，避免潛在的交通危害發生。

34 7.2 Research Situation 在VANET 中, Network Coding 和Index Coding 的應用已有許多研究。 Lee U 提出 CodeTorrent (使用NC的檔案群集協定)： 使用Network Coding優化節點選擇和內容選擇的計算方法。 Ahmed S 提出VANETCODE(使用NC的檔案協調下載協定)： 對鄰居的封包段進行Network Coding 。

35 Li M 提出了CodeOn： 採用Symbol-Level Network Coding (SLNC) 取代 Packet- Level Network Coding (PLNC) ，降低傳輸過程中造成的錯誤。 Hassanabadi B 提出基於Index Coding 的MAC層協定： 以分散式回饋機制取得Side-Information，再透過Index Coding減少傳輸 次數。 用來提供安全方面相關的應用服務和位置訊息的交換服務。

36 7.3 Index Coding 利用接收端的 Side-Information 進行訊源編碼的技術。
無線網路中，某節點要廣播n個封包 X1,X2,…,Xn，給n個接收節點 R1,R2,…,Rn，使得每個接收節點 Ri 能收到所需的 Xi 封包。 假設每個節點都已經有關於X1,X2,…,Xn的部分Side-Information。 這種關係可以透過一個有n個頂點的Directed Side Information Graph G 描述，其中頂點 i ~ j 的有向邊，表示節點 Ri接收到 Xj封包。

37 在給定Side-Information Graph G的條件下，尋找 X1,X2,…,Xn的最優編碼策 略，使得每個節點可根據自己的Side-Information和所接收到的Coded Packet，解碼出所需要的資訊。 雖然接收節點向回饋Side-Information會增加系統傳輸成本，但在資訊量較大 的情況下，透過Index Coding得到的編碼增益遠大於回饋造成的傳輸成 本，因此Index Coding仍是一種高效率的資訊傳輸方式。

38 索引編碼的結構分為2個部分： Get Side-Information。 Encode/Decode of Index Coding。

39 7.3.1 Get Side-Information Side-Information的定義： 若節點 i 收到一個封包 j ，但 j 封包並非節點 i 需要的封包 (i≠j )。 Side-Information 的概念： (1)存在一個發送端，發送的訊息X為bit，𝑋={0,1} 𝑛，利用廣播發送。 (2)存在n個接收端R1,R2,..,Rn，每個Ri都想得到對應的bit封包Xi。 (3)過程中，每個Ri都有機會得到Xj(j≠i)，即為Ri 的 Side-Information。

40 7.3.2 Encode/Decode of Index Coding
Index Coding 的Encode/Decode有許多方法，包括Side-Information Matrix 的minimum rank 或maximum clique 等。 有文獻從圖論的角度對Index Coding 性質進行了深入研究，證明了對於任 意給定的Side-Information Graph，可以找到最小長度等於Side- Information Matrix’s minimum rank 的Linear Index Coding 建構方法。

41 進一步證明， Optimal Linear Index Coding可以根據Side-Information Matrix的minimum rank matrix得到，但複雜度較高，因為在給定一個矩 陣的條件下尋找最大線性無關組本身就是一個NP-hard問題，網路規模較大 的情況下，無法達到即時編碼的需求。 現有文獻當中，提出了一系列線性規劃、圖著色等理論方法的啟發式演算法。 將採取運用maximum clique的Index Coding。

42 以下介紹Index Coding On VANET Data Broadcast機制： 7. 4
以下介紹Index Coding On VANET Data Broadcast機制： Distribution Feedback On Side-Information Generation Mechanism Base On Maximum Clique Index Coding Solution

43 7.4 Use Index Coding On VANET Data Broadcast
採用Index Coding技術，在封包遺失率很高的VANET環境中。 目標是在一定的封包遺失率下，盡可能降低最小傳播次數。 利用分散式回饋機制產生Side-Information，再用Index Coding將訊 息編碼以進行廣播。

44 7.4.1 Distribution Feedback Side-Information Generation Mechanism
每個節點Nk 以二元矩陣格式，維護一份Side-Information table： 若節點 j 收到節點 I 的訊息 F(Nk,i,j)=1，否則F(Nk,i,j)=0。 有2種產生Side-Information的回饋方式： (1)週期性回饋： 無論Side-Information table是否改變，節點會週期性傳送回饋訊息。 (2)觸發性回饋： 每當節點收到其他節點的新訊息或Side-Information table中的內容 過期，會更新Side-Information table並廣播。

45 週期性回饋，優點：即時性佳，缺點：通訊成本大。
觸發性回饋則反之。 無論採用哪種方式，收到回饋訊息的車輛，會更新自身的Side- Information table ，確保自身的Side-Information table與現狀同 步。

46 7.4.2 Base On Maximum Clique Index Coding Solution
利用Side-Information table ，每個時隙各節點能得知鄰居的Side-Information。 1 5 2 3 4 節點拓譜圖 0: Broadcaster ， 1~5: Receiver

47 由於無線通道的特性，在一個時刻下某些節點未能收到期望的封包，卻機會式 的得到傳給其他節點的封包，即為一個Side-Information。 廣播節點0透過回饋機制，建立紀錄鄰居的Side-Information Table，如下： 封包 目標 車 輛 1 2 3 4 5

48 (1)將Side-Information table 轉換為有向拓樸圖。 F(1,3)=1，表示節點1收到節點3的訊息，對應右圖中節點1指向節點3有向邊。 F(3,2)=0，表示節點3沒有收到節點2訊息。 1 2 3 4 5 訊息 車 1 2 3 4 5 有向拓樸圖

49 (2)轉換為無向拓樸圖。 若節點A和節點B存在一條雙向邊，能轉為一條無向邊，其餘則刪除。
1 2 3 4 5 1 5 2 3 4 有向拓樸圖 無向拓樸圖

50 此時節點 1、3、4 形成了一個maximum clique。
對於接收節點 1、3、4，廣播節點 0 只需再將封包X1、X3、X4 利 用XOR運算後廣播，節點 1、3、4 即能用已存的Side-Information， 解碼出需要的資訊。 Node 1 Packet： X1=[X1 ⊕ X3 ⊕ X4] ⊕X3 ⊕ X4。

51 根據無向拓樸圖，節點 0 會利用Index Coding 編碼[X1 ⊕ X3 ⊕ X4] 和 [X2 ⊕ X5] ，即能用2次的發送機會送出5個封包。 透過Index Coding，廣播節點能在一次的發送中，盡量發送最多的訊息。 1 5 2 3 [X1 ⊕ X3 ⊕ X4] 4 [X2 ⊕ X5] 無向拓樸圖

52 7.4.3 Maximum Clique Generation Method
前面將Index Coding問題轉為尋找無向圖中maximum clique的問題。 Maximum Clique 是一個NP-hard問題。 1980年代末期，許多人利用啟發式演算法求解，如：BK演算法、遺傳演算 法、模擬退火演算法、類神經網路等，得到了滿意的效果。 這裡使用一種改進的圖著色演算法MaxCliqueDyn來尋找maximum clique。

53 Clique： 指無向圖中的完全連接子圖，即兩兩之間有邊的頂點集合。 Maximal Clique： 對於一圖中，若一Clique不能被其他任一Clique包含，即非其他Clique真子 集。 Maximum Clique： 一圖中，頂點數最多的clique。 maximum是尋找一個頂點數最多的clique，maximal是尋找一組最大的 clique，前者的計算速度會是後者的數倍。

54 7.5 模擬實驗 為了驗證演算法的有效性，設計實驗平台模擬VANET中Index Coding 的應用情景。 實驗平台：
利用Sumo模擬車輛交通、NS-2模擬網路通訊。 兩者之間利用TraCI協定交換資訊。 模擬平台在執行時，可以控制節點的運動行為，能真實的模擬VANET 的通訊情形和移動行為。

55 環境結構為Client-Server架構：SUMO當Server，NS-2為Client ，透過TCP協定通訊，分別進行交通模擬和通訊模擬。
0. NS2連接SUMO 2. 模擬 1. SIMSTEP k命令 4. 設置NS節點 的目的節點 3. 車輛位置訊息 5. 模擬 TraCI 模擬環境結構

56 地圖場景：取自OpenStreetMap 城市道路的實際地圖。 路段：選擇速限在 40 km/ h 以上的道路，面積 8500m×8500 m 。

57 車輛的設定： 車輛：31台(具備SRD和GPS) 廣播車輛S：一台車行走固定路線，路線經過地圖大部分區域。 接收車輛R：其他30台車的路線為隨機選 將地圖按照cost-base location service protocol的規則，均勻的劃分為 level 1 grid，每9個level 1 grid再形成一個level 2 grid。

58 7.5.2 實驗設計 實驗中設計的3個訊息封包： HELLO封包： 由所有車輛週期性的發送，用來維護鄰居節點的集合。 DATA封包：
由廣播車輛S發送，車輛R進行接收，封包可能是編碼或未編碼。 ACK封包： 由接收車輛R接收到封包後的回應封包，透過ACK訊息回饋目 前的 Side-Information情況。

59 封包發送流程 Step1. 廣播車輛S負責發送封包，接收車輛R1~Rn接收廣播封包。
封包於每個發送週期傳送。( 如：1s ,與TraCI設定的時間相同 ) R1 S R2 R5 R3 R4 Rn

60 Step2. S透過發送HELLO封包找到鄰居建立清單，確定能收到廣播封包的接收車輛Ri。 S HELLO R1 HELLO HELLO HELLO R2 R5 HELLO R3 R4 Rn

61 Step3. S開始廣播訊息 S DATA R1 DATA DATA DATA R2 R5 DATA R3 R4 Rn

62 Step4. 若S收到節點 Ri 回傳的 ACK 封包，表示Ri 收到了DATA封包。
a. 當 Xj = Ri，表示節點Ri 收到期望封包。 b. 若DATA封包非節點i需要的封包，則產生了一個Side-Information。 S ACK R2 X3 X2 ACK (Side-Information) R1

63 Step5. S 透過ACK封包(回饋機制)，維護周邊車輛的Side-Information Table。
1) 得到期望封包(i=j)，退出Side-Information Table不參與Index Coding。 2) 得到他人封包，回傳Side-Information並更新時間。 3) 某節點資訊過期(無回應等)，該節點的Side-Information會被移除。 訊 息 車 X1 X2 X3 … Xn clock R1 1 20 R2 10 R3 …. Rn 30 S ACK ACK (Side-Information) R2 R1

64 Step6. S 透過Side-Information Table以MaxCliqueDyn 找出maximum clique。
若存在maximum clique的所有節點都再相鄰節點清單中， S即對每個maximum clique 進行Index Coding並發送封包。 若不存在maximum clique，則隨機選擇相鄰清單中的任一節點發送其DATA封包。 S [X1 ⊕ X4 ⊕ X9] 1 [X5 ⊕ X6] (X4,X9) R2 R3 9 4 5 (X6) (X5) 6 (X1,X9) (X1,X4)

65 7.5.3 實驗結果與分析 在實驗過程中，初始將maximum clique大小設定為2。
更多的節點，將形成更分散Side-Information Graph，而出現更 多的maximum clique，有利於進行更有效的索引編碼。

66 最少傳播次數：廣播車輛以最少傳播的次數，讓所有車輛收到所需封包。 (未編碼前，接收節點數量等於封包傳輸次數。)
可以看出，經過Index Coding後，有效降低了最少傳播次數。

67 編碼增益：為編碼前後的傳輸次數比。 編碼增益保持在1.4 ~ 1.6 間，編碼後使得封包傳播次數降了近1/3。

68 實驗分析 實驗結果可以看出，廣播車輛能用更少的時隙發送完指定的封包， 節省無線通道的頻寬，提高廣播效率。
大小為2的Maximum Clique演算法，即能取得很好的效果。 Maximum Clique越大，理論上Index Coding演算法的性能越好， 即最少傳輸次數更低而編碼增益更高，但同時會消耗更多計算資 源。

69 7.6 結論 提出了一種基於索引編碼的訊息廣播方案，使用該方案可以實現更 高效率的訊息傳輸服務。
透過使用實際地圖進行模擬，實驗結果證明在VANET中使用Index Coding技術的訊息廣播方法，可以降低最少傳輸次數，有利於更有 效的Index Coding。 Research on Index Coding Technology in Vehicular Network, XIA Bin, WANG Guanghao, WU Yue. Computer Engineering, 2015, 41(6): 1-5.