Luận văn Nghiên cứu chiến lược bảo trì thông tin định tuyến trong mạng AD HOC phân cụm
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Hoàng Xuân Giang
NGHIÊN CỨU CHIẾN LƯỢC BẢO TRÌ THÔNG TIN
ĐỊNH TUYẾN TRONG MẠNG AD HOC PHÂN CỤM
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
Hoàng Xuân Giang
NGHIÊN CỨU CHIẾN LƯỢC BẢO TRÌ THÔNG TIN
ĐỊNH TUYẾN TRONG MẠNG AD HOC PHÂN CỤM
Ngành: Khoa học máy tính
Mã số: 8480101
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 2020
Học viên
Hoàng Xuân Giang
MỤC LỤC
MỞ ĐẦU........................................................................................................... 1
PHÂN CỤM...................................................................................................... 4
1.5. Tổng kết Chương 1 .............................................................................. 18
3.2.4. Chi phí điều khiển......................................................................... 43
3.5. Tổng kết Chương 3 .............................................................................. 52
1
MỞ ĐẦU
Được hình thành bởi các kết nối tạm thời giữa các nút mạng di động không
có sự hỗ trợ của cơ sở hạ tầng mạng cố định, mạng ad hoc di động (MANET)
có nhiều những đặc điểm khác biệt so với mạng không dây và có dây truyền
thống làm nảy sinh nhiều thách thức và các hướng nghiên cứu khác nhau: vấn
đề định tuyến hiệu quả khi topo mạng thay đổi, đảm bảo chất lượng dịch vụ
theo yêu cầu từ chương trình ứng dụng, đảm bảo an ninh mạng, tiết kiệm năng
lượng, khả năng tự tổ chức, chuyển đổi các dịch vụ từ mô hình client-server và
đảm bảo hiệu năng kích thước mạng thay đổi. Kết quả của nghiên cứu phân
loại và đánh giá về số lượng các nghiên cứu theo các hướng khác nhau đối với
mạng MANET trong thời gian gần đây cho thấy, hướng nghiên cứu về định
tuyến trong mạng MANET đứng đầu về số lượng các nghiên cứu đã được công
bố. Như vậy, có thể khẳng định, định tuyến trong mạng MANET đã và đang là
một vấn đề rất cần được quan tâm giải quyết trong những nghiên cứu cải tiến
hiệu năng mạng MANET.
Phân cụm là một chiến lược hiệu quả để giải quyết tính động và khả năng
mở rộng của mạng ad hoc di động có quy mô lớn. Các giao thức định tuyến
theo cụm có khả năng mở rộng tốt hơn các giao thức định tuyến phẳng vì kỹ
thuật phân cụm làm giảm kích thước của bảng định tuyến và chi phí cần thiết
để duy trì thông tin định tuyến. Phân cụm có thể làm tăng tính sẵn sàng của
thông tin trong mạng, chẳng hạn như vị trí của các nút di động, bằng cách nhân
bản thông tin tới các nút trong các cụm khác nhau. Khi triển khai truyền thông
quảng bá hoặc truyền thông đa điểm, kỹ thuật phân cụm cho phép lan truyền
thông tin một cách có chọn lọc để giảm các gói tin quảng bá dư thừa. Hơn nữa,
việc phân cụm sẽ tạo hỗ trợ cho việc quản lý tài nguyên một cách hiệu quả bằng
2
cách kiểm soát được việc chia sẻ và tiết kiệm tài nguyên nhằm đáp ứng các yêu
cầu QoS của ứng dụng.
Đã có những nghiên cứu đề xuất các kỹ thuật phân cụm trong mạng ad
hoc, chẳng hạn như sử dụng tập quản lý cụm, phân cụm phân tán, phân cụm
trên cơ sở tín hiệu và trên cơ sở vị trí. Các nghiên cứu này tập trung vào việc
xây dựng các cụm để quản lý sự di động của nút hoặc tối ưu hóa sức mạnh/chi
phí của các nút quản lý cụm. Trong đề tài này, mạng ad hoc được giả định là
đã được phân cụm. Đề tài tập trung nghiên cứu các kỹ thuật và chiến lược khác
nhau để triển khai một tầng con phía trên thực hiện nhiệm vụ bảo trì và quản lý
trạng thái động của các cụm, bao gồm trạng thái các nút và dữ liệu/tệp sẵn sàng,
kết nối mạng, băng thông, khả năng xử lý và những thông tin khác. Ý tưởng
của các đề xuất được nghiên cứu trong đề tài là nhằm ẩn đi tính động của các
cụm để cải thiện hiệu năng của các ứng dụng trong mạng MANET phân cụm.
Duy trì trạng thái của các cụm liên quan đến hai hoạt động chính: thu thập
và phân phối thông tin. Trong giai đoạn thu thập, các nút mạng sẽ thu thập
thông tin trạng thái cục bộ trong cụm và trong giai đoạn phân phối, thông tin
được chia sẻ với các cụm khác. Vấn đề bảo trì là một thách thức trong mạng
MANET vì tính di động của các nút, trạng thái của các cụm có thể thường
xuyên thay đổi dẫn đến tăng chi phí thực hiện các hoạt động thu thập và phân
phối. Một chiến lược bảo trì tốt sẽ cân bằng giữa khối lượng các công việc và
mức tiêu thụ năng lượng của các nút, tối thiểu hoá chi phí và theo dõi các thay
đổi một cách kịp thời và chính xác.
Để quản lý bất kỳ thông tin trạng thái nào, một giao thức duy trì cần thực
hiện các hoạt động thu thập và phân phối. Trong đề tài này, để không mất tính
tổng quát, kết nối logic giữa các cụm được xem là thông tin trạng thái. Hai cụm
là có kết nối nếu chúng liền kề nhau và có thể định tuyến trực tiếp các thông
3
điệp với nhau qua một nút biên. Có thể mô hình hóa các cụm và kết nối giữa
chúng như là một lớp bao phủ trên mạng MANET ban đầu, với mỗi cụm là một
đỉnh và mỗi kết nối của chúng là một cạnh.
Một cách tiếp cận đơn giản để giải quyết vấn đề duy trì trạng thái trong
mạng MANET phân cụm là giao nhiệm vụ duy trì cho các nút quản lý cụm.
Điều này liên quan đến việc duy trì thông tin của các cụm lân cận và chia sẻ
thông tin với các đầu quản lý cụm khác. Các nút quản lý cụm thường có nhiệm
vụ xử lý các yêu cầu định tuyến liên cụm cho các nút trong cụm của mình. Các
nút khác trong cụm chỉ cần duy trì đường tới nút quản lý của chúng.
Mục đích của đề tài này là nghiên cứu một số chiến lược bảo trì thông tin
định tuyến trong mạng MANET phân cụm nhằm nâng cao hiệu quả định tuyến.
Các chiến lược này cũng được so sánh, đánh giá về mức độ hiệu quả so với một
số chiến lược đã đề xuất khác bằng cách sử dụng phần mềm mô phỏng.
Cấu trúc luận văn được trình bày như sau: Chương 1 trình bày tổng quan
về mạng MANET và vấn đề định tuyến trong mạng MANET phân cụm. Một
số chiến lược bảo trì thông tin định tuyến trong mạng MANET phân cụm được
trình bày và phân tích chi tiết trong chương 2. Kết quả của việc cài đặt, mô
phỏng, so sánh đánh giá hiệu hiệu quả của một số chiến lược bảo trì thông tin
định tuyến trong mạng MANET phân cụm được trình bày trong Chương 3. Nội
dung tổng kết và hướng phát triển của đề tài được đưa ra trong phần kết luận.
4
CHƯƠNG 1. TỔNG QUAN VỀ ĐỊNH TUYẾN TRONG
MẠNG MANET PHÂN CỤM
1.1. Tổng quan về mạng MANET
1.1.1. Khái niệm mạng MANET
Mạng MANET (Mobile Ad hoc Network) [11] là một tập các nút không
dây di động có thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ
của trạm cơ sở cố định hoặc mạng có dây. Mỗi nút di động có một phạm vi
truyền giới hạn, do đó chúng cần sự trợ giúp của các nút láng giềng để chuyển
tiếp các gói dữ liệu. Hình 1.1 minh họa một mạng MANET. Trong ví dụ này,
các gói tin từ nút nguồn là một máy tính cần chuyển tới một nút đích là một
điện thoại thông minh không nằm trong phạm vi truyền của nút nguồn. Vì vậy,
cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin từ nút nguồn
tới nút đích. Để thực hiện được công việc này, các nút mạng phải sử dụng giao
thức định tuyến phù hợp cho mạng MANET.
Hình 1.1. Một ví dụ của mạng MANET
Thuật ngữ “Ad hoc” áp dụng cho mạng không dây mô tả một mạng không
có cơ sở hạ tầng cố định, trong đó hình trạng mạng được tạo thành bởi chính
các nút mạng. Chế độ “Ad hoc” của chuẩn IEEE 802.11 hoạt động theo mô
5
hình này, mặc dù nó chỉ hỗ trợ để thiết lập một mạng đơn chặng. Các mạng di
động không dây kiểu không cấu trúc (MANET) đã mở rộng khái niệm “Ad
hoc” đa chặng theo nghĩa: một nút mạng có thể định tuyến và chuyển tiếp một
gói tin nó nhận được từ một nút mạng khác. Nói cách khác, con đường chuyển
tiếp gói tin từ nút nguồn tới nút đích có thể chứa các nút trung gian khác. Các
nút trung gian sẽ đọc thông tin trong phần header của các gói tin dữ liệu và
chuyển tiếp chúng tới chặng kế tiếp trên một con đường đã được hình thành.
Các nút trong mạng MANET thông thường sẽ kết nối với nhau trong một
khoảng thời gian để trao đổi thông tin. Trong khi trao đổi thông tin, các nút này
vẫn có thể di chuyển, do đó, mạng này phải đáp ứng được yêu cầu truyền dữ
liệu trong khi hình trạng mạng có thể thay đổi liên tục. Các nút mạng phải có
cơ chế tự tổ chức thành một mạng để thiết lập các đường truyền dữ liệu mà
không cần sự hỗ trợ từ bên ngoài. Trong mô hình này, mỗi nút mạng có thể
đóng vai trò là một nút đầu cuối để chạy các chương trình ứng dụng của
người sử dụng hoặc là một bộ định tuyến để chuyển tiếp các gói tin cho các
nút mạng khác.
1.1.2. Đặc điểm của mạng MANET
Do MANET là một mạng không dây hoạt động không cần sự hỗ trợ của
hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị di động
vừa đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến nên mạng
MANET còn có một số đặc điểm nổi bật sau:
Cấu trúc động: Do tính chất di chuyển ngẫu nhiên của các nút mạng nên cấu
trúc của loại mạng này cũng thường xuyên thay đổi một cách ngẫu nhiên ở
những thời điểm không xác định trước. Trong khi thay đổi, cấu trúc của
mạng MANET có thêm hoặc mất đi các kết nối hai chiều hoặc kết nối một
chiều.
6
Chất lượng liên kết hạn chế: Các liên kết không dây thường có băng thông
nhỏ hơn so với các liên kết có dây. Ngoài ra, do ảnh hưởng của cơ chế đa
truy cập, vấn đề suy giảm tín hiệu, nhiễu và các yếu tố khác, băng thông
thực của các liên kết không dây thường thấp hơn nhiều so với tốc độ truyền
tối đa theo lý thuyết của môi trường truyền không dây.
Các nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng MANET
có thể là một bộ cảm biến, một điện thoại thông minh hoặc một máy tính
xách tay. Thông thường các thiết bị này có tài nguyên hạn chế so với các
máy tính trong mạng có dây và không dây truyền thống về tốc độ xử lý,
dung lượng bộ nhớ và năng lượng nguồn pin nuôi sống hoạt động của nút.
Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường chịu tác
động về mặt vật lý từ các nguồn gây nguy hại về an ninh nhiều hơn so với
mạng có dây. Về khía cạnh vật lý, các kỹ thuật gây mất an ninh và bảo mật
trong mạng như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ
triển khai trong mạng MANET hơn là trong mạng có dây truyền thống.
Có thể thấy những đặc điểm này là các yếu tố ảnh hưởng rất nhiều đến
hiệu năng của mạng MANET. Để có thể triển khai được mạng MANET trong
thực tế, các thiết kế mạng MANET phải giải quyết được những thách thức sinh
ra do những đặc điểm đã nêu trên của mạng MANET. Những thách thức này
gồm các vấn đề kỹ thuật như khả năng truyền dữ liệu và định tuyến hiệu quả
khi kích thước mạng thay đổi; đảm bảo chất lượng dịch vụ (QoS) cho các
chương trình ứng dụng; cơ chế chuyển đổi một số dịch vụ từ mô hình client-
server; tiết kiệm năng lượng pin để kéo dài thời gian hoạt động của các nút
mạng riêng lẻ và của toàn mạng; đảm bảo an ninh mạng; khả năng hợp tác giữa
các nút mạng và khả năng tự tổ chức của mạng;
7
1.1.3. Ứng dụng của mạng MANET
Ngày nay, mạng MANET có nhiều những ứng dụng trong đời sống, kinh
tế, xã hội của con người. Mô hình mạng này phù hợp đối với những tình huống
cần triển khai hệ thống mạng một cách nhanh chóng, linh động và thường xuyên
có sự biến đổi trong cấu trúc mạng. Ngày nay, mạng MANET được ứng dụng
trong rất nhiều lĩnh vực từ các ứng dụng trong thương mại tới các ứng dụng
trong các hoạt động quân sự, ứng dụng trong các hoạt động khẩn cấp, ứng dụng
trong gia đình, văn phòng và giáo dục, mạng giao thông và mạng cảm biến.
Đối với các ứng dụng của mạng MANET trong thương mại, những người
dùng có thể chia sẻ dữ liệu giữa các thiết bị di động trong một cuộc họp hay hội
thảo mà không cần sự hỗ trợ của một cơ sở hạ tầng mạng cố định. Các máy tính
của những cá nhân có thể kết nối với nhau để tạo thành một mạng tạm thời phục
vụ cho các ứng dụng truyền thông dữ liệu trong một nhóm những người dùng
mà không cần sự hiện diện của các bộ thu phát tập trung. Kết nối Internet từ
một thiết bị của một người dùng cũng có thể được chia sẻ tới các thiết bị của
những người dùng khác thông qua mạng MANET.
Ứng dụng mạng MANET trông quân đội là một trong những ý tưởng
được đưa ra ngay từ khi mạng MANET được phát triển. Trong mô hình chiến
đấu của quân đội trên chiến trường không có sự hỗ trợ về hạ tầng mạng cố định,
mỗi người lính hoặc một phương tiện quân sự như xe tăng, máy bay, tàu chiến,
tàu thủy đều có thể được kết nối và trao đổi thông tin tạm thời với nhau hoặc
với trạm chỉ huy một cách linh động thông qua mạng MANET được hình thành
bởi kết nối giữa các thiết bị di động truyền thông không dây được gắn vào các
phương tiện quân sự hay những người lính tham gia vào cuộc chiến.
Tại các vùng bị thiên tai, thảm họa, có thể tất cả các phương tiện và hạ
tầng truyền thông được xây dựng trước đó đều bị phá hủy hoàn toàn. Mỗi chiếc
8
xe của cảnh sát, cứu hỏa, cứu thương,… có thể được trang bị các thiết bị truyền
nhận không dây để trở thành một thiết bị đầu cuối di động và là một phần của
mạng MANET. Mỗi nhân viên cứu hộ cũng có thể cũng mang theo một thiết bị
đầu cuối di động. Các thiết bị đầu cuối này đều liên kết với nhau, hình thành
nên một mạng MANET tạm thời nhằm trao đổi thông tin. Cấu hình mạng thay
đổi theo những thời điểm khác nhau. Ngoài ra, các thiết bị đầu cuối di động
không chỉ cung cấp chức năng gửi và nhận thông tin mà còn có thể chuyển tiếp
thông tin như vai trò như các bộ định tuyến.
Mỗi thiết bị thông minh trong gia đình, các điên thoại di động thông minh
và máy tính của những người sử dụng trong văn phòng, trong môi trường
trường học, các lớp học có thể đóng vai trò như một nút mạng trong một mạng
MANET được hình thành tạm thời mà không cần sự hỗ trợ của hạ tầng mạng
cố định nhằm phục vụ cho các ứng dụng chia sẻ thông tin, truyền dữ liệu
multimedia, quản lý ngôi nhà thông minh, quản lý lớp học thông minh,…
Trong vấn đề quản lý và hỗ trợ giao thông, mỗi phương tiện giao thông
là một nút mạng di động trong mạng MANET được hình thành tạm thời trên
một khu vực địa lý nhằm hỗ trợ trao đổi và quản lý các thông tin về tình trạng
giao thông, hỗ trợ tìm đường tránh tắc nghẽn giao thông, theo dõi và quản lý
các thiết bị tham gia giao thông, v.v.
Cảm biến là các thiết bị nhỏ, phân tán, giá thành thấp, tiết kiệm năng
lượng, có khả năng truyền thông không dây và xử lý cục bộ. Một mạng MANET
có thể là một mạng cảm biến gồm các nút cảm biến. Các nút này hợp tác với
nhau để cùng thực hiện một nhiệm vụ cụ thể, ví dụ như: giám sát môi trường
(không khí, đất, nước), theo dõi môi trường sống, hành vi, dân số của các loài
động, thực vật, dò tìm động chấn, theo dõi tài nguyên, thực hiện trinh thám
trong quân đội,...
9
1.2. Vấn đề bảo trì thông tin định tuyến trong mạng MANET phân cụm
Phân cụm là một chiến lược hiệu quả để giải quyết tính động và khả năng
mở rộng của mạng ad hoc di động (MANET) [2]. Theo [1], các giao thức định
tuyến trên cơ sở phân cụm có khả năng mở rộng hơn so với các giao thức định
tuyến phẳng, vì việc phân cụm làm giảm kích thước của bảng định tuyến và chi
phí định tuyến cần thiết để bảo trì thông tin định tuyến. Phân cụm có thể làm
tăng tính sẵn sàng của thông tin mạng, chẳng hạn như vị trí của các nút di động,
bằng cách sao chép thông tin giữa các nút trong các cụm khác nhau. Khi thực
hiện truyền thông tin kiểu quảng bá hoặc multicast, phân cụm cho phép cơ chế
lan truyền thông tin kiểu quảng bá một cách có chọn lọc để giảm các thông điệp
quảng bá dư thừa. Hơn nữa, việc phân cụm tạo cơ chế để quản lý tài nguyên
hiệu quả bằng cách chia sẻ và dự trữ tài nguyên có kiểm soát để đáp ứng các
yêu cầu chất lượng dịch vụ (QoS) của ứng dụng.
Đã có công trình nghiên cứu xem xét các kỹ thuật phân cụm khác nhau
trong mạng ad hoc [1], chẳng hạn như sử dụng tập quản lý, phân cụm phân tán,
cơ chế báo hiệu và dựa vào vị trí. Những nghiên cứu này chủ yếu tập trung vào
việc xây dựng các cụm để quản lý tính di động của nút hoặc tối ưu năng lượng
cũng như chi phí quản lý của các nút đầu cụm. Trong đề tài này, mạng được
giả định là đã được phân cụm để nghiên cứu các kỹ thuật triển khai một tầng
con có nhiệm vụ quản lý trạng thái động của các cụm, chẳng hạn như trạng thái
sẵn sàng của nút và dữ liệu/tệp có sẵn, kết nối mạng, băng thông, khả năng xử
lý và thông tin khác. Ý tưởng của đề tài này là nhằm che giấu tính động của các
cụm bên dưới, để cải thiện hiệu suất của các ứng dụng hoạt động trong mạng
MANET phân cụm.
Việc duy trì trạng thái của các cụm liên quan đến hai hoạt động chính là
thu thập và phân phối thông tin. Trong pha thu thập, các nút thu thập thông tin
trạng thái trong cụm nội bộ của nó. Trong pha phân phối, thông tin được chia
10
sẻ cho các cụm khác. Bảo trì là một vấn đề thách thức trong mạng MANET vì
tính di động của các nút làm thay đổi thường xuyên trạng thái của các cụm và
tăng chi phí thực hiện các hoạt động thu thập và phân phối thông tin. Một chiến
lược bảo trì tốt sẽ cân bằng tải công việc và mức tiêu thụ năng lượng của các
nút, tối thiểu hóa chi phí và lưu vết các thay đổi một cách kịp thời và chính xác.
Để quản lý thông tin trạng thái, một giao thức bảo trì cần thực hiện các
hoạt động thu thập và phân phối. Trong nghiên cứu này, để không mất tính tổng
quát, kết nối logic giữa các cụm được coi là thông tin trạng thái. Hai cụm được
xem là có kết nối, nếu chúng liền kề nhau và có thể định tuyến trực tiếp các
thông điệp với nhau thông qua một nút biên. Ta có thể mô hình hóa các cụm và
các kết nối giữa chúng như một lớp phủ trên mạng MANET ban đầu với các
cụm là các đỉnh và kết nối của chúng là các cạnh của lớp phủ.
Theo [1], một cách tiếp cận đơn giản để giải quyết bài toán bảo trì trạng
thái trong mạng MANET phân cụm là giao trách nhiệm bảo trì cho nút đầu
cụm. Trách nhiệm này liên quan đến việc duy trì thông tin của các cụm lân cận
và chia sẻ thông tin với các đầu cụm khác. Các nút đầu cụm thường chịu trách
nhiệm quản lý và xử lý các yêu cầu định tuyến liên cụm cho các nút cùng cụm
với nó. Khi đó, các nút khác trong cụm chỉ cần duy trì một con đường đến nút
đầu cụm của chúng. Đề tài này sẽ nghiên cứu kỹ nghiên cứu [1] đề xuấttriển
khai một chiến lược bảo trì mạng phủ phân cụm dựa trên nút đứng đầu, được
gọi là CWHO (Cluster-Based With Head Overlay). Đây là chiến lược cơ sở để
so sánh với các chiến lược bảo trì khác.
Trong thiết kế của các chiến lược bảo trì thông tin trong mạng MANET,
còn có những cách tiếp cận khác. Ngược lại với chiến lược CWHO, còn có một
chiến lược phân phối đầy đủ, không dựa vào các nút đứng đầu. Theo cách tiếp
cận phân tán đầy đủ, mọi nút đều chia sẻ trách nhiệm như nhau trong việc thu
11
thập và phân phối thông tin về các cụm lân cận của chúng. Theo phương pháp
này, mọi nút có thể xử lý các hoạt động định tuyến liên cụm, vì chúng chia sẻ
thông tin trạng thái của tất cả các cụm trong mạng. Do đó, đề tài này cũng
nghiên cứu về đề xuất [1]triển khai một chiến lược bảo trì thông tin định tuyến
trong mạng phủ phân cụm không có đứng đầu, được đặt tên là CWOHO
(Cluster- Based WithOut Head Overlay).
Hai chiến lược bảo trì ở trên có thể được sử dụng để chia sẻ thông tin
trạng thái cục bộ của các cụm với toàn bộ mạng. Cả hai đều có những ưu điểm
riêng, có thể khác nhau trong các điều kiện mạng khác nhau. Chiến lược CWHO
đơn giản và hoạt động tốt trong nhiều tình huống. Tuy nhiên, nó có thể gặp phải
các vấn đề như mất cân bằng tải và khả năng tiêu thụ năng lượng, nút đầu cụm
bị lỗi hoặc di chuyển và nút đầu cụm chịu tải lưu lượng truy cập bổ sung. Chiến
lược CWOHO có thể tránh được những vấn đề này, nhưng chi phí bảo trì có
thể cao.
Ở giữa hai cách tiếp cận trên, có những cách tiếp cận bảo trì thông tin
định tuyến khác. Một trong những cách tiếp cận này là chiến lược Phân cụm
với thông tin nút lân cận CNI (Clusters with Neighbor Information) [1]. Chiến
lược CNI thực hiện hoạt động thu thập thông tin một cách phân tán như trong
chiến lược CWOHO. Tuy nhiên, thông tin thu thập không được chia sẻ với toàn
bộ mạng. Các nút chỉ duy trì thông tin về các cụm lân cận của chúng. Với cách
tiếp cận này, nghiên cứu giả định rằng mọi nút đều có kiến thức trước về cấu
trúc kết nối mạng. Cấu trúc kết nối cho thấy hướng của các cụm và có thể xây
dựng được nó bằng cách sử dụng thuật toán phân tán hoặc sử dụng thông tin về
vị trí địa lý các nút trong mạng. Trong chiến lược CNI, việc định tuyến liên
cụm được thực hiện theo cách tiếp cận sử dụng quyết định định tuyến tại mỗi
cụm trung gian.
12
Một chiến lược bảo trì thông tin định tuyến cụ thể nào đó có thể không
áp dụng được cho tất cả các điều kiện và mô hình di động của mạng. Ví dụ: nếu
các nút di chuyển chậm trong mạng, thì chiến lược bảo trì với nút đầu cụm có
thể có hiệu suất tốt. Tuy nhiên, trong trường hợp mạng có tính cơ động cao, có
thể cần xem xét đến chiến lược bảo trì phân tán. Để hiểu tác động của tính di
động của nút, đề tài này sẽ đánh giá hiệu năng của ba chiến lược bảo trì ở trên
theo hai mô hình di động khác nhau, đó là mô hình Random Waypoint và
Manhattan Grid bằng phương pháp mô phỏng.
Các công việc sẽ được thực hiện trong đề tài này bao gồm: (a) Đưa ra
một nghiên cứu toàn diện về vấn đề bảo trì trạng thái trong các mạng MANET
phân cụm bằng cách triển khai thiết kế của chiến lược bảo trì với nút đầu cụm
CWHO. Đây là chiến lược phổ biến và được sử dụng rộng rãi nhất; (b) Triển
khai chiến lược bảo trì một cách gần nhất với cách tiếp cận phân phối đầy đủ,
được gọi là CWOHO. Trong CWOHO, các nút kết hợp thông tin từ tất cả các
nút biên để xác định khả năng kết nối của nó với các cụm lân cận. Thông tin
này sau đó được quảng bá để chia sẻ cho mọi nút trong mạng; (c) Triển khai
chiến lược CNI là lấy điểm giữa giữa hai thái cực chiến lược CWHO và
CWOHO; (d) Sử dụng mô phỏng để đánh giá về ba chiến lược bảo trì trong các
điều kiện mạng khác nhau. Điều này cung cấp một cái nhìn sâu sắc cho các
chiến lược thiết kế khác nhau cho vấn đề bảo trì thông tin định tuyến.
1.3. Một số kỹ thuật phân cụm trong mạng MANET
Kỹ thuật phân cụm thường được sử dụng để giảm chi phí định tuyến của
mạng và tăng thời gian sống của các nút trong mạng. Kỹ thuật phân cụm phân
tán được nghiên cứu rộng rãi nhất trên mạng ad hoc và cảm biến không dây dựa
trên lý thuyết đồ thị thống trị. Một tập thống trị [5] của đồ thị G = (V, E) có thể
được định nghĩa là một tập con của các đỉnh S ⊆ V sao cho mọi đỉnh v ∈ V đều
13
nằm trong S hoặc liền kề với một đỉnh của S. Một đỉnh của S được xem là thống
trị chính nó và các đỉnh lân cận của nó. Một cạnh được gọi là cạnh bị thống trị
nếu một trong hai điểm mút của nó nằm trong S và các cạnh khác được gọi là
cạnh tự do. Nhiều kỹ thuật đã được đề xuất để chọn tập thống trị S [1], chẳng
hạn như tập thống trị độc lập (IDS), tập thống trị kết nối (CDS) và tập thống trị
kết nối yếu (WCDS). Trong IDS, không có hai đỉnh trong S liền kề nhau; trong
khi đó trong CDS, tất cả các đỉnh trong S đều được kết nối. Do đó, số lượng
cụm có thể có trong IDS nhỏ hơn trong CDS. Tuy nhiên, khả năng kết nối của
các nút đầu cụm trong CDS được xem là thuận lợi hơn cho các ứng dụng truyền
thông kiểu quảng bá. WCDS là một biến thể của CDS, giúp nới lỏng yêu cầu
kết nối trực tiếp giữa các nút thống trị lân cận.
Phương pháp DDR trong nghiên cứu [9] đề xuất một kỹ thuật phân tán
khác để phân cụm các nút thành các vùng không chồng lấp. Đối với việc hình
thành vùng, DDR không chọn một tập hợp con các nút trong mạng như trong
tập thống trị. Thay vào đó, một thuật toán phân tán được sử dụng để xây dựng
một rừng. Các cây trong rừng được hình thành bằng cách trao đổi các thông
điệp báo hiệu định kỳ giữa các nút. Mỗi cây tạo thành một vùng riêng biệt và
được gán một định danh vùng (zone-ID) bằng cách sử dụng thuật toán đặt tên
vùng. Các vùng được kết nối với nhau bởi các nút biên không thuộc cùng một
cây nhưng nằm trong cùng một phạm vi truyền thông.
Một số mạng ad hoc hỗn độn sử dụng các nút báo hiệu để phân cụm các
nút trong mạng. Các nút báo hiệu cố gắng tác động vào các nút lân cận để thu
hút các nút khác nhằm tạo thành cụm. Phương pháp LABAR [4] nghiên cứu về
mạng hỗn độn trong đó chỉ có một tập con các nút có thông tin vị trí chính xác
của chúng. Các nút có thông tin vị trí được gọi là các nút G và phần còn lại là
các nút S. Các nút G đóng vai trò là nút báo hiệu và tạo thành các vùng bằng
cách lôi kéo các nút S trong vùng lân cận của chúng. Phương pháp BEAD [7]
14
nghiên cứu mạng ad hoc phân cấp ba tầng với các nút di động (MN) ở tầng thấp
nhất, theo sau là các nút chuyển tiếp (FN) và các điểm truy cập (AP) ở các tầng
tiếp theo. Các thông điệp báo hiệu định kỳ được gửi bởi FN và AP được quét
bởi các MN để xác định nút cha tốt nhất của chúng trong mạng. Phương pháp
trong [16] cũng là một dạng kỹ thuật phân cụm dựa trên nút báo hiệu.
Các nút trong MANET cũng có thể được nhóm lại kiểu vật lý dựa trên
mối quan hệ logic hoặc kiểu hoạt động của chúng. Các ứng dụng như khắc phục
thảm họa hoặc triển khai trong quân sự trong một khu vực thường yêu cầu sự
hợp tác giữa các nhóm nhỏ các nút trong mạng. Các thành viên trong nhóm có
chung mối quan tâm và chúng luôn di chuyển theo nhóm với tốc độ và hướng
tương tự như nhau. Từ đặc điểm này, có thể phân chia các nút vật lý thành nhiều
nhóm nhỏ. Kỹ thuật này được gọi là kỹ thuật phân cụm dựa trên nhóm.
Một kỹ thuật phân cụm vật lý khác, thường được sử dụng trong các mạng
hoạt động với các nút có hỗ trợ hệ thống định vị toàn cầu GPS, là phân chia
việc triển khai thành các lưới địa lý. Kỹ thuật này đòi hỏi mỗi nút phải biết
trước thông tin về hình dạng của khu vực triển khai và phân vùng của khu vực.
Thông tin trên giúp mỗi nút xác định ranh giới của cụm và cụm chứa nó. So
sánh với tính di động của nhóm, trong kỹ thuật này tính di động của các nút là
ngẫu nhiên và các phân vùng địa lý được cố định.
Ngoài ra, còn có những kỹ thuật phân cụm khác. Nghiên cứu [14] đã khảo
sát các kỹ thuật phân cụm trong các mạng không dây. Các kỹ thuật phân cụm
trong mạng MANET được tổng kết trong Bảng 2.1.
Kỹ thuật phân cụm
Tập thống trị
Đặc điểm
Giao thức
Phân cụm logic bằng cách
chọn một tập con các nút trong IDS,CDS, WCDS
mạng
15
Phân cụm logic dưới dạng
phân tán
Cụm phân tán
DDR
Phân cụm logic sử dụng nút
báo hiệu
GLIDER, LABAR,
BEAD
Dựa trên báo hiệu
Dựa trên nhóm
Phân cụm vật lý dựa trên mối
quan hệ logic giữa các nút
HSR, LANMAR
Phân cụm vật lý sử dụng
thông tin vị trí và hình trạng
mạng
DCS, ZHLS, DLM,
GLS
Phân vùng địa lý
Bảng 2.1. Một số kỹ thuật phân cụm tiêu biểu trong mạng MANET
1.4. Một số kỹ thuật bảo trì thông tin cụm trong mạng MANET
Trong mạng có cấu hình động, thông tin trạng thái của các cụm, chẳng
hạn như kết nối giữa các cụm, băng thông của các liên kết lớp phủ và kích thước
của cụm, có thể thay đổi thường xuyên. Đã có các chiến lược bảo trì thông tin
mạng được nghiên cứu và đề xuất [1]. Có thể phân chia các chiến lược bảo trì
thông tin mạng thành hai nhóm là nhóm các chiến lược bảo trì dựa trên nút
đứng đầu và nhóm các chiến lược sử dụng phương pháp phân tán. Mô tả ngắn
gọn về các giao thức triển khai của các chiến lược này được trình bày trong
Bảng 2.2.
Giao thức
CBRP
Mô tả
Dựa trên nút đứng đầu mỗi cụm thực hiện nhiệm vụ
kết nối và định tuyến liên cụm.
LABAR, BEAD
Sử dụng nút đặc biệt (G-node trong LABER) để bảo
trì kết nối và định tuyến cho các vùng.
CEDAR, MCEDAR Sử dụng các nút lõi để bảo trì thông tin về các cụm.
GLIDER
Topo mạng cảm biến được phân tán cho mọi nút và sử
dụng cho định tuyến.
Tải về để xem bản đầy đủ
62 trang
15660
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nghiên cứu chiến lược bảo trì thông tin định tuyến trong mạng AD HOC phân cụm", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_nghien_cuu_chien_luoc_bao_tri_thong_tin_dinh_tuyen.pdf
