Giao thức quản lý Topology trong mạng không dây ngang hàng

- Phùng minh quân giao thức quản lý topology trong mạng không dây ngang hàng Luận văn thạc sĩ khoa học Chuyên ngành: Công nghệ thông tin Hà Nội - 2008 phùng minh quân  CÔNG NGHệ THÔNG TIN  KHóA bộ giáo dục và đào tạo TRƯờNG ĐạI HọC bách khoa Hà Nội.
- Phùng minh quân giao thức quản lý topology trong mạng không dây ngang hàng Chuyên ngành: Công nghệ thông tin Luận văn thạc sĩ khoa học Ng−ời h−ớng dẫn khoa học: ts.
- vũ tuyết trinh Hà Nội - 2008 Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học NHỮNG LỜI ĐẦU TIấN Với những dũng chữ đầu tiờn này, tụi xin dành để gửi lời cảm ơn chõn thành và sõu sắc nhất tới cụ giỏo, tiến sĩ Vũ Tuyết Trinh - người đó tận tỡnh hướng dẫn, chỉ bảo và tạo cho tụi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành cụng việc của mỡnh.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học MỤC LỤC DANH MỤC HèNH VẼ DANH MỤC BẢNG BIỂU MỞ ĐẦU CHƯƠNG 1 - TỔNG QUAN .
- Mạng P2P khụng dõy – Mạng tựy biến khụng dõy .
- Bài toỏn quản lý topology cho mạng khụng dõy P2P .
- Cỏc phương phỏp tiếp cận bài toỏn quản lý topology cho mạng khụng dõy tựy biến .
- Vị trớ của giao thức quản lý topology trong tầng giao thức của mạng tựy biến10 CHƯƠNG 2 - QUẢN Lí KẾT NỐI CỦA CÁC NÚT MẠNG LÂN CẬN .
- Thuật toỏn dựa trờn mức năng lượng của cỏc nỳt mạng .
- Giao thức RAW .
- Giao thức AWP .
- Giao thức CAW Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 3.4.
- Lựa chọn giao thức quản lý topology .
- Lựa chọn giao thức quản lý topology KẾT LUẬN TÀI LIỆU THAM KHẢO Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học DANH MỤC HèNH VẼ Hỡnh 1.1: Mụ hỡnh mạng P2P.
- 5 Hỡnh 1.2: Mạng tựy biến khụng dõy.
- 7 Hỡnh 1.3: Mục đớch giải quyết của bài toỏn quản lý topology cho mạng tựy biến khụng dõy Hỡnh 1.4: Vị trớ của giao thức quản lý topology trong tầng giao thức Hỡnh 1.5: Quan hệ giữa lớp routing và lớp quản lý topology.
- 12 Hỡnh 1.6: Quan hệ giữa lớp quản lý topology vả lớp MAC.
- 13 Hỡnh 2.1: Mạng khụng dõy tựy biến mật độ lớn.
- 35 Hỡnh 3.2: Cỏc trường thụng tin cần lưu trữ về nỳt mạng lõn cận của giao thức AWP Hỡnh 3.3: Sự phụ thuộc giữa tỷ lệ gúi tin được gửi thành cụng với tỷ lệ phần trăm thời gian hoạt động của nỳt.
- 41 Hỡnh 3.10: Cỏc trường thụng tin cần lưu trữ về một nỳt mạng lõn cận trong giao thức AWP.
- 60 Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học DANH MỤC BẢNG BIỂU Bảng 2.1 Cỏc tham số của mụ hỡnh giả lập.
- 53 Bảng 3.4: Đề xuất sử dụng cỏc thuật toỏn bật tắt nỳt mạng.
- 54 Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 1MỞ ĐẦU Sự phỏt triển của cụng nghệ mạng ngang hàng (Peer to peer – P2P), và cụng nghệ kết nối, lưu trữ của thiết bị khụng dõy đó tạo nờn một hướng nghiờn cứu mới cho ứng dụng mạng, đú là cỏc ứng dụng mạng khụng dõy ngang hàng (wireless P2P).
- Mạng khụng dõy P2P cho phộp cỏc nỳt mạng cú thể kết nối trực tiếp với nhau bằng cỏch sử dụng bộ thu phỏt khụng dõy (wireless transceiver) mà khụng cần bất cứ một cơ sở hạ tầng cố định nào.
- Đõy là một đặc tớnh riờng biệt của mạng khụng dõy P2P so với cỏc mạng khụng dõy truyền thống như cỏc mạng chia ụ (cellular networks) và mạng WLAN, trong đú cỏc nỳt mạng (vớ dụ như cỏc thuờ bao điện thoại di động) giao tiếp với nhau thụng qua cỏc trạm vụ tuyến cơ sở (base station) hoặc cỏc điểm truy cập (access point).
- Tuy nhiờn, mụ hỡnh mạng khụng dõy P2P gặp phải một số thỏch thức lớn đú là.
- Topology của mạng thường xuyờn thay đổi: Do cỏc nỳt mạng là cỏc thiết bị khụng dõy nờn chỳng cú thể chuyển động tự do, và cú thể tham gia Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 2hay rời khỏi mạng một cỏch tựy ý.
- Vỡ vậy, mỗi nỳt mạng cần phải cú cơ chế xỏc định xem bản thõn nú cú thể kết nối với những nỳt mạng nào.
- Năng lượng của cỏc nỳt mạng bị cạn kiệt: Cỏc nỳt mạng khụng dõy thường hoạt động bằng nguồn năng lượng pin hoặc acquy.
- Tuy nhiờn, cỏc nghiờn cứu này chỉ tập trung vào việc đưa ra những giao thức quản lý topology để đỏp ứng cho từng mục đớch ứng dụng cụ thể hoặc trong từng ràng buộc cụ thể.
- Xuất phỏt từ thực trạng đú, với mục đớch hệ thống húa và đưa ra những khuyến nghị về việc lựa chọn cỏc giao thức quản lý topology cho cỏc ứng dụng khụng dõy một cỏch phự hợp, luận văn sẽ tiến hành phõn tớch, so sỏnh, đỏnh giỏ một số giao thức quản lý topology tiờu biểu, từ đú đề xuất một số tiờu chớ để lựa chọn cỏc giao thức này cho cỏc ứng dụng khụng dõy cụ thể.
- Giới thiệu một cỏch tổng quan về sự ra đời và phỏt triển của mạng khụng dõy P2P, cỏc phương phỏp tiếp cận bài toỏn quản lý topology cho mạng khụng dõy P2P, vị trớ của giao thức quản lý topology trong tầng giao thức.
- Chương 2 – Quản lý kết nối của cỏc nỳt mạng lõn cận.
- Chương này phõn tớch và đỏnh giỏ một số thuật toỏn quản lý kết nối của một nỳt mạng với cỏc nỳt mạng lõn cận nú.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 3Chương 3 – Quản lý việc bật tắt cỏc nỳt mạng.
- Chương này phõn tớch và đỏnh giỏ một số giao thức bật tắt cỏc nỳt mạng nhằm tiết kiệm năng lượng cho cỏc nỳt mạng và đề xuất việc ỏp dụng cỏc giao thức đú theo những mục tiờu và ràng buộc cụ thể.
- Chương này đưa ra một số kịch bản về ứng dụng để minh họa cho việc lựa chọn cỏc giao thức quản lý topology đó phõn tớch ở chương 2 và chương 3.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 4CHƯƠNG 1 - TỔNG QUAN 1.1.
- Cỏc hệ thống P2P này ngoài việc chia sẻ file cũn phỏt triển theo hướng chia sẻ khả năng xử lý của cỏc nỳt mạng rảnh rỗi.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 5Mạng P2P khụng cú khỏi niệm mỏy chủ và mỏy khỏch.
- Mỗi nỳt mạng đúng vai trũ đồng thời là mỏy khỏch và mỏy chủ đối với cỏc mỏy khỏc trong mạng [18].
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 61.1.2.
- Mạng P2P khụng dõy – Mạng tựy biến khụng dõy Trong những năm gần đõy, thế giới đó được chứng kiến sự phỏt triển ngoạn mục của cỏc ứng dụng khụng dõy.
- Đõy là kết quả tất yếu của cỏc tiến bộ cụng nghệ liờn quan đến mạng khụng dõy và khả năng tớnh toỏn, lưu trữ của cỏc thiết bị di động.
- Những tiến bộ cụng nghệ núi trờn đó gúp phần tạo ra một kiểu kết nối mới giữa cỏc thiết bị di động, đú là mạng P2P khụng dõy.
- Như vậy, về bản chất mạng P2P khụng dõy là một mạng tựy biến khụng dõy.
- Khỏi niệm về mạng tựy biến khụng dõy được mụ tả như sau: Mạng khụng dõy tựy biến (Wireless ad-hoc network): là một tập hợp gồm nhiều hơn một thiết bị/nỳt mạng với khả năng nối mạng và giao tiếp khụng dõy với nhau mà khụng cần sự hỗ trợ của một sự quản trị trung tõm Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 7nào.
- Mỗi nỳt trong một mạng tựy biến khụng dõy hoạt động vừa như một mỏy chủ (host) vừa như một thiết bị định tuyến.
- Hỡnh 1.2: Mạng tựy biến khụng dõy Trong mạng khụng dõy tựy biến, tỡnh trạng kết nối giữa cỏc nỳt mạng cú thể thay đổi theo thời gian tựy theo chuyển động của nỳt, sự xuất hiện của nỳt mới và việc nỳt cũ rời khỏi mạng.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 8Một vấn đề bất cập xảy ra là khi cú nhiều nỳt mạng thỡ topology mạng trở nờn quỏ phức tạp: Cú quỏ nhiều kết nối giữa cỏc nỳt, dẫn đến khả năng xung đột cao, cú quỏ nhiều lựa chọn để routing dẫn đến thuật toỏn routing khú hoạt động hiệu quả, hao phớ năng lượng nỳt mạng …Từ đú, một yờu cầu đặt ra là giảm độ phức tạp cho topology mạng, nghĩa là xỏc định 1 nỳt được phộp tạo kết nối với cỏc nỳt nào, và xỏc định cơ chế để tiết kiệm năng lượng cho nỳt mạng.
- Đõy chớnh là mục đớch của bài toỏn quản lý topology cho mạng P2P khụng dõy mà luận văn sẽ đề cập trong phần tiếp theo.
- Hỡnh 1.3: Mục đớch giải quyết của bài toỏn quản lý topology cho mạng tựy biến khụng dõy 1.2.
- Bài toỏn quản lý topology cho mạng khụng dõy P2P 1.2.1.
- Phỏt biểu bài toỏn Bài toỏn quản lý topology cho mạng khụng dõy P2P được phỏt biểu như sau [15]: Quản lý topology là một cỏch thức phối hợp quyết định của cỏc nỳt mạng trong đú tinh đến giới hạn truyền tớn hiệu của nỳt mạng nhằm tạo ra một mạng với những thuộc tớnh mong muốn (như tớnh kết nối) đồng thời giảm năng lượng tiờu thụ của cỏc nỳt mạng và/hoặc tăng hiệu năng của mạng.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 91.2.2.
- Cỏc phương phỏp tiếp cận bài toỏn quản lý topology cho mạng khụng dõy tựy biến Hiện nay, cỏc nghiờn cứu trờn thế giới về bài toỏn quản lý topology cho mạng khụng dõy tựy biến tập trung theo 2 hướng tiếp cận sau: 1.2.2.1.
- Như vậy bài toỏn quản lý được quy về việc xõy dựng đồ thị T.
- Trong nhiều năm, rất nhiều tỏc giả đó sử dụng phương phỏp tiếp cận phi đồ thị để giải bài toỏn quản lý topology trong mạng tựy biến và đưa ra nhiều cụng trỡnh nghiờn cứu cú giỏ trị nhằm tối ưu húa cỏc yếu tố khỏc nhau của mạng.
- Tuy nhiờn nhược điểm của cỏch tiếp cận này là nú đũi hỏi mỗi nỳt mạng phải luụn lưu trữ và cập nhật thụng tin về toàn bộ mạng, điều này là khụng khả thi đối với mạng khụng dõy tựy biến cú diện rộng và cỏc nỳt mạng di động.
- Trong hướng tiếp cận Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 10này, cỏc mụ hỡnh giải tớch và cỏc giới hạn về hiệu năng khụng được tớnh toỏn trước.
- Những vấn đề cần giải quyết của bài toỏn quản lý topology cho mạng khụng dõy P2P theo hướng tiếp cận phi đồ thị bao gồm.
- Quản lý kết nối của một nỳt mạng với cỏc nỳt lõn cận: Nghĩa là xỏc định xem một nỳt mạng được phộp tạo liờn kết với nỳt nào trong giới hạn truyền tớn hiệu của nú • Quản lý việc bật tắt cỏc nỳt mạng: Nghĩa là thiết lập một cơ chế bật tắt cho cỏc nỳt trong mạng nhằm tiết kiệm năng lượng cho nỳt mạng mà vẫn đảm bảo được hiệu năng hoạt động của mạng ở mức chấp nhận được.
- Hướng tiếp cận này đó khắc phục được nhược điểm của hướng tiếp cận dựa trờn lý thuyết đồ thị, nghĩa là nú khả thi đối với mạng khụng dõy tựy biến cú diện rộng và cỏc nỳt mạng di động.
- Tuy nhiờn đa số cỏc nghiờn cứu gần đõy chấp nhận đưa giao thức quản lý topology vào giữa lớp routing và lớp MAC của mạng khụng dõy tựy biến (Hỡnh 1.4).
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 11 Hỡnh 1.4: Vị trớ của giao thức quản lý topology trong tầng giao thức 1.2.3.1.
- Quan hệ giữa lớp quản lý topology và lớp routing Lớp routing chịu trỏch nhiệm tỡm đường giữa nỳt nguồn và nỳt đớch trong mang.
- Khi nỳt mạng u cần gửi một thụng điệp tới nỳt mạng v, nú sẽ gọi đến giao thức routing.
- Sự tương tỏc hai chiều giữa lớp routing và lớp quản lý topology được minh họa trờn hỡnh 1.5 [15].
- Ngược lại, lớp routing cú thể yờu cầu lớp quản lý topology cập nhật lại danh sỏch cỏc nỳt mậng lõn cận nếu như nú phỏt hiện ra cú quỏ nhiều đường đi khụng cũn kết nối được.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 12 Hỡnh 1.5: Quan hệ giữa lớp routing và lớp quản lý topology 1.2.3.2.
- Quan hệ giữa lớp quản lý topology và lớp MAC Lớp MAC (Medium Access Control) chịu trỏch nhiệm điều phối truy cập tới kờnh giao tiếp khụng dõy.
- MAC là lớp giao thức rất quan trọng trong cỏc mạng khụng dõy tựy biến giỳp, nú tối thiểu húa xung đột truy cập của cỏc nỳt mạng từ đú duy trỡ hiệu năng cho mạng ở mức chấp nhận được.
- Để mụ tả rừ hơn sự tương tỏc giữa lớp MAC và lớp quản lý topology ta sử dụng giao thức MAC trong chuẩn IEEE 802.11 để minh họa.
- Để hạn chế xung đột, tất cả cỏc nỳt mạng lưu giữ một vector để theo dừi cỏc quỏ trỡnh truyền dữ liệu đang diễn ra (Network Allocation Vector - NAV).
- NAV được cập nhật mỗi khi nỳt mạng nhận được thụng điệp RTS, CTS hoặc ACK.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 13Chỳ ý rằng tất cả cỏc nỳt mạng khỏc nằm trong trong giới hạn truyền tớn của u, v cũng sẽ nghe được một phần hoặc toàn bộ quỏ trỡnh trao đổi cỏc thụng điệp RTS/CTS/ACK giữa u và v.
- Như vậy sự tương tỏc hai chiều giữa lớp routing và lớp quản lý topology được minh họa trờn hỡnh 1.6 [15].
- Trong đú, lớp quản lý topology sẽ thiết lập mức năng lượng cho cỏc nỳt mạng (quy định cơ chế bật tắt cho nỳt mạng).
- Ngược lại lớp MAC sẽ yờu cầu lớp quản lý topology cập nhật lại danh sỏch liền kề của nỳt mạng khi nỳt mạng phỏt hiện ra những nỳt mạng mới ở vị trớ lõn cận với nú (Việc phỏt hiện cỏc nỳt mạng mới ở vị trớ lõn cận được thực hiện nhờ cơ chế “nghe” như đó mụ tả ở trờn) Hỡnh 1.6: Quan hệ giữa lớp quản lý topology vả lớp MAC Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 14CHƯƠNG 2 - QUẢN Lí KẾT NỐI CỦA CÁC NÚT MẠNG LÂN CẬN 2.1.
- Giới thiệu Trong mạng khụng dõy tựy biến, mỗi nỳt mạng cú thể kết nối tới tất cả cỏc nỳt mạng khỏc nằm trong giới hạn truyền tớn hiệu của nú.
- Hỡnh 2.1: Mạng khụng dõy tựy biến mật độ lớn Để giải quyết vấn đề nờu trờn, giao thức quản lý topology đưa ra một cơ chế để xỏc định xem một nỳt mạng được phộp tạo liờn kờt với những nỳt mạng nào trong giới hạn truyền tớn hiệu của nú.
- Mụ hỡnh húa hệ thống Xột một ứng dụng chia sẻ file P2P hoạt động ở tầng trờn cựng của một mạng khụng dõy P2P với N người dựng (N nỳt).
- Gọi nỳt mạng thứ i là iu , giới hạn truyền tớn hiệu của nỳt iu là iR , khoảng cỏch từ nỳt iu đến nỳt sulà siuud→, và tập tất cả cỏc nỳt là U Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 15{}NiuU ,...,3,2,1.
- Nằm trong giới hạn truyền tớn hiệu của nỳt mạng iu • Thỏa món thuật toỏn lựa chọn của giao thức quản lý topology Tớnh chất bất đối xứng của tập liền kề: Theo cỏch hiểu thụng thường của mạng P2P thỡ khi nỳt mạng iu và su cú quan hệ với nhau thỡ chỳng sẽ cú chức năng tương đương nhau trong mối quan hệ đú.
- Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 16 Hỡnh 2.2: Tớnh bất đối xứng của tập liền kề 2.3.
- Một số thuật toỏn Cỏc giao thức quản lý topology được đề xuất gần đõy đó đưa ra nhiều thuật toỏn để xõy dựng tập liền kề cho nỳt mạng theo những tiờu chớ lựa chọn khỏc nhau.Trong phạm vi luận văn này, ta sẽ xem xột một số thuật toỏn tiờu biểu dưa trờn những tiờu chớ cơ bản sau.
- Tớnh cụng bằng giữa cỏc nỳt mạng: Trong mạng tựy biến khụng dõy, cỏc nỳt mạng luụn phải đúng gúp vào việc duy trỡ mạng chung (đúng vai trũ chuyển tiếp dữ liệu cho nỳt khỏc).
- Điều này làm tiờu hao năng lượng của nỳt mạng và làm chậm tốc độ xử lý của nỳt mạng đú.
- Vỡ vậy đối với những mạng tựy biến mà cỏc nỳt mạng cú tớnh cỏ nhõn cao, cần phải cú một cơ chế đảm bảo tớnh cụng bằng giữa cỏc nỳt mạng trong việc đúng gúp vào duy trỡ mạng chung.
- Tớnh hiệu quả của việc chia sẻ tập tin giữa cỏc nỳt mạng: Ứng dụng chia sẻ tập tin là ứng dụng rất phổ biến trong mạng khụng dõy tựy biến hiện nay.
- Nếu một nỳt mạng chứa nhiều tập tin được ưa thớch thỡ sẽ cú rất nhiều (a) A nằm trong tập liền kề của B nhưng B khụng nằm trong tập liền kề của A (b) B nằm trong tập liền kề của A nhưng A khụng nằm trong tập liền kề của B (c) A và B nằm trong tập liền kề của nhau Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 17kết nối đến nỳt mạng đú để download tập tin.
- Khi đú dễ xảy ra trường hợp tắc nghẽn mạng và nỳt mạng đú nhanh chúng cạn kiệt năng lượng.
- Trong trường hợp này, cần ỏp dụng một cơ chế để giảm tải cho cỏc nỳt mạng chứa nhiều tập tin được ưa thớch.
- Tớnh hiệu quả trong việc sử dụng năng lượng của cỏc nỳt mạng: Với những mạng tựy biến mà cỏc nỳt mạng cú mức chờnh lệch năng lượng lớn, cỏc nỳt mạng cú mức năng lượng thấp sẽ nhanh chúng bị cạn kiệt năng lượng.
- Để kộo dài hoạt động của cỏc nỳt mạng này, cần cú cơ chế giảm tải cho chỳng.
- Thuật toỏn dựa trờn mức năng lượng của cỏc nỳt mạng trong trỡnh bày trong phần 2.3.3 sẽ đưa ra cơ chế này.
- Đõy là những yếu tố quan trọng và cơ bản nhất của cỏc mạng khụng dõy P2P thụng dụng hiện nay.
- Thuật toỏn dựa trờn tớnh cụng bằng Mục đớch của thuật toỏn là để cỏc nỳt mạng cú mức độ đúng gúp vào mạng chung cụng bằng với nhau.
- Ta phõn cỏc hoạt động của mỗi nỳt mạng ra thành 2 loại như sau.
- Hoạt động riờng: Bao gồm việc download file từ cỏc nỳt khỏc Ta lượng húa mức độ đúng gúp này bằng metric sau iipublecontrbTTm = [4] Giao thức quản lý topology trong mạng khụng dõy ngang hàng Phựng Minh Quõn - Luận văn cao học 18Trong đú ipublicT biểu diễn khoảng thời gian mà trong đú nỳt mạng iu đúng gúp vào mạng chung, và iT là tổng thời gian mà nỳt iu tham gia vào mạng P2P như một trong cỏc peer

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt