Tóm tắt Luận án Nghiên cứu giải pháp cải thiện hiệu năng mạng manet

BỘ THÔNG TIN VÀ TRUYỀN THÔNG

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

VŨ KHÁNH QUÝ

NGHIÊN CỨU GIẢI PHÁP CẢI THIỆN HIỆU NĂNG

MẠNG MANET

Chuyên ngành: Kỹ thuật Viễn thông

Mã số: 9.52.02.08

TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT

Hà Nội - 2021

Công trình hoàn thành tại:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học:

1. PGS.TS. Nguyễn Tiến Ban

2. PGS.TS. Nguyễn Đình Hân

Phản biện 1:

Phản biện 2:

Phản biện 3:

Luận án được bảo vệ trước hội đồng chấm luận án cấp Học viện họp tại:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

vào hồi:

Có thể tìm hiểu luận án tại:

1. Thư viện Quốc gia Việt Nam

2. Thư viện Học viện Công nghệ Bưu chính Viễn thông

1

MỞ ĐẦU

Với sự phát triển mạnh mẽ của các hệ thống thông tin di động, theo báo

cáo của Cisco vào năm 2017, lưu lượng dữ liệu di động toàn cầu đã tăng 18

lần trong vòng 5 năm qua, chiếm 63% tổng lưu lượng mạng và đạt 7.2

exabytes mỗi tháng với trên 8 tỉ thiết bị di động tham gia kết nối mạng. Dự

kiến đến năm 2021, lưu lượng dữ liệu di động toàn cầu sẽ tăng 7 lần so với

hiện tại và có trên 11.6 tỉ thiết bị di động tham gia kết nối mạng. Trong đó,

lưu lượng dữ liệu đa phương tiện chiếm ¾ lưu lượng mạng toàn cầu [18]. Do

đó, thiết kế các mạng di động nhanh hơn, tiết kiệm năng lượng hơn là nhu

cầu cấp thiết. Các mạng di động tùy biến (Mobile Ad-hoc Networks -

MANET) ra đời từ những năm 1970 là một tập các thiết bị di động có khả

năng tự cấu hình, thiết lập và truyền thông với nhau mà không dựa vào các

trạm cơ sở [13], [24], [45].

Do rất linh hoạt trong việc thiết lập và truyền dữ liệu, các mạng MANET

đã có nhiều ứng dụng thiết thực phục vụ con người trong các lĩnh vực như

chăm sóc sức khỏe [5], [51], cứu hộ, khắc phục thảm họa [12], [60], giải trí

[59], [84], quân sự [61], giao thông thông minh [20], [56] và rất nhiều các

lĩnh vực khác đã được chỉ ra trong [8].

Hiệu năng của mạng MANET phụ thuộc vào quy mô, mô hình truyền

thông và môi trường giao tiếp vô tuyến. Tuy nhiên, với khả năng và năng lực

hạn chế, hiệu năng của MANET nói chung khá thấp [24], [45], [88]. Trong

MANET, vì các nút mạng di động phải hợp tác với nhau để truyền gói tin,

giao thức định tuyến có vai trò đặc biệt quan trọng trong vấn đề cải thiện hiệu

năng mạng [82]. Các giao thức định tuyến thông thường đã được sử dụng

cho MANET như AODV hay DSR sử dụng số chặng (hop-count) làm tham

số định tuyến là không hiệu quả [24].

Khảo sát cho thấy, rất nhiều nghiên cứu đã được thực hiện để giải quyết

vấn đề này. Tuy nhiên mỗi nghiên cứu chỉ phù hợp với một cấu trúc, ứng

dụng mạng cụ thể. Do đó, đề xuất các giải pháp định tuyến mạnh mẽ, tin cậy,

hiệu năng cao là hướng nghiên cứu cấp thiết, thời sự và có tính mở. Do vậy,

nghiên cứu sinh đã chọn đề tài “Nghiên cứu giải pháp cải thiện hiệu năng

mạng MANET” cho luận án của mình.

Mục tiêu nghiên cứu của luận án là đề xuất các cơ chế, giao thức nhằm

cải thiện hiệu năng mạng MANET cũng như tích hợp, mở rộng khả năng của

2

mạng MANET với các mạng đám mây và Internet, góp phần nâng cao chất

lượng dịch vụ truyền tin cũng như mở ra các năng lực mới cho MANET.

Để đạt được các mục tiêu nêu trên, các nhiệm vụ cụ thể cần phải giải

quyết bao gồm: (1) Nghiên cứu, đề xuất các giao thức định tuyến cải thiện

hiệu năng cho mạng MANET; (2) đề xuất các giải pháp nhằm tích hợp, mở

rộng khả năng cho mạng MANET và (3) Mô phỏng, đánh giá và so sánh hiệu

năng các giao thức, giải pháp đề xuất với các giao thức, giải pháp truyền

thống của mạng MANET và đề xuất các giải pháp áp dụng.

Từ các nhiệm vụ nghiên cứu trên, phương pháp nghiên cứu của luận án

là nghiên cứu lý thuyết kết hợp với mô phỏng. Về lý thuyết, luận án thực

hiện khảo sát, phân tích, tổng hợp đánh giá các nghiên cứu liên quan trong

và ngoài nước, từ đó xác định các vấn đề nghiên cứu khả thi, hệ thống hóa

các vấn đề cần nghiên cứu, xây dựng mô hình bài toán, đề xuất giải thuật khả

thi, mô phỏng, phân tích và đánh giá hiệu quả của giải thuật. Cuối cùng, đưa

ra các nhận xét, đánh giá dựa trên các kết quả đạt được; đề xuất các khuyến

nghị, các giải pháp cải thiện hiệu năng hệ thống.

Với các mục tiêu nghiên cứu đã nêu ở trên, kết quả nghiên cứu của luận

án gồm ba phần: Mở đầu, Nội dung và Kết luận. Phần Nội dung gồm 04

chương với nội dung như sau:

Chương 1. Mạng MANET và bài toán cải thiện hiệu năng.

Chương 2. Định tuyến trong mạng MANET

Chương 3. Định tuyến cải thiện hiệu năng mạng MANET

Chương 4. Tích hợp, mở rộng khả năng của MANET

3

CHƯƠNG 1: MẠNG MANET VÀ BÀI TOÁN CẢI THIỆN HIỆU NĂNG

1.1 Mô hình hệ thống mạng MANET

Để trình bày nguyên lý và những ý tưởng chính của giao thức, luận án sử

dụng một đồ thị có trọng số G để biểu diễn mô hình mạng MANET như sau:

Định nghĩa 1.1: Gọi G = (V, E) là đồ thị truyền thông trong mạng

MANET. Khi đó V = {V_ꢀ, . . . , V_ꢁ} là tập hữu hạn các đỉnh của G, E là tập hữu

hạn các cạnh. Với mỗi cặp nút V , V , chúng ta có E_ꢂꢃ= ꢄV , V ꢅ nếu hai nút

ꢂ

ꢃ

ꢂ

ꢃ

liên kết trực tiếp với nhau.

Hình 1.1. Mô hình đồ thị của mạng MANET.

Để biểu diễn khả năng tính toán và lựa chọn tuyến đường truyền tin phù

hợp của giao thức, luận án mô hình hóa kiến trúc liên mạng bởi một đồ thị

có trọng số. Mỗi cạnh E_ꢂꢃcủa cặp nút ꢄV , V ꢅ sẽ được thiết lập một trọng số

ꢂ

ꢃ

W . Ở đây, W biểu diễn giá trị của các tham số định tuyến. Lưu ý, trong

ꢂ,ꢃ

mạng MANET hai nút mạng bất kỳ có thể có kết nối trực tiếp (tức là một

cạnh của đồ thị) hoặc kết nối gián tiếp thông qua các nút trung gian (tức là

một đường đi trong đồ thị). Vì vậy, các tuyến đường từ nút nguồn đến nút

đích có thể được biểu diễn bởi các đường đi trên đồ thị.

4

1.2 Hiệu năng mạng MANET

1.2.1 Các yếu tố ảnh hưởng

Hiệu năng của mạng MANET bị ràng buộc bởi nhiều yếu tố khác nhau.

Những vấn đề này được biết đến như là các bài toán với độ phức tạp đầy đủ

(NP-complete) [24], [45]. Để đơn giản hóa, có thể chia các yếu tố này thành

hai loại chính: từ môi trường ngoài và nội tại trong mạng.

1.2.2 Các tiêu chí đánh giá hiệu năng thông qua mô phỏng

Nội dung này trình bày về các tiêu chí đánh giá hiệu năng thông qua mô

phỏng như tỷ lệ phân phối gói tin, trễ trung bình, thông lượng trungbình, tải

định tuyến, tuổi thọ của mạng và năng lượng trung bình còn lại của nút mạng.

1.3 Các công trình nghiên cứu liên quan

1.3.1 Các công trình nghiên cứu trong nước

Tại Việt Nam các kết quả nghiên cứu liên quan đến hệ thống mạng

MANET còn khá hạn chế.

1.3.2 Các công trình nghiên cứu ngoài nước

Khảo sát các giao thức định tuyến cho mạng MANET được công bố trên

IEEE Xplore Digital Library cho thấy, nhằm cải thiện hiệu năng cho mạng

MANET, các nghiên cứu trên thế giới tập trung vào một số hướng sau:

Tiếp cận theo hướng sử dụng MANET đa kênh.

Tiếp cận theo hướng định tuyến sử dụng đa tham số.

Tiếp cận theo hướng định tuyến đảm bảo QoS.

Tiếp cận theo hướng tiết kiệm năng lượng.

1.4 Xác định bài toán nghiên cứu

Dựa trên khảo sát và phân tích tình hình nghiên cứu trong nước và trên

thế giới, luận án xác định được một số hướng nghiên cứu nhằm giải quyết

bài toán cải thiện hiệu năng mạng MANET, như sau:

Vấn đề thứ nhất: Nghiên cứu và đề xuất các giao thức định tuyến:

-

Định tuyến với cấu trúc mạng MANET đa kênh

Định tuyến đa tham số:

Định tuyến đảm bảo QoS

Vấn đề thứ hai: Tích hợp, mở rộng khả năng của MANET:

-

Giải pháp tăng tuổi thọ mạng

Giải pháp phối hợp MANET và đám mây

5

Hình 1.6. Xác định bài toán nghiên cứu.

1.7 Kết luận Chương 1

Nội dung Chương 1 trình bày khái quát về mô hình, nguyên lý hoạt động,

các tham số và yếu tố ảnh hưởng đến hiệu năng hệ thống mạng MANET.

Qua khảo sát, phân tích và đánh giá tình hình nghiên cứu trong nước và thế

giới cho thấy các hạn chế của các nghiên cứu trước đây trong vấn đề cải thiện

hiệu năng mạng MANET. Trến cơ sở các hạn chế này, hướng nghiên cứu

của luận án được xác định là đề xuất các giao thức định tuyến nhằm cải thiện

hiệu năng cho các cấu trúc mạng MANET khác nhau; đề xuất các cơ chế,

giải pháp nhằm tích hợp, mở rộng khả năng của mạng MANET.

CHƯƠNG 2: ĐỊNH TUYẾN TRONG MẠNG MANET

Tóm tắt: Trong Chương 2, để làm rõ hơn vấn đề định tuyến và nhằm tìm

ra phương thức để giải quyết các bài toán đã được xác định, luận án thực hiện

một khảo sát các tham số và giao thức định tuyến gần đây được đề xuất cho

mạng MANET. Kết quả cho thấy, nhằm cải thiện hiệu năng MANET, với

mỗi cấu trúc, ứng dụng MANET, cần có các giải pháp khác nhau, phù hợp

với cấu trúc, ứng dụng đó. Khảo sát các giao thức định tuyến tiêu biểu của

MANET cho thấy, giao thức định tuyến AODV cho hiệu năng mạng ổn định

và tốt hơn các giao thức khác. Do đó, cải tiến giao thức AODV nhằm đáp

