Nghiên cứu kỹ thuật định tuyến đa đường hiệu quả, tin cậy và tiết kiệm năng lượng trên cơ sở cải tiến giao thức AOMDV

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Nguyễn Kiên Giang

NGHIÊN CỨU KỸ THUẬT ĐỊNH TUYẾN ĐA ĐƯỜNG

HIỆU QUẢ, TIN CẬY VÀ TIẾT KIỆM NĂNG LƯỢNG

TRÊN CƠ SỞ CẢI TIẾN GIAO THỨC AOMDV

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2020

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Nguyễn Kiên Giang

NGHIÊN CỨU KỸ THUẬT ĐỊNH TUYẾN ĐA ĐƯỜNG

HIỆU QUẢ, TIN CẬY VÀ TIẾT KIỆM NĂNG LƯỢNG

TRÊN CƠ SỞ CẢI TIẾN GIAO THỨC AOMDV

Ngành: Khoa học máy tính

Mã số: 9480101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS. TS. NGUYỄN VĂN TAM

Thái Nguyên - 2020

LỜI CẢM ƠN

Sau thời gian học tập và rèn luyện tại Trường Đại học Công nghệ thông tin

và Truyền thông – Đại học Thái Nguyên, bằng sự biết ơn và kính trọng, tôi xin

gửi lời cảm ơn chân thành đến Ban Giám hiệu, Phòng Đào tạo và Khoa Công nghệ

thông tin thuộc Trường Đại học Công nghệ thông tin và Truyền thông – Đại học

Thái Nguyên cùng các thầy, cô giáo đã nhiệt tình hướng dẫn, giảng dạy và tạo mọi

điều kiện thuận lợi giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu và hoàn

thiện luận văn này.

Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Nguyễn Văn Tam,

người thầy đã trực tiếp hướng dẫn, giúp đỡ em trong quá trình thực hiện đề tài.

Xin chân thành cảm ơn gia đình, bạn bè cùng đồng nghiệp đã tạo điều kiện

sát, nghiên cứu để hoàn thành đề tài này.

Tuy nhiên điều kiện về năng lực bản thân còn hạn chế, luận văn chắc chắn

không tránh khỏi những thiếu sót. Kính mong nhận được sự đóng góp ý kiến của

các thầy cô giáo, bạn bè và đồng nghiệp để luận văn của tôi được hoàn thiện hơn.

Xin trân trọng cảm ơn!

Thái Nguyên, ngày … tháng …. năm 2019

Học viên

Nguyễn Kiên Giang

MỤC LỤC

DANH MỤC CÁC TỪ VIẾT TẮT .......................................................................1

MỞ ĐẦU................................................................................................................3

CHƯƠNG 1. MẠNG AD HOC DI ĐỘNG VÀ ĐỊNH TUYẾN ĐA ĐƯỜNG....6

1.1. Tổng quan về mạng ad hoc di động ............................................................6

1.1.1. Định nghĩa mạng ad hoc di động .........................................................6

1.1.2. Đặc điểm của mạng ad hoc di động.....................................................7

1.1.3. Ứng dụng của mạng MANET..............................................................9

1.1.3.1. Ứng dụng trong quân đội ..................................................................9

1.3.1.2. Các ứng dụng trong cuộc sống........................................................10

1.3.1.3. Mạng cảm biến................................................................................12

1.3.1.4. Mạng Rooftop .................................................................................12

1.3.1.5. Mở rộng phạm vi của điểm truy cập...............................................13

1.2. Giao thức định tuyến đa đường AOMDV.................................................14

1.2.1. Tổng quan về giao thức AOMDV......................................................14

1.2.2. Vấn đề chống định tuyến lặp .............................................................15

1.2.3. Các đường tách biệt............................................................................18

1.2.4. Bảng định tuyến .................................................................................24

1.2.5. Thuật toán cập nhật đường.................................................................25

1.2.6. Tiến trình khám phá đường................................................................27

1.2.7. Cơ chế bảo trì đường..........................................................................30

1.2.8. Cơ chế chuyển tiếp dữ liệu.................................................................31

1.3. Một số nghiên cứu cải tiến giao thức AOMDV........................................31

1.5. Tổng kết chương 1 ....................................................................................34

CHƯƠNG 2. KỸ THUẬT ĐỊNH TUYẾN ĐA ĐƯỜNG HIỆU QUẢ, TIN CẬY

VÀ TIẾT KIỆM NĂNG LƯỢNG CỦA GIAO THỨC ĐỊNH TUYẾN E2E￾LREEMR..............................................................................................................36