ứng các yêu cầu, nhiệm vụ của các cấu trúc mạng khác nhau là phù hợp.

6

2.1 Nguyên lý định tuyến trong mạng MANET

Khảo sát các giao thức định tuyến cho MANET, dựa theo phương thức

định tuyến, có thể phân các giao thức định tuyến vào hai nhóm chính: định

tuyến chủ động và định tuyến theo yêu cầu.

2.2 Khảo sát tham số định tuyến

Nội dung phần này trình bày về đặc điểm của các tham số định tuyến cho

mạng MANET. Các tham số định tuyến được phân tích, so sánh và phân lớp

theo các hướng tiếp cận như lưu lượng, thông tin vô tuyến, vị trí và di động,

năng lượng.

2.3 Bài toán lựa chọn các tham số định tuyến

2.3.1 Đơn tham số

Các thuật toán tính chi phí tuyến đường dựa trên đơn tham số như Hop-

count hoặc delay đã được biết đến và sử dụng rộng rãi trong các mạng hiện

tại. Để ánh xạ nhiều điều kiện ràng buộc vào một tham số duy nhất, cách tiếp

cận khả thi là trộn các yều cầu chất lượng dịch vụ vào thành một yêu cầu duy

nhất, từ đó ánh xạ thành một tham số định tuyến.

2.3.2 Đa tham số

Gọi ꢆ_ꢇ,ꢈlà chi phí của liên kết (ꢉ, ꢊ) , thuộc tuyến đường ꢋ =

{ꢉ, ꢊ, ꢌ, … , ꢍ, ꢎ} là tập các nút mạng của tuyến đường.

Định nghĩa 2.1: Chi phí của tuyến đường p là tổng (Additive), nếu:

ꢆ_ꢏ= ꢆ_ꢇ,ꢈ+ ꢆ +. . . +ꢆ_ꢑ,ꢒ

(2.21)

ꢈ,ꢐ

Định nghĩa 2.2: Chi phí của tuyến đường p là tích (Multiplicative), nếu

ꢆ_ꢏ= ꢆ_ꢇ,ꢈ× ꢆ_ꢈ,ꢐ× … × ꢆ_ꢑ,ꢒ

(2.22)

Định nghĩa 2.3: Chi phí của tuyến đường p là cực tiểu (Minimum), nếu

ꢆ_ꢏ= ꢎꢉꢓ{ꢆ_ꢇ,ꢈ, ꢆ , … , ꢆ_ꢑ,ꢒ

}

(2.23)

ꢈ,ꢐ

Trong [24], [45], các nghiên cứu đã chỉ ra, khi có nhiều hơn hoặc bằng 2

tham số kiểu additive hoặc multiplicative tham gia, bài toán xác định tuyến

đường tối ưu sẽ có độ phức tạp NP-Complete. Do đó, các nghiên cứu thường

tìm cách hạn chế các tham số ràng buộc để đưa về dạng bài toán có thể giải

được trong thời gian thực.

7

2.4 Các phương thức thu nhận thông tin định tuyến

Phần này trình bày các phương thức thu nhận thông tin định tuyến trong

mạng MANET.

2.5 Các giao thức định tuyến tiêu biểu cho mạng MANET

2.5.1 Giao thức định tuyến AODV và DSR

2.5.2 Giao thức định tuyến OLSR và DSDV

2.5.3 So sánh hiệu năng các giao thức

Kết quả mô phỏng cho thấy, trong điều kiện mạng có lưu lượng và tốc độ

di động thấp, các giao thức định tuyến chủ động như OLSR hoạt động khá

tốt. Tuy nhiên, khi lưu lượng mạng hoặc tốc độ di chuyển của nút mạng tăng

cao, các giao thức định tuyến theo yêu cầu như AODV có các chỉ số hiệu

năng vượt trội so với các giao thức còn lại. Hơn thế, chi phí tải định tuyến

của các giao thức theo yêu cầu cũng thấp hơn rất nhiều so với các giao thức

chủ động. Điều này phản ánh khả năng tiết kiệm năng lượng của giao thức

định tuyến theo yêu cầu so với giao thức định tuyến chủ động.

2.6 Kết luận Chương 2

Do thuộc tính tự tổ chức của MANET, định tuyến là được coi là một vấn

đề đầy thách thức. Khảo sát các tham số và giao thức định tuyến cung cấp

một cách thức để thiết kế các giao thức định tuyến mới cho MANET. Trong

chương này, luận án đã tiến hành khảo sát các tham số và giao thức định

tuyến đề xuất cho mạng MANET công bố trên cơ sở dữ liệu của thư viện số

IEEE Xplore trong giai đoạn 2010- 2017. Kết quả cho thấy, cải thiện hiệu

năng là hướng nghiên cứu cấp thiết, định tuyến là vấn đề chính trong việc

nâng cao hiệu năng MANET. Hơn thế, nghiên cứu luôn có tính kế thừa, do

đó, đa số các giao thức đề xuất mới cho MANET được cải tiến dựa trên các

giao thức định tuyến tiêu biểu đã biết. So sánh hiệu năng một số giao thức

tiêu biểu cho MANET trong các kịch bản khác nhau về di động và lưu lượng

mạng cho thấy, giao thức AODV có hiệu năng tương đối ổn định trong đa số

các kịch bản. Do đó, nghiên cứu, đề xuất các giao thức định tuyến mới trên

cơ sở cải tiến từ giao thức AODV là hướng nghiên cứu khả thi.

CHƯƠNG 3: ĐỊNH TUYẾN CẢI THIỆN HIỆU NĂNG MẠNG MANET

Tóm tắt: Như đã đề cập trong Chương 2, định tuyến là vấn đề chính để

cải thiện hiệu năng của mạng MANET. Trong Chương 3, luận án đề xuất ba

8

thuật toán định tuyến nhằm cải thiện hiệu năng cho ba cấu trúc MANET khác

nhau, cụ thể như sau: (1) Cải thiện hiệu năng mạng MANET hoạt động đa

kênh, tiếp cận theo hướng tác tử di động, cải tiến từ AODV [J2]; (2) Cải thiện

hiệu năng mạng MANET đơn kênh, tiếp cận theo hướng đa tham số với hàm

tính chi phí dựa vào một tập gồm ba tham số: độ dài hàng đợi, chất lượng

tuyến đường và số chặng, cải tiến từ AODV [C2]; Cuối cùng, để đảm bảo

chất lượng dịch vụ cho các ứng dụng đa phương tiện hoạt động trên mạng

MANET, luận án đề xuất giao thức Q-AODV [J3].

3.1 Giao thức định tuyến A-WCETT

3.1.1 Cách tiêp cận và ý tưởng thiết kế

Nhằm cải thiện hiệu năng mạng MANET hoạt động đa kênh (MANET đa

kênh), Draves và nhóm nghiên cứu [71] đã đề xuất giao thức định tuyến

WCETT với mục đích đặc biệt là giảm nhiễu đồng kênh. Giải pháp đưa ra là

cố gắng hạn chế các nút sử dụng cùng một kênh trên toàn tuyến. Kỹ thuật cụ

thể là dùng một trọng số bình quân (ꢔ) để cân bằng giữa tổng chi phí toàn

tuyến với ảnh hưởng của kênh bị thắt nút cổ chai. Về chi tiết, tài liệu số [71]

không đưa ra cách xác định giá trị ꢔ (xem Mục 2.2.2.7).

Luận án đề xuất thiết lập giao thức định tuyến mới, gọi là A-WCETT trên

cơ sở mở rộng WCETT để lựa chọn tuyến đường cho mạng MANET.

3.1.2 Tham số định tuyến

Trong giao thức AODV [10], chi phí của tuyến đường được tính bằng

tổng số chặng từ nguồn đến đích. Để cải thiện hiệu năng mạng MANET,

Couto và cộng sự [19] đề xuất tham số định tuyến ETX (Mục 2.2.2.5).

Để xác định ETX, mỗi nút gửi các gói tin thăm dò tới các nút láng giềng.

Dựa vào số gói tin thăm dò gửi đi và số gói tin phản hồi nhận được, mỗi nút

đánh giá được khả năng truyền tin thành công. Lần lượt ký hiệu ꢕ_ꢖvà ꢕ_ꢗlà

xác suất gửi một gói dữ liệu thành công và xác suất gói tin ACK nhận được.

Khi đó, xác suất một sự kiện truyền/nhận thành công trên một liên kết là

ꢕ_ꢖ× ꢕ_ꢗ. Số lần truyền dự kiến trên một liên kết giữa hai nút trên liên kết ꢍ

được xác định theo công thức sau:

ꢀ

ꢘꢙꢚ = _ꢛ

(3.1)

× ꢛ

ꢜ

ꢝ

ETX của tuyến đường p, là tổng ETX của các liên kết l, với ꢍ ∈ ꢋ.

9

∑

ꢘꢙꢚ_(ꢞ)

=

_ꢑ∈ꢞꢘꢙꢚ_(ꢑ)

(3.2)

Để ràng buộc băng thông vào quyết định lựa chọn tuyến đường, tham số

ETT được xác định như sau. Ký hiệu S là kích cỡ của gói tin và B là băng

thông trên liên kết l. ETT của liên kết l được xác định:

ꢘꢙꢙ = ꢘꢙꢚ_(ꢑ)× (ꢟ/ꢠ)

(3.3)

(ꢑ)

Bằng việc đưa băng thông kết nối vào tính toán chi phí của đường đi, chi

phí ETT không những ràng buộc các can thiệp vật lý (liên quan đến tỷ lệ tổn

thất gói tin), mà còn chịu ảnh hưởng từ chất lượng mỗi kết nối.

3.1.3 Đặc tả giao thức

Cũng giống như WCETT, A-WCETT là một giao thức định tuyến theo

yêu cầu, hoạt động dựa trên nguyên lý, mỗi khi có yêu cầu truyền dữ liệu,

nút nguồn sẽ khám phá và xác định tuyến đường từ nút nguồn đến nút đích.

Cấu trúc gói tin điều khiển và tiến trình tìm đường của A-WCETT hoàn toàn

giống như WCETT [67].

Luận án đề xuất một phương pháp xác định giá trị ꢔ động, tùy thuộc vào

tỷ lệ giữa các kênh, cụ thể như sau:

Xét tuyến đường ꢋ gồm D chặng. Tổng thời gian truyền của các chặng

cùng trên kênh j (giả sử hệ thống có tối đa k kênh) được xác định như sau:

∑

ꢚ = _{ꢡꢢặꢣꢤ ꢇ ꢥꢗꢦꢧềꢣ ꢥꢗêꢣ ꢐêꢣꢢ ꢈ}ꢘꢙꢙ , 1 ≤ ꢊ ≤ ꢌ

(3.4)

(3.5)

ꢈ

(ꢇ)

ꢬ

ꢔ = ^∑

ꢩꢪꢪ

(ꢫ)

ꢫꢭꢮ

ꢳꢴꢵ

ꢮꢱꢰꢱꢲ

ꢯ

ꢰ

ꢨ

ꢺ

ꢀ

ꢽ

ꢘꢙꢙ_(ꢇ)+ ꢹ ꢼ _ꢀꢿ^ꢒ_ꢈꢿ^ꣀ_ꢐ^ꣁꢚ

ꢈ

ꢇꢾꢀ

ꢀꢻꢺ

∑

ꢶ − ꢷꢸꢘꢙꢙ = ꢹ_ꢀꢻꢺ

ꢼ

Hoạt động của giao thức A-WCETT được mô tả bằng mã giả như sau:

Thuật toán 3.1: Thuật toán lựa chọn tuyến đường A-WCETT

1

2

3

4

5

6

P=routeset(S,D)

Cost=∞, Selectedroute={∅}

for each p in P

X[k]={∅}, Total=0

for j=1 to sizeof(route[p])

Total=Total+ETT[j]

10

Thuật toán 3.1: Thuật toán lựa chọn tuyến đường A-WCETT

7