2.1. Xây dựng độ đo định tuyến.......................................................................36

2.2. Cơ chế hoạt động.......................................................................................38

2.3. Xác định năng lượng còn lại và năng lượng còn lại tối thiểu...................39

2.4. Xác định năng lượng truyền dự kiến.........................................................41

2.5. Xác định tổng năng lượng truyền dự kiến ................................................42

2.6. Xác định số lần truyền dự kiến .................................................................43

2.7. Xác định tổng số lần truyền dự kiến .........................................................45

2.8. Chọn đường dựa trên CETX và CETE .....................................................45

2.9. Tổng kết Chương 2 ...................................................................................48

CHƯƠNG 3. MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG GIAO THỨC........50

3.1. Thiết lập môi trường mô phỏng ................................................................50

3.2. Độ đo hiệu năng ........................................................................................51

3.3. Kết quả mô phỏng và đánh giá..................................................................53

3.3.1. Tỷ lệ mất gói ......................................................................................53

3.3.2. Chi phí định tuyến chuẩn hoá ............................................................54

3.3.3. Tổng năng lượng tiêu thụ...................................................................56

3.3.4. Thông lượng.......................................................................................57

3.3.5. Tỷ lệ truyền thành công .....................................................................58

3.3.6. Chi phí định tuyến..............................................................................59

3.3.7. Trễ đầu cuối trung bình......................................................................60

3.4. Tổng kết Chương 3 ...................................................................................62

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN...........................................................63

TÀI LIỆU THAM KHẢO....................................................................................65

1

DANH MỤC CÁC TỪ VIẾT TẮT

Từ viết tắt Tiếng Anh Nghĩa tiếng Việt

ADSL Asymmetric Digital

Subscriber Line

Đường thuê bao số bất đối

xứng

AODV Ad hoc On demand

Distance Vector

Giao thức định tuyến theo yêu

cầu dạng vector khoảng cách

dành cho mạng ad hoc

AOMDV Ad hoc On demand

Multipath Distance Vector

Giao thức định tuyến AODV đa

đường

CETE Cumulative Expected

Transmission Energy

Tổng năng lượng truyền dự

kiến của đường

CETX Cumulative Expected

Transmission Count

Tổng số lần truyền dự kiến của

đường

DA Destination Address Địa chỉ đích

DoS Denial-of-Service Tấn công từ chối dịch vụ

DSR Dynamic Source Routing Giao thức định tuyến nguồn

động

E2E￾LREEMR

End-to-End Link Reliable

Energy Efficient Multipath

Routing

Giao thức định tuyến đa đường

có liên kết đầu cuối tin cậy và

tiết kiệm năng lượng

ETE Expected Transmission

Energy

Năng lượng truyền dự kiến

ETX Expected Transmission

Count

Số lần truyền dự kiến

ISP Internet Serive Provider Nhà cung cấp dịch vụ Internet

LET Link Expiration Time Thời gian hết hạn liên kết

LPU Local Path Update Cập nhật đường nội bộ

2

LR-EE￾AOMDV

Link Reliable Energy

Efficient AOMDV

Giao thức định tuyến AOMDV

cải tiến độ tin cậy liên kết và

năng lượng sử dụng

MANET Mobile Ad hoc Network Mạng ad hoc di động

MDSDV Modified Destination￾Sequenced Distance￾Vector

Giao thức định tuyến DSDV cải

tiến

MP-DSR Multipath Dynamic

Source Routing

Giao thức định tuyến DSR đa

đường

MP-OLSR Multipath Optimized Link

State Routing Protocol

Giao thức định tuyến OLSR đa

đường

MRE Minimal Residual Energy Năng lượng còn lại tối thiểu

NS-2 Network Simulator

version 2

Phần mềm mô phỏng mạng NS

phiên bản 2

OLSR Optimized Link State

Routing Protocol

Giao thức định tuyến tối ưu

trạng thái đường liên kết

OMMRE￾AOMDV

Optimized Minimal

Maximal nodal Residual

Energy AOMDV

Giao thức định tuyến AOMDV

tối ưu năng lượng nút mạng

QoS Quality of Service Chất lượng dịch vụ

RREP Route Reply Gói tin trả lời đường

RREQ Route Request Gói tin yêu cầu tìm đường

RRER Route Error Gói tin báo lỗi đường

RSSI Received Signal Strength

Indicators

Chỉ số độ mạnh tín hiệu nhận

được

SA Source Addrress Địa chỉ nguồn

ZRP Zone Routing Protocol Giao thức định tuyến vùng