If link[j].chanel=k then X[k]=X[k]+ETT[j]

endfor

8

9

ꢔ=Total/max(X[k])

10

Calculator(A-WCETT[i]) //Theo công thức (3.5)

11 endfor

12 Cost = ∞

13 for each p in P

14 If Cost< A-WCETT[p] then

15

Cost=A-WCETT[p]; Selectedroute=rouset[p]

16 return(Selectedroute, Cost)

3.1.4 Đánh giá hiệu năng

Từ các kết quả mô phỏng cho thấy: giao thức A-WCETT cải thiện độ trễ

và thông lượng tốt hơn giao thức WCETT do được tối ưu về tham số ꢔ. Hai

giao thức A-WCETT và WCETT hoạt động đa kênh nên tăng thông lượng

và giảm tắc nghẽn toàn hệ thống. Nhờ những cải tiến đó mà chúng đạt được

thời gian trễ thấp và thông lượng cải thiện so với giao thức AODV.

3.2 Giao thức định tuyến MM-AODV

3.2.1 Cách tiếp cận và ý tưởng thiết kế

Nhằm cải thiện hiệu năng cho mạng MANET đa tham số, luận án đề xuất

một giao thức định tuyến, cải tiến từ AODV gọi là MM-AODV. Hàm tính

chi phí kết hợp giữa ba tham số: độ dài hàng đợi của nút mạng, chất lượng

liên kết và số chặng để ra quyết định chọn tuyến đường. Hơn thế, luận án

cũng thiết lập bộ tham số hiệu năng (∝, ꢔ, ꣂ). Tùy theo giá trị bộ hệ số được

thiết lập, giao thức MM-AODV sẽ lựa chọn cơ chế định tuyến dựa trên: Số

chặng nhỏ nhất (∝= 1), Chất lượng tuyến đường (ꢔ = 1) hay Độ dài hàng

đợi (ꣂ = 1) hoặc lựa chọn cơ chế với bộ hệ số cân bằng (∝= ꢔ = ꣂ = 1/3).

Các vấn đề chi tiết được luận án trình bày như sau.

3.2.2 Tham số định tuyến

Để cải thiện hiệu năng của mạng, luận án đề xuất hàm tính chi phí với ba

tham số định tuyến như sau:

ꣃ_(꣄): Là số chặng giữa nút nguồn và nút đích của tuyến đường p.

11

Chất lượng liên kết ꣅ꣆꣇_(꣈): Tham số này được mô tả trong Mục 2.2.2.5.

Lần lượt ký hiệu ꢕ_ꢖvà ꢕ_ꢗlà xác suất gửi và nhận một gói tin thành công trên

liên kết ꢍ. Khi đó, xác suất dự kiến truyền/nhận thành công một gói tin trên

liên kết ꢍ (một kết nối giữa hai nút liền kề) được xác định như sau:

ꢀ

ꢘꢙꢚ = _ꢛ

(3.6)

× ꢛ

ꢜ

ꢝ

ETX của một tuyến đường, là tổng các ETX của các liên kết trên tuyến .

Độ dài hàng đợi ꣉꣊_(꣋): Tỷ lệ độ dài hàng đợi của một nút mạng i được

đánh giá theo công thức sau:

꣎

ꢫ

꣌꣍_(ꢇ)

=

(3.7)

꣎

ꢳꢴꢵ

Trong đó, ꣌_ꢇvà ꣌_ꢒꣀꣁlần lượt là số gói tin trong hàng đợi lớp MAC và

kích cỡ hàng đợi lớn nhất của nút ꢉ.

3.2.3 Đặc tả giao thức

Cũng giống như giao thức AODV, MM-AODV là một giao thức định

tuyến theo yêu cầu, hoạt động dựa trên nguyên lý, mỗi khi có yêu cầu truyền

dữ liệu, nút nguồn sẽ khám phá và xác định tuyến đường từ nút nguồn đến

nút đích. Tiến trình khám phá tuyến đường bắt đầu với việc nút nguồn gửi

quảng bá gói tin tìm đường RREQ với phần tiêu đề đã được thay đổi như sau

{ETX, LQ, AODV RREQ Header}, tham số h sẽ nhận được giá trị từ trường

Hop-count trong phần tiêu đề mặc định của AODV. Sau đó, những gói tin

này sẽ được chuyển tiếp thông qua các nút trung gian để tới nút đích. Một

điểm khác so với phương thức gửi gói tin RREQ trong giao thức AODV

truyền thống là, tại mỗi nút trung gian, khi nhận được gói tin RREQ, nút

trung gian sẽ tiến hành cập nhật các giá trị ETX và LQ.

Để tính chi phí tuyến đường, luận án đề xuất hàm chi phí ꢸ꣏ như sau:

∝× ℎ_(ꢞ)+ ꢔ × ꢘꢙꢚ_(ꢞ)+ ꣂ × ꣌꣍_(ꢞ)

ꢸ꣏ = ꣐

(3.8)

(ꢞ)

∝ + ꢔ + ꣂ = 1

Do đó, chi phí của tuyến đường p có D chặng được xác định như sau:

^ꢽ꣑ꢀꢸ꣏_{( )}

(3.9)

∑

ꢸ꣏_{( )}

=

ꢞ

ꢇ

ꢇꢾꢀ

12

Dựa vào chi phí ꢸ꣏_{( )}, nút đích sẽ chọn tuyến có chi phí thấp nhất. Thuật

ꢞ

toán lựa chọn tuyến đường của MM-AODV được mô tả bằng mã giả:

Thuật toán 3.2: Thuật toán lựa chọn tuyến đường MM-AODV

1

2

3

4

5

6

7

8

9

P=routeset(S,D)

Cost=∞, Selectedroute={∅}

Setup performance factors (꣒, ꢔ, ꣂ)

for each p in P

Calculator(CP[p]) //Theo công thức (3.9)

endfor

Cost=min(CP[p])

Selectedroute=routeset[p]

return(Selectedroute, Cost)

3.2.3 Đánh giá hiệu năng

Các kết quả mô phỏng cho thấy, khi số kết nối đầu-cuối thấp, cơ chế định

tuyến dựa trên số chặng (∝= 1) phát huy ưu điểm và luôn cho các tiêu chí

hiệu năng cao. Tuy nhiên, khi lưu lượng truyền trong mạng tăng lên, hiện

tượng xung đột và tắc nghẽn thường xuyên xảy ra với mức độ ngày càng

tăng. Khi đó, cơ chế định tuyến với số chặng bộc lộ hạn chế, dẫn đến các

hiệu năng bị suy giảm nhanh. Ngược lại, các cơ chế định tuyến dựa vào chất

lượng tuyến đường hay độ dài hàng đợi hoặc phối hợp giữa các tham số trên

sẽ phát huy ưu điểm. Kết quả cũng cho thấy, giao thức định tuyến MM-

AODV với bộ hệ số cân bằng (∝= ꢔ = ꣂ = 1/3) thu được các hiệu năng

tốt hơn so với các cơ chế định tuyến được mô phỏng.

3.3 Giao thức Q-AODV

3.3.1 Cách tiếp cận và ý tưởng thiết kế

Để có thể đảm bảo QoS cho các ứng dụng Multimedia-MANET, các điều

kiện ràng buộc về chất lượng dịch vụ cần được ánh xạ thành các tham số

định tuyến và tham gia vào quyết định lựa chọn tuyến đường. Khi có nhiều

hơn một tham số định tuyến có kiểu additive hoặc multiplicative tham giao

vào quá trình xác định tuyến đường, bài toán xác định tuyến đường tối ưu sẽ

có độ phức tạp NP. Để giải quyết vấn đề đó, luận án đề xuất một giao thức

định tuyến sử dụng hai tham số là băng thông (kiểu additive) và trễ (kiểu

minimum). Để đảm bảo giao thức định tuyến có thể tùy chỉnh và phù hợp

13

với các ứng dụng Multimedia-MANET khác nhau, luận án đề xuất một giao

thức định tuyến có thể hoạt động theo cả hai mô hình, như sau:

Mô hình thích nghi (Adaptive Model): Cung cấp tuyến đường có

băng thông và trễ tốt nhất

Mô hình cam kết (Admission Model): Cung cấp tuyến đường có băng

thông thỏa mãn điều kiện tối thiểu và có trễ tốt nhất.

3.3.2 Tham số định tuyến

Các tham số băng thông và trễ phản ánh một số đặc điểm cơ bản của một

tuyến đường trong mạng. Chúng ta có thể xem băng thông và trễ lần lượt như

độ rộng và chiều dài của một tuyến đường. Nói cách khác, bài toán định

tuyến cho các ứng dụng Multimedia-MANET nhằm mục đích tìm ra tuyến

đường trong mạng, thỏa mãn các ràng buộc về dài và rộng. Sử dụng các tham

số định tuyến băng thông và trễ như một phương thức thỏa hiệp giữa tốc độ

di chuyển và chiều dài của tuyến đường. Do đó, trong nghiên cứu này, hai

tham số định tuyến được chọn là băng thông (kiểu additive) và trễ (kiểu

minimum) đã được mô tả trong các Mục 2.2.2.1 và Mục 2.2.2.3.

3.3.3 Đặc tả giao thức

Q-AODV là một giao thức định tuyến theo yêu cầu. Tiến trình khám phá

tuyến đường bắt đầu với việc nút nguồn gửi quảng bá gói tin tìm đường

RREQ với phần tiêu đề đã được thay đổi như sau {Model-Flag, Bandwidth

Request, Bandwidth, Delay Request, Delay, AODV RREQ Header}. Sau đó,

những gói tin này sẽ được chuyển tiếp thông qua các nút trung gian để tới

nút đích. Một điểm khác so với phương thức gửi gói tin RREQ trong giao

thức AODV truyền thống là, tại mỗi nút trung gian, khi nhận được gói tin

RREQ, nút trung gian sẽ tiến hành thủ tục Quality-check, Hình 3.9 nhằm hai

mục đích: (1) Thực hiện loại bỏ ngay lập tức tuyến đường không thỏa mãn

điều kiện băng thông hoặc trễ theo yêu cầu. Điều này giúp giảm băng thông,

năng lượng tiêu thụ và chi phí định tuyến vào các hoạt động không cần thiết

và (2) Tính toán băng thông và trễ của tuyến đường. Băng thông và trễ của

mỗi liên kết được xác định dựa vào thông tin của gói Hello [46].

Sau khi hoàn thành thủ tục này, do có thể bị ảnh hưởng bởi nhiễu can

thiệp trong quá trình truyền dữ liệu, luận án đề xuất sử dụng hàm (Min-

14

Bandwidth) nhằm tính giới hạn trên băng thông toàn tuyến. Cuối cùng, nút

đích gửi định danh gói tin RREP với phần tiêu đề được sửa đổi {Bandwidth,

Delay, AODV RREP Header} đến nút nguồn. Sau khi nhận được tập các

tuyến đường ứng viên. Để xác định được tuyến đường thỏa mãn các điều

kiện ràng buộc, hàm tính chi phí tuyến đường được xác định như sau.

Gọi Delay(p) và Bandwidth(p), lần lượt là trễ đầu-cuối và băng thông, thu

được từ gói RREP. Hàm chi phí của tuyến p được tính như sau:

ꢽ꣚ꢑꣀꢧ

(꣛)

ꢸ꣓꣔꣕_ꢆ꣖ꢍ꣗꣘_ꢠ꣗ꢓꢕ꣙ꢉꢕ꣕ℎ_(ꢞ)

=

(3.10)

꣜ꣀꢣꢛ꣝ꢇꢛꢥꢢ

(꣛)

Đặt ꣞ và ꢸ꣓꣔꣕_ꢟ꣖꣕ lần lượt là tổng số tuyến đường và tập chi phí của các

tuyến đường ứng viên thỏa mãn điều kiện (1), chúng ta thu được:

ꢸ꣓꣔꣕_ꢆ꣖ꢍ꣗꣘_ꢠ꣗ꢓꢕ꣙ꢉꢕ꣕ℎ_(ꢀ)

ꢸ꣓꣔꣕_ꢆ꣖ꢍ꣗꣘_ꢠ꣗ꢓꢕ꣙ꢉꢕ꣕ℎ_(꣟)

⎧

⎪

.

ꢸ꣓꣔꣕_ꢟ꣖꣕ =

(3.11)

(3.12)

⎨

⎪

⎩

ꢸ꣓꣔꣕_ꢆ꣖ꢍ꣗꣘_ꢠ꣗ꢓꢕ꣙ꢉꢕ꣕ℎ_(꣠꣑ꢀ)

ꢸ꣓꣔꣕_ꢆ꣖ꢍ꣗꣘_ꢠ꣗ꢓꢕ꣙ꢉꢕ꣕ℎ_(꣠)

꣡ꢋ꣕ꢉꢎ꣗ꢍ꣢꣓꣣꣕꣖ = ꣤ꢉꢓ (ꢸ꣓꣔꣕_ꢟ꣖꣕)

Theo đó, tuyến đường tối ưu được xác định theo công thức (3.12). Hoạt

động của giao thức Q-AODV được mô tả bằng mã giả như sau:

Thuật toán 3.3: Thuật toán lựa chọn tuyến đường Q-AODV.

1

P=routeset(S,D)

2

// Công thức (3.12)

3

4

Cost=∞, Selectedroute={∅}

for each p in P

5

6

8

9

if Cost>Cost_Delay_Bandwidth(p) then

Cost=Cost_Delay_Bandwidth(p)

Selectedroute=routeset(p)

end if

10

11

end for

return (Selectedroute, Cost)

15

3.3.3 Đánh giá hiệu năng

Kết quả mô phỏng cho thấy, giao thức đề xuất Q-AODV hoạt động tốt

trong cả hai mô hình Adaptive và Admission. Để đánh giá hiệu quả của giao

thức đề xuất, các kịch bản mô phỏng với sự thay đổi về mức độ di động của

nút mạng theo cả hai mô hình Adaptive và Admission đã được thiết lập. Kết

quả cho thấy, giao thức đề xuất cải thiện các tiêu chí hiệu năng đáng kể so

với các giao thức truyền thống như AODV và DSR trong mô hình Adaptive.

Trong mô hình Admission, Q-AODV cải thiện các tiêu chí như tỷ lệ phân

phối gói tin, trễ và tải định tuyến tốt hơn so với mô hình Adaptive.

3.4 Kết luận Chương 3

Do cấu trúc mạng động, định tuyến là vấn đề chính trong mạng MANET.

Hiệu năng của MANET phục thuộc vào cấu trúc, vị trí triển khai, kiểu ứng

dụng mạng; thuộc tính và năng lực của nút mạng. Trong phần này, luận án

đã đề xuất ba giao thức định tuyến nhằm cải thiện hiệu năng cho ba cấu trúc

mạng cụ thể, gồm:

(1) Giao thức định tuyến A_WCETT cho mạng hoạt động đa kênh [J2];

(2) Giao thức MM-AODV cho các mạng MANET đa tham số [C2];

(3) Giao thức Q-AODV cho các ứng dụng Multimedia-MANET [J3].

Kết quả đánh giá và so sánh hiệu năng trong một số kịch bản cụ thể cho

thấy, các giao thức định tuyến đề xuất đều cải thiện hiệu năng so với các giao

thức định tuyến truyền thống của MANET.

CHƯƠNG 4: ĐỊNH TUYẾN NÂNG CAO TUỔI THỌ MẠNG MANET

Tóm tắt: Trong chương này, luận án đề xuất 02 giải pháp nhằm tích hợp,

mở rộng để đem đến những năng lực và khả năng mới cho MANET, cụ thể

như sau: (1) Giải pháp nâng cao tuổi thọ MANET, mà cụ thể là đề xuất giao

thức định tuyến tiết kiệm năng lượng AERP [J4]. Dựa trên AERP, luận án

tiếp tục đề xuất giao thức định tuyến HPLR, cải tiến từ AERP nhằm sử dụng

năng lượng hiệu quả và cải thiện hiệu năng cho MANET [C4] và (2) Cơ chế

hợp tác giữa các máy chủ cho mạng Cloud-assited MANET [C3].

16

4.1 Định tuyến tiết kiệm năng lượng

4.1.1 Giới thiệu

Định tuyến tiết kiệm năng lượng là một trong những điều kiện quan trọng

nhất khi thiết kế giao thức định tuyến cho mạng MANET. Do các nút mạng

di động sử dụng pin với mức năng lượng lưu trữ giới hạn. Một nút mạng khi

hết năng lượng không chỉ ảnh hưởng đến chính nó mà còn ảnh hưởng đến

khả năng chuyển tiếp gói tin của những nút khác cũng như hiệu năng và tuổi

thọ của toàn hệ thống. Một hướng tiếp cận quan trọng là phân phối tải. Mục

tiêu chính của phân phối tải là cân bằng việc sử dụng năng lượng giữa các

nút và tối đa hóa tuổi thọ mạng bằng cách tránh sử dụng các nút có mức năng

lượng thấp khi lựa chọn tuyến đường trong quá trình định tuyến [27], [34].

Trong phần này, luận án đề xuất:

(1) Giao thức định tuyến AERP nhằm cải thiện hiệu quả sử dụng năng

lượng cho mạng MANET.

(2) Giao thức định tuyến HPLR, trên cơ sở cải tiến từ giao thức AERP

nhằm cải thiện tuổi thọ và đảm bảo hiệu năng mạng MANET.

4.1.2 Giao thức định tuyến AERP

4.1.2.1 Mô tả giao thức

Hình 4.2. Thủ tục Energy-check.

17

Giống như AODV, giao thức AERP hoạt động với tiến trình xác định

tuyến đường của AODV mở rộng. Tiến trình khám phá tuyến đường bắt đầu

với việc nút nguồn gửi quảng bá gói tin tìm đường RREQ với phần tiêu đề

được bổ sung hai trường mới {Total Remaining Energy, Min Remaining

Energy, AODV RREQ}. Một điểm khác so với phương thức chuyển tiếp gói

tin RREQ truyền thống của AODV là tại mỗi nút trung gian, khi nhận được

gói tin RREQ, nút này sẽ thực hiện một thủ tục, được đặt tên là Energy-check

như mô tả trong Hình 4.2.

4.1.2.2 Tham số định tuyến và lựa chọn tuyến đường

Để tính chi phí của của tuyến đường ꢋ ∈ ꣏ có số chặng h, luận án đề xuất

công thức tính dựa trên tổng mức năng lượng tiêu thụ (TCE) như sau:

ꢩ

ꢫ

ꢢꢻꢀ

ꢇꢾꢀ

∑

ꢙꢸꢘ =

(1 −

)

(4.1)

ꢩ

ꢳꢴꢵ

Trong đó: ꢘ_ꢇlà năng lượng còn lại của nút i, ꢘ_ꢒꣀꣁlà năng lượng khởi tạo

ban đầu của mỗi nút và ℎ là số chặng.

Tuy nhiên, công thức (4.1) có điểm hạn chế là không loại bỏ được tuyến

có tổng năng lượng toàn tuyến cao nhất nhưng lại chứa nút có mức năng

lượng sắp cạn kiệt. Do đó, tuổi thọ mạng có thể ngắn hơn. Để giải quyết vấn

đề này, luận án định nghĩa hàm chi phí AERP như sau:

+ ꣦1 − ^ꢒꢇꢣꢹ_ꢩꢼ꣧

(4.2)

ꢩ

ꢪꢡꢩ

ꢢꢻꢀ

ꢰ

ꢶꢘ꣥꣏ =

ꢳꢴꢵ

ꢀꢿꢈꢿꢢ

Bằng cách đưa tham số mức năng lượng thấp nhất vào trong công thức

(4.2), có thể xem là nỗ lực để cân bằng sự ảnh hưởng giữa tổng năng lượng

của toàn tuyến và năng lượng thấp nhất trong tuyến.

Bảng 4.1. Minh họa phương thức tính AERP.

ꢒꢇꢣ

ꢘ

ꢙꢸꢘ

ꢈ

1 −

꣨

꣩

Tuyến h+1

ꢶꢘ꣥꣏

ꢘ_ꢒꣀꣁ

ℎ + 1

ꢀꢿꢈꢿꢢ

1

2

3

4

0.65

0.38

0.36

0.56

0.80

0.50

0.60

1.45

0.88

0.86

1.16

5

18

Bảng 4.1 minh họa phương pháp tính giá trị AERP theo công thức (4.2).

Kết quả cho thấy tuyến số 3 (AERP = 0.86) sẽ được chọn để truyền dữ liệu.

4.1.3 Giao thức định tuyến HPLR

Để cân bằng vấn đề cải thiện hiệu năng cũng như tuổi thọ của MANET,

luận án đề xuất giao thức định tuyến HPLR, cải tiến từ giao thức AERP (Mục

4.1.2) với trọng tâm là cải tiến thuật toán để có thể chọn tuyến đường có độ

trễ thấp và cải thiện tuổi thọ mạng cao.

4.1.3.1 Thuật toán chọn tuyến đường

Không giống như thuật toán lựa chọn tuyến đường của AERP, trong

HPLR, sau khi xác định được tập tuyến đường ứng viên, nút nguồn sẽ thực

hiện một thuật toán chọn ra tuyến đường phù hợp với hai ràng buộc sau:

1) Để đảm bảo tính hiệu quả của thuật toán, luận án áp dụng một kỹ thuật

được đề xuất gần đây nhằm giới hạn số tuyến ứng viên [3]. Chỉ những ứng

viên có số hopcount nằm trong khoảng [꣪꣓ꢋꢎꢉꢓ, ꣪꣓ꢋꢎ꣗꣫] mới được xem

xét. Trong đó, ꣪꣓ꢋꢎꢉꢓ, là số chặng của tuyến đường ứng viên ngắn nhất

giữa cặp nút nguồn-đích (S, D) và ꣪꣓ꢋꢎ꣗꣫ được xác định như sau:

꣪꣓ꢋꢎ꣗꣫ = ꣪꣓ꢋꢎꢉꢓ + 2

(4.3)

Về lý thuyết, ꣪꣓ꢋꢎ꣗꣫ = ꣪꣓ꢋꢎꢉꢓ + ε, trong đó, ε là một số thực dương.

Tuy nhiên, với rất nhiều thực nghiệm cũng như khảo sát một số nghiên cứu

khác, nghiên cứu sinh nhận thấy giá trị ε = 2 là phù hợp. Kết quả là, kỹ thuật

này nhằm giới hạn số hữu hạn các tuyến đường cần xem xét. Nói cách khác,

nó ngầm ưu tiên các tuyến đường có độ trễ thấp.

2) Để thu được các tuyến đường ứng viên giàu năng lượng hơn, hàm chi

phí HPLR được định nghĩa như sau:

ꢒꢇꢣ

ꢘ

ꢙꢸꢘ

ꢈ

꣪꣏꣌꣥ = ꢔ ×

+ (1 − ꢔ) × ꣦1 −

꣨

꣩꣧

(4.4)

ℎ + 1

ꢘ_ꢒꣀꣁ

ꢀꢿꢈꢿꢢ

Trong đó, ꢔ là hệ số cân bằng, có giá trị trong khoảng [0,1]. Có hai cách

để hiểu công thức (4.4). Trước hết, chúng ta có thể coi đó là sự cân bằng giữa

tổng dung lượng pin còn lại của cả tuyến và dung lượng pin nhỏ nhất còn lại.

Thứ hai, nó cho thấy mối quan hệ giữa các nút có ảnh hưởng nhất với các

nút khác trong tuyến. Nói cách khác, đây chính là sự thực thi chính sách ưu

tiên đối với các nút có mức năng lượng cạn kiệt. Chi tiết thuật toán lựa chọn

tuyến đường được mô tả bởi mã giả.