Khóa luận Tối ưu hóa topology trong mạng AD-HOC
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Đức Hải
TỐI ƯU HÓA TOPOLOGY TRONG MẠNG AD-HOC
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Đức Hải
TỐI ƯU HÓA TOPOLOGY TRONG MẠNG AD-HOC
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: PGS.TS Trần Hồng Quân
HÀ NỘI - 2009
Lời cảm ơn
Để hoàn thành được khóa luận này trước hết em xin gửi cảm ơn tất cả các thầy
cô trong trường Đại Học Công Nghệ đã truyền thụ cho em những kiến thức để có thể
nghiên cứu những vấn đề của khóa luận, sự cảm ơn chân thành đến PGS.TS Trần
Hồng Quân, người đã trực tiếp hướng dẫn em trong suốt quá trình làm khóa luận, đến
anh Vũ Anh Hải ban BCCS VNPT, người đã giúp đỡ em rất nhiều trong quá trình xây
dựng chương trình mô phỏng.
Và cuối cùng em xin gửi lời cảm ơn tới gia đình, người thân và bạn bè đã giúp
đỡ, tạo điều kiện, động viên em trong suốt quá trình làm khóa luận.
Hà Nội, ngày
tháng
năm 2009
Sinh viên
Nguyễn Đức Hải
Tóm tắt nội dung
Ngày nay với sự phát triển nhanh chóng và đa dạng của các thiết bị di dộng,
nhu cầu kết nối giữa các thiết bị mọi lúc mọi nơi ngày càng trở nên cấp thiết. Một
trong những giải pháp cho yêu cầu này đó là xây dựng nên một mạng ad-hoc. Về cơ
bản, mạng ad-hoc có thể kết nối tất cả các thiết bị truyền thông không dây mà không
sử dụng bất cứ các cơ sở hạ tầng cố định nào. Rất nhiều vấn đề đã được đặt ra đó là
làm sao tạo ra được một mạng ahoc là tối ưu nhất. Một trong những vấn đề cần giải
quyết đó là làm thế nào để duy trì được mạng ad-hoc với thời gian là dài nhất trong
điều kiện bị giới hạn về nguồn năng lượng.
Trong khóa luận này chúng ta sẽ giải quyết vấn đề này theo một phương pháp
tiếp cận là tối ưu hóa topology của mang ad-hoc sao cho các node trong mạng có thể
truyền được số lượng các gói tin là lớn nhất và sử dụng nguồn năng lượng là nhỏ nhất.
MỤC LỤC
Mở đầu.................................................................................................................................1
Chương 1. Giới thiệu về mạng Ad-hoc.............................................................................2
1.1. Mạng Ad-Hoc............................................................................................................2
1.2. Những sự thách thức .................................................................................................4
Chương 2. Mô hình hóa mạng ad-hoc ..............................................................................6
2.1. Kênh truyền không dây .............................................................................................6
2.2. Đồ thị truyền thông .................................................................................................10
2.3. Mô hình hóa sự tiêu thụ năng lượng .......................................................................13
2.4. Mô hình hóa tính di động........................................................................................16
Chương 3. Tối ưu hóa Topology......................................................................................20
3.1. Vấn đề về vùng ảnh hưởng......................................................................................20
3.1.1. Định nghĩa vấn đề............................................................................................20
3.1.2. Vấn đề RA trong những mạng một chiều (One-Dimensional Networks). ......21
3.1.3. Vấn đề RA trong mạng 2 và 3 chiều................................................................23
3.1.4. Vấn đề về tính đối xứng...................................................................................25
3.2.Chi phí năng lượng của Range Assignment tối ưu. .................................................33
Chương 4. Hiệu quả năng lượng của sự kết nối các topology......................................34
4.1. Hiêu quả năng lượng Unicast..................................................................................34
4.2. Hiệu quả năng lượng broadcast...............................................................................39
Chương 5. Mô phỏng và kết quả thực nghiệm ..............................................................43
5.1. Ý tưởng xây dựng một chương trình mô phỏng......................................................43
5.2. Xây dựng chương trình mô phỏng ..........................................................................43
5.3. Kết quả mô phỏng ...................................................................................................44
5.4. Nhận xét ..................................................................................................................44
Chương 6. Kết luận ..........................................................................................................46
6.1. Những kết quả đạt được và mặt hạn chế của khóa luận..........................................46
6.2. Phương hướng phát triển.........................................................................................47
Tài liệu tham khảo............................................................................................................48
DANH MỤC HÌNH ẢNH
Hình 1: Mô hình two-ray group............................................................................................8
Hình 2: Chiều của mạng và phạm vi vùng ảnh hưởng của node........................................11
Hình 3: Đồ thị điểm 2 chiều ...............................................................................................12
Hình 4: Các cạnh backward................................................................................................21
Hình 5: Minimum Spanning Tree.......................................................................................24
Hình 6: SRA và WSRA......................................................................................................26
Hình 7: Gadget cho cạnh (a, b)...........................................................................................29
Hình 8: Sự sắp xếp các node và khoảng cách giữa chúng..................................................33
Hình 9: Đồ thị maxpower G và đồ thị con G’ với các hệ số power stretch .......................35
Hình 10: Bảng các đồ thị định tuyến và các hệ số liên quan..............................................37
Hình 11: Một vùng bao phủ của 1 node trong đồ thị Gabriel ............................................38
Hình 12: Giao diện chính của chương trình .......................................................................43
Mở đầu
Những thiết bị tính toán và truyền thông không dây đã trở nên phổ biến và đi kèm
với đó là cơ sở hạ tầng truyền thông ngày càng lớn mạnh đã làm nên một sự phát triển
nhanh chóng của mạng không dây. Hầu hết các nghiên cứu và sự phát triển dành cho
mạng không dây đó là những sự ổn định, được sự quan tâm của cộng đồng khoa học và
nghành công nghiệp truyền thông, lĩnh vực truyền thông đang được kích thích và đang
hướng tới truyền thông giao tiếp mà không cần bất cứ một cơ sở hạ tầng nào. Với những
yêu cầu cấp thiết này thì mạng ad-hoc là một giải pháp hữu hiệu. Vấn đề đặt ra đó là làm
sao để thiết kế được mạng ad-hoc với một độ ổn định cao, hiệu năng trên đường truyền là
lớn nhất, đồng thời tiết kiêm được năng lượng sử dụng cho mỗi node. Trong khóa luận
này chúng ta sẽ tiếp cận và giải quyết vấn đề này theo một phương pháp là tối ưu hóa
Topology để đạt tới hiệu năng sử dụng của mạng một cách cao nhất, đồng thời tiết kiệm
năng lượng được sử dụng cho từng node. Một số nội dung chính của khóa luận khi nghiên
cứu về vấn đề tối ưu hóa Topology được trình bày lần lượt theo các chương sau:
Chương 1: Giới thiệu về mạng ad-hoc, tầm quan trọng, tính năng nổi bật cũng như
những thách thức khi xây dựng một mạng ad-hoc.
Chương 2: Mô hình hóa mạng ad-hoc, mô hình về các kênh truyền không dây, xây
dựng topology của mạng ad-hoc dựa trên đồ thị truyền thông
Chương 3: Tối ưu hóa Topology, đưa ra các thuật toán nhằm tính toán và tạo ra
được topology cho mạng ad-hoc sao cho một cách tối ưu nhất
Chương 4: Hiệu quả năng lượng từ việc tối ưu hóa Topology, chúng ta sẽ chứng
minh rằng với Topology tối ưu thì năng lượng sử dụng cho mạng ad-hoc sẽ được giảm
xuống.
Chương 5: Mô tả về chương trình mô phỏng, đưa ra các ý tưởng xây dựng chương
trình mô phỏng, các module chính, kết quả thực nghiệm và các đánh giá thực tế
Chương 6: Kết luận, đưa ra những mặt đã đạt được của khóa luận, những mặt còn hạn chế
và bước phát triển tiếp theo của khóa luận trong tương lai
1
Chương 1. Giới thiệu về mạng Ad-hoc
1.1. Mạng Ad-Hoc
Mạng ad-hoc là lĩnh vực nền tảng trong truyền thông không dây.Công nghệ này
cho phép những node mạng có thể truyền thông ngay lập tức với những node khác sử
dụng những bộ phát không dây mà không cần sử dụng một cơ sở hạ tầng cố định. Điều
này là một sự khác biệt rất lớn của mạng ad-hoc với nhiều mạng không dây cổ điển như
mạng cellular hay wireless LAN, trong những mạng này, mỗi node sẽ phải truyền thông
với một trạm cơ sở và những trạm cơ sở này thì sử dụng mạng có dây.
Mạng ad-hoc đang được trông đợi sẽ là một cuộc cách mạng hóa của truyền thông
không dây trong vài năm tới: bằng sự bổ sung những mô hình mạng cổ điển (Internet,
mạng cellular, truyền thông vệ tinh), mạng ad-hoc sẽ trở nên vô cùng phổ biến, bằng cách
khai thác công nghệ không dây ad-hoc, những thiết bị không dây vô cùng phổ biến (điện
thoại , PDA, laptop …) và những thiết bị cố định (máy trạm, những điểm truy xuất
Internet không dây …) có thể được kết nối cùng nhau sẽ tạo thành một mạng rộng khắp
hay là một mạng toàn cầu.
Những ứng dụng trong tương lai theo xu hướng công nghệ mạng ad-hoc sẽ chứng
minh rằng nó rất hữu dụng.Ví dụ, hãy xem xét những tình huống sau đây. Một trận động
đất đã phá hủy hầu hết mọi thứ, các cớ sở hạ tầng thông tin liên lac của một thành phố
lớn(đường dây điện thoại, các máy trạm của mạng cellular …). Một vài đội cứu hộ (chữa
cháy, cảnh sát, y tế …) đang làm việc trên thảm họa đó để cứu mọi người và giúp đỡ
những người bị thương.Để mang lại một sự giúp đỡ tốt hơn cho người dân thì những đội
cứu hộ phải được phối hợp với nhau.Rõ ràng, một hành động phối hợp chỉ có thể đạt
được nếu những người cứu hộ có khả năng giao tiếp, với những người trong đội của mình
vả cả những đội khác nữa (ví dụ như cảnh sát với cảnh sát hay cứu hỏa với y tế). Với
công nghệ có sẵn, những nỗi nỗ lực phối hợp của những người cứu hộ trong hoàn cảnh cơ
sở hạ tầng thông tin liên lạc bị phá hủy nghiêm trọng là rất khó khăn: thậm chí nếu các
thành viên trong nhóm được trang bị những bộ đàm hoặc là các thiết bị tương tự, khi
không có quyền truy cập vào các cớ sở hạ tầng cố định có sẵn thì những người cứu hộ chỉ
có thể liên lạc trong một phạm vi gần. Vì vậy một trong những ưu tiên ngày nay trong
quản lý thiên tai đó là làm thế nào để khôi phục lại được hệ thống cơ sở thông tin liên lạc
càng nhanh càng tốt, việc này thường được thực hiện bằng cách sửa chữa các cơ sở hạ
tầng đã bị phá hủy và triển khai các thiết bị thông tin liên lạc tạm thời.
2
Tình hình có thể khác đi rất nhiều nếu công nghệ mạng ad-hoc đã sẵn sàng: bằng
cách sử dụng đầy đủ các hình thức truyền thông không dây phân cấp hay truyền thông
không dây đa chặng, những người cứu hộ sẽ có khả năng giao tiếp trong một khoảng cách
tương đối xa. Đối với môt khu vực thiên tai có một mật độ dân cư đông hay là một thành
phố thì công nghệ mạng ad-hoc có thể mang lại thành công trong những nỗ lực cứu hộ
mà không cần sử dụng một cơ sở hạ tầng thông tin liên lạc nào.
Ví dụ trên phần nào mô tả được những tính năng nối bật của những ứng dụng sử
dụng công nghệ mạng ad-hoc:
Mạng không đồng nhất: Một mạng ad-hoc điển hình là một mạng lưới bao gồm
nhiều thiết bị không đồng nhất. Ví dụ ở giả thiết phía trên đã mô tả, các nhóm cứu hộ làm
việc trên vùng bị thiên tai sẽ được trang bị các thiết bị truyền thông giao tiếp khác nhau
như: điện thoại di động, PDAs, bộ đàm hay máy tính xách tay … .Để cho việc thiết lập
một mạng lưới thông tin liên lạc một cách thành công thì công nghệ mạng phải là nền
tảng giúp cho phép các thiết bị khác nhau có thể giao tiếp được với nhau.
Tính di động: trong một mạng ad-hoc điển hình, hầu hết các node trong mạng là di
động, một ví dụ trong trường hợp này chính là những người làm việc trong vùng bị thiên
tai mà ta đã nêu trong giả thiết phía trên.
Mạng phân tán: việc xây dựng một mạng ad-hoc phân tán là khi các nút trong
mạng là phân tán theo phương diện vật lý, trong thực tế khi các nút mạng là gần nhau thì
truyền thông qua một chặng sẽ hữu dụng hơn rất nhiều và sự truyền thông qua nhiều
chặng là không cần thiết.
Tiềm năng của những ứng dụng trong mạng ad-hoc là rất nhiều , trong đó chúng ta
đánh giá những điều sau đây:
Phân phối nhanh chóng lưu lượng truy cập trên đường cao tốc và khu đô
thị: .Những tuyến đường cao tốc và các khu đô thị có thể được trang bị những trạm phát
vô tuyến cố định, gửi những thông tin quảng bá tới những xe hơi có gắn những thiết bị
thu nhận GPS. Lần lượt các xe đang hoạt động có thể cập nhật được giao thông rất nhanh
chóng.So với những công nghệ cũ thì công nghệ mới này sẽ cung cấp những chính xác và
nhanh chóng hơn.
Truy cập Internet khắp nơi: Trong một tương lai rất gần, những khu vực công
cộng như, sân bay, nhà ga, khu mua sắm cao cấp, sẽ được trang bị những điểm truy cập
Internet không dây, bằng cách sử dụng các thiết bị di động của những người dùng khác
như là một cầu nối không dây việc truy cập internet sẽ được phủ rộng hầu hết mọi nơi.
3
Phân phối những điểm thu nhận thông tin: Bằng cách sử dụng những trạm truyền
thông không dây những điểm thu nhận thông tin có thể phân phối hoặc thu thập thông tin
từ những người sử dụng. Ví dụ về một điểm thu nhận thông tin đó là một thông tin về
một chuyến du lịch, các sự kiện xung quanh, thông tin về các cửa hàng, nhà ăn trong khu
một khu vực. …
1.2. Những sự thách thức
Mặc dù công nghệ dành cho mạng ad-hoc là tương đối hoàn thiện nhưng những
ứng dụng trên nó hầu như hoàn toàn không có.Một phần của thực tế này chính là một số
vấn đề trong mạng ad-hoc còn chưa có hướng giải quyết.Trong phần này chúng ta sẽ mô
tả những trạng thái của công nghệ mạng ad-hoc hiện thời và đối điện với thách thức trong
việc thiết kế mạng ad-hoc.
Mạng không dây ad-hoc đã thu hút được nhiều sự quan tâm của của các nhà ngiên
cứu và các ngành công nghiệp trong một vài năm gần đây.Với tư cách là kết quả của một
loạt các hoạt động ngiên cứu đáng kể, các cơ chế truyền thông không dây ad-hoc cơ bản
đã được thiết kế và chuẩn hóa. Những ví dụ phổ biến nhất, chuẩn giao tiếp IEEE 802.11
và Bluetooth đã được thực thi trong hàng loạt các thiết bị không dây thương mại, và
những chuẩn này cho phép các thiết bị không dây giao tiếp với nhau mà ít sử dụng các cơ
sở hạ tầng.
Vì vậy, giao tiểp không dây, multihop giữa các thiêt bị khác nhau như điện thoại
di động, máy tính cách tay, PDA hay các thiết bị thông minh đều có thể trở thành hiện
thực với công nghệ được cung cấp hiện thời.
Mặc dù thực tế là công nghệ dành cho mạng ad-hoc đang tồn tại, nhưng những
ứng dụng trên nền tảng mô hình mạng ad-hoc hầu như hoàn toàn không có.Nguyên nhân
của điều này đó là thực tế khi triển khai các dịch vụ mạng ad-hoc gặp rất nhiều khó
khăn.Những thách thức chính mà chúng ta sẽ gặp phải là:
- Sự duy trì năng lượng: Những thiết bị trong mạng ad-hoc thường được sư dụng
nguồn năng lượng thông qua pin được gắn cùng, một trong những mục tiêu chính đó là
thiết kế mạng sao cho nguồn năng lượng được sử dụng một cách hiệu quả nhất.
- Hình trạng mạng không cấu trúc và/hoặc thay đổi theo thời gian: Trong một
mạng lưới các node, về nguyên tắc một thiết bị di động có thể ở bất kỳ nơi nào trong một
khu vực rộng lớn và liên tục di động, như vậy một đồ thị của hình trạng mạng sẽ biểu
4
diễn cho sự liên kết giữa các node thường là không có cấu trúc.Hơn nữa hình trạng mạng
sẽ thay đổi theo thời gian vì các nodes gần như liên tục di chuyển.Với nguyên nhân này
việc tối ưu hóa các giao thức trong mạng ad-hoc là một công việc rất khó khăn.
- Chất lượng thông tin liên lạc kém: Thông tin liên lạc trong trên một kênh truyền
không dây nói chung là kém chất lượng hơn so với một kênh truyền có dây.Hơn nữa chất
lượng thông tin liên lạc là bị ảnh hưởng bởi yếu tố môi trường, (điều kiện thời tiết, các
vật cản, chướng ngại vật, sự can thiệp của các mạng lưới không dây khác, …).Vì vậy các
ứng dụng cho mạng ad-hoc nên có khả năng phục hồi nhanh chóng để đáp ứng lại sự ảnh
hưởng từ bên ngoài này.
- Tính toán sự giới hạn tài nguyên: Đặc trưng của mạng ad-hoc là những tài
nguyên sẵn có rất ít.Đặc biệt năng lượng và lương băng thông được cung cấp trong mạng
rất hạn chế so với những mô hình mạng trước đây.Những giao thức trong mạng ad-hoc
phải mang lại mức độ thực thi cao trong điều kiện những tài nguyên có sẵn bị hạn chế.
- Khả năng mở rộng: Trong tương lai không xa của mạng ad-hoc, mạng có thể
gồm hàng trăm hay tới hàng nghìn những node, điều này có nghĩa là giao thức dành cho
mạng ad-hoc phải có khả năng hoạt động hiệu quả trong môi trường có một số lượng rất
lớn các node tham gia.
Trong trường hợp công nghệ mạng ad-hoc được sử dụng để tạo nên một mạng
rộng khắp thì các vấn đề sau đây cũng nên được quan tâm:
Phân chia mạng toàn cầu: Trong viễn cảnh của một mạng rộng khắp được mô tả
trong phần 1.1.1 thì dữ liệu sẽ đi qua hầu hết các mô hình của các mạng: ad-hoc, cellular,
vệ tinh, wireless LAN, Internet, vv.Một lý thuyết lý tưởng là người sử dụng có thể
chuyển dữ liệu thông suốt từ một mạng này tới một mạng khác mà không cần những ứng
dụng chuyển đổi hoặc ngắt chuyển đổi.Và để thực hiện được điều này thì quả thực là một
nhiệm vụ rất khó khăn.
Mô phỏng sự liên kết giữa các node: Khi thiết kế một giao thức mạng, việc thiết
kế thường được giả định rằng tất cả các node đều tình nguyện tham gia thực thi mạng này.
Trong tương lai của những ứng dụng mạng ad-hoc, những node mạng thường được sở
hữu bởi các đối tượng khác nhau (người dùng cá nhân, các chuyên gia hay những tổ chức
lợi nhuận hoặc phi lợi nhuận), và những node này sẽ tự động tham gia thực thi các giao
thức trong mạng ad-hoc. Vì vậy những node trong mạng phải được mô phỏng theo một
giao thức nào đó một cách chi tiết và đặc biệt
5
Chương 2. Mô hình hóa mạng ad-hoc
Trong chương này, chúng ta sẽ giới thiệu một mô hình mạng ad-hoc không dây
đơn giản nhưng đã được áp dụng rộng khắp.Mô hình này cũng được áp dụng cho những
mạng có kiểu tương tự như mạng ad-hoc
2.1. Kênh truyền không dây
Những node trong mạng ad-hoc truyền thông thông qua những bộ thu phát không
dây. Vì lý do này, một điều quan trọng khi xây dựng một khối mô hình cho mạng ad-hoc
là xây dựng kênh truyền không dây.
Một kênh truyền không dây giữa một đơn vị truyền u và một đơn vị nhận v được
thiết lập khi và chỉ khi cường độ của tín hiệu nhận được bởi node v (Pr) ở trên một
ngưỡng, ngưỡng này được gọi là cảm ứng với ngưỡng (sensitivity threshold). Về mặt
hình thức có một liên kết không dây trực tiếp giữa u và v nếu Pr ≥ β , β là giá trị cảm
ứng với ngưỡng, giá trị chính xác của β phụ thuộc vào bộ truyền không dây và tốc độ
truyền dữ liệu: cho một kênh truyền không dây, nếu tốc độ truyền dữ liệu là cao thì giá trị
của β cũng cao hơn.Điều này cũng cho thấy rằng Pr cũng cần cao hơn. Để đơn giản hóa
trong các ví dụ sau thì chúng ta giả thiết rằng β sẽ có giá trị 1.
Cường độ của tín hiệu nhận được Pr sẽ phụ thuộc vào cường độ tín hiệu gửi Pt của
u trên kênh truyền không dây và với sự mất mát trên đường truyền, tín hiệu trên mô hình
này sẽ bị suy giảm theo khoảng cách. Gọi PL(u,v) là giá trị mất mát trên kênh truyền giữa
u và v chúng ta có thể tính Pr theo công thức:
P
t
Pr =
PL(u,v)
Vì vậy sự cố của một kênh truyền không dây giữa hai node mạng bất kỳ có thể
được dự đoán trước nếu sự mất mát trên đường truyền được biết
Việc mô hình hóa sự mất mát trên đường truyền trước đó là một nhiệm vụ khó
khăn nhất của các nhà thiết kế hệ thống mạng không dây.Các nguyên nhân ảnh hưởng
xấu đến những tín hiệu không dây lan truyền trong môi trường có thể được phân thành ba
nhóm: sự phản xạ, nhiễu, sự phân tán. Sự phản xạ xảy ra khi sóng điện từ va chạm với bề
mặt của một đối tượng nào đó sẽ tạo ra một sóng điện từ khác có bước sóng gần bằng với
bước sóng ban đầu tùy thuộc vào bề mặt phản xạ.Ví dụ như, tín hiệu không dây sẽ được
6
phản xạ bởi mặt đất, những tòa nhà lớn và những bức tường.Nhiễu được gây ra bởi một
đối tượng khác nằm giữa người gửi và người nhận mà tiêu biểu là sự giao thoa sóng sẽ
gây nên sự nhiễu tín hiệu. Sự suy giảm xảy ra khi một số nhỏ các đổi tượng người nhận
và người gửi cũng sẽ nhận những tín hiệu dẫn đến sóng lan truyền bị phân tán và suy
giảm cường độ.Trong phần sau đây chúng tôi xin giới thiệu một cách ngắn gọn những mô
hình mất mát trên đường truyền phổ biến nhất.
2.1.1. Mô hình truyền free space
Mô hình này được sử dụng để truyền các tín hiệu lan truyền khi đường truyền giữa
người gửi và người nhận là rỗi và không bị tắc nghẽn. Có nghĩa là với Pr(d) là cường độ
của tín hiệu nhận được từ người gửi với khoảng cách giữa 2 node gửi và nhận là d, chúng
ta có công thức 2.1:
P .Gt .Gr .λ2
t
Pr(d) =
(4π )2 .d 2 .L
Với Gt là gia lượng ănten (transmitter angtenna gain) của người gửi, Gr là gia lượng
ăngten của người nhận, L là hệ số mất mát hệ thống không liên quan đến quá trình truyền
và λ là bước sóng.Vì chúng ta không quan tâm đến những đặc điểm riêng của người gửi,
chúng ta có thể đơn giản hóa và có công thức 2.2 sau:
P
t
P (d) = C f .
r
d 2
Cf là một hằng số phụ thuộc và các đặc điểm của người gửi
Với công thức trên đã cho chúng ta thấy rằng cường độ suy giảm của tín hiệu nhận
được tỉ lệ với bình phương khoảng cách d giữa người gửi và người nhận
Kết hợp với công thức 2.2 với giá trị cảm ứng ngưỡng, những tín hiệu chỉ có thể
được truyền đi khi và chỉ khi
d ≤ C f .P
t
Nói cách khác, vùng bao phủ của một node truyền chính là một vùng tròn có bán kính là
C f .P với node truyền là tâm
t
Công thức free space chỉ đúng khi giá trị d là tương đối lớn đối với ăngten phủ của
người truyền là tương đối xa
2.1.2. Mô hình two-ray ground
7
Mô hình free space là một trường hợp đặc biệt, khi mà đường truyền giữa người
gửi và người nhận là duy nhất và tín hiệu truyền cũng là duy nhất.Chính vì lý do này mô
hình free space thường là không chính xác. Để cải thiện tính chính xác hay xem xét mô
hình two-ray ground theo 2 phần: đường truyền trực tiếp và đường truyền phản xạ qua
mặt đất giữa người gửi và người nhận. Xem hình bên dưới.
Hình 1: Mô hình two-ray group
Trong mô hình two-ray ground cường độ của tín hiệu nhận với khoảng cách truyền
nhận là d được tính theo công thức 2.3:
ht2 .hr2
P (d) = P .Gt .Gr .
r
t
d4
ht là độ cao của ăngten của bên truyền, hr là độ cao của ăngten bên nhận, nếu
khoảng cách giữa người gửi và người nhận là tương đối lớn. (d >> ht .hr ) .Với giả thiết
này ta có thể viết được một công thức đơn giản (2.4) để tính cường độ sóng nhận với
khoảng cách d là
P
t
P = Ct .
r
d 4
Ct(t viết tắt của two – ground model), Ct là một hằng số phụ thuộc và các đặc điểm của
người gửi. Vì vậy điểm khác biệt với mô hình “free space ” là độ suy giảm tín hiệu trong
trường hợp này tỉ lệ với khoảng cách tương quan lên tới lũy thừa 4 thay vì bình phương
khoảng cách tương quan.
Kết hợp với công thức 2.2 với giá trị cảm ứng ngưỡng, chúng ta có vùng bao phủ
4
của một node truyền chính là một vùng tròn có bán kính là Ct .P
t
8
2.1.3 Mô hình log- distance path
Mô hình log- distance path thu được nhờ sự kết hợp của các phương pháp phân
tích và phương pháp thực ngiệm. Phương pháp thực nghiệm dựa trên cơ sở các phép thử
ngiệm đo lường cũng như là các phép điều chỉnh trực tiếp trên dữ liệu.Mô hình này có thể
được coi là mô hình tổng quát của hai mô hình trên, mô hình free space và two-ray
ground. Biết rằng hệ số mất mát đường truyền trung bình tương ứng với khoảng cách d
một cách chính xác là số mũ củaα , nó được gọi là mất mát đường truyền hệ số mũ hay là
độ suy giảm cường độ theo khoảng cách.
P
t
P (d) =
r
dα
α
Miền bao phủ sóng của mô hình này là một vùng tròn có bán kính là P với node
t
truyền là tâm
Giá trị của α phụ thuộc nhiều vào điều kiện môi trường, và nó được đánh giá
trong nhiều trường hợp thực ngiệm khác nhau
Dưới đây là một bảng thể hiện một số giá trị của α theo từng điều kiện môi trường
(Trích Topology Control In Wireless Ad-hoc Networks (Paolo Santi))
Môi trường
Trống trải
α
2
Khu vực dân cư
2.7 – 3.5
2.1.4 Những biến đổi quy mô lớn và quy mô nhỏ
Mô hình truyền log-distance path thường dự đoán giá trị trung bình cường độ tín
hiệu nhận được nhờ một khoảng cách nhất đinh, tuy nhiên cường độ của các tín hiệu nhận
được thường là rất khác nhau từ những giá trị trung bình này. Vì lý do này, mô hình xác
suất đã được sử dụng để tính toán cho các sự thay đổi của các kênh không dây.Trong mô
hình xác suất, diện tích bao phủ sẽ không xa hơn một vùng tròn, cho tới khi một kênh
không dây giữa hai node xuất hiện như là một sự kiện ngẫu nhiên.
Mô hình kênh truyền xác xuất có thể chia thành 2 lớp:
Mô hình những biến đổi quy mô lớn: mô hình này sẽ dự đoán những biến đổi của
cường độ tín hiệu trong một vùng rộng lớn.
9
Mô hình những biến đổi quy mô nhỏ: mô hình này sẽ dự đoán những biến đổi của
cường độ tín hiệu trong một vùng nhỏ, chúng còn được gọi là mô hình multipath fading.
2.2. Đồ thị truyền thông
Đồ thị truyền thông tạo nên những hình trạng của mạng (Network Topology) có
nghĩa là, các node kết nối không dây sẽ sử dụng để kết nối đến những node khác.Như đã
đưa ra thảo luận trong các phần trước, rõ ràng là sự liên kết giữa 2 đơn vị u và v trong
mạng phụ thuộc rât nhiều vào khoảng cách giữa u và v, cường độ truyền được sử dụng để
truyền dữ liệu và những môi trường xung quanh. Từ việc tính toán cho sự biến đổi của tín
hiệu không dây ở mức độ lớn và mức độ nhỏ đồng thời tạo ra một mô hình chặt chẽ gắn
liền với các ứng dụng thực tiễn là một công việc rất phức tạp, trong chương này và các
phần còn lại của khóa luận chúng ta sẽ mô hình hóa kênh không dây sử dụng mô hình
log-distance path, chúng sẽ được loại trừ nhiều đặc tính của môi trường.Đây là mô hình
được coi là tiêu chuẩn trong nghiên cứu về kiểm soát topology trong mạng ad-hoc.
Gọi N là tập hợp những node không dây, với | N | = n. Các node được đặt trong
vùng giới hạn R. Để đơn giản hơn, chúng ta giả sử rằng R là một chiều của một hình lập
phương với cạnh là l. Ta có
R = [0, l]d với l > 0 khi d = 1, 2 3. Với bất kỳ node u thuộc N, vị trí của u trong R ,
được xác định bởi L(u), được diễn tả như chiều tọa độ. Do đó hàm L : N α R sẽ ánh xạ
tất cả các node trong mạng thành một đồ thị được giới hạn bởi R. Nếu các node là di
động, thì vị trí vật lý của các node sẽ phụ thuộc vào thời gian. Nếu node di chuyển trong
vùng R. Chúng ta có thể giả định rằng sự mất mát nói chung của tính di động có thể được
thêm vào bằng một đối số trong L, đó là khoảng thời gian thiết lập t. Tóm tắt lại hàm L :
N x T α R sẽ gán toàn bộ các tính chất của những node N và tại bất kỳ thời điểm t thuộc
T thành tập hợp những tọa độ d chiều để biểu diễn cho những node vật lý tại thời điểm t.
Một d –chiều di động của mạng ad-hoc được biểu diễn bởi cặp Md = (N, L), N, L đã được
định nghĩa tại phía trên.
Cho một mạng lưới Md = (N, L) , một vùng ảnh hưởng của Md là một hàm gán cho
tất cả các thành phần u của N một giá trị RA(u) nằm trong khoảng từ [0 , rmax], được coi
là vùng ảnh hưởng. Thông số rmax được gọi là vùng ảnh hưởng lớn nhất, và thông số này
phụ thuộc vào những thuộc tính của trạm truyền được trang bị trên các node. Và một điều
giả định rằng tất cả các node đều được trang bị những thiết bị có các thuộc tính tương tự
10
nhau, có nghĩa là tất cả các node trong mạng đều có rmax bằng nhau. Trong trường hợp
mạng bao gồm các đơn vị được trang bị các thiết bị có khả năng thu phát là khác nhau và
giá trị rmax sẽ được lấy giá trị là vùng ảnh hưởng lớn nhất của node.
Vùng ảnh hưởng của một node u có nghĩa là trong vùng ảnh hưởng ấy dữ liệu được
truyền bởi node u bắt buộc phải được nhận một cách chính xác. Cho một vùng có độ rộng
r vùng ảnh hưởng của R để dữ liệu có thể chuyển một cách chính xác phụ thuộc vào
chiều mạng : trong trường hợp mạng một chiều, nó sẽ là chiều dài gồm 2 phần có độ dài
là 2r với u là trung tâm, trong trường hợp là mạng 2 chiều nó sẽ là một vòng tròng có bán
kính là r và u là trung tâm, trong trường hợp là 3 chiều, nó là một khối cầu có bán kính là
r và u là trung tâm. (xem hình bên dưới).
Hình 2: Chiều của mạng và phạm vi vùng ảnh hưởng của node
Chú ý rằng, dưới giả thiết sự lan truyền tín hiệu không dây theo mô hình log
distance, với bất kỳ node, trong một pham vi truyền r∈ (0, rmax] thì cường độ truyền sẽ là
Pr ∈ (0, Pmax], Pmax là mức cường độ truyền là lớn nhất của các node.Vì vậy cần chú ý
rằng khái niệm phạm vi truyền và cường độ truyền là tương đương nhau, và chúng có thể
hoàn toàn thay thế cho nhau trong những phần còn lại của bài viết này.
Cho một mạng Md = (N, L) và một vùng ảnh hưởng RA, đồ thị truyền thông bao
gồm RA trên Md tại thời điểm t được định nghĩa là một đồ thì có hướng Gt = (N, E(t)),
E(t) là một cạnh có hướng giữa u và v , nó sẽ có được nếu RA(u) ≥ δ (L(u,t), L(v,t)) trong
đó δ (L(u,t), L(v,t)) là khoảng cách giữa u và v theo thời điểm t. Nói cách khác những liên
kết có hướng không dây (u , v) có thể có được khi và chỉ khi node u và v nằm trong
khoảng cách từ chính nó tới RA (u) tại thời điểm t. Trường hợp này v được gọi là 1 hop
hàng xóm, hay một hàng xóm trong khoảng ngắn của node u. Một kết nối được gọi là
thuộc 2 hướng, hay có tính đối xứng khi tại một thời điểm t (u, v) ∈ E(t) và (v, u) ∈ E(t).
Trong trường hợp này các node u và v được gọi là hàng xóm đối xứng
11
Vùng ảnh hưởng với max power có nghĩa là RA(u) = rmax cho mỗi node u, hay tất
cả các node u trong mạng sẽ truyền với tối đa sức mạnh. Đồ thị truyền thông thu được
cuối cùng được gọi là đồ thị sức mạnh tối đa và nó sẽ được biểu diễn tất cả các kết nối có
thể giữa các node mạng.
Một vùng ảnh hưởng RA được gọi là kết nối tại thời điểm t, hay đơn giản hơn là kết
nối, nếu đồ thị truyền thông thu được cuối cùng tại thời điểm t là một kết nối mạnh, có
nghĩa là với bất kỳ cặp u và v, có ít nhất một đường đi có hướng từ u tới v. Một vùng ảnh
hưởng mà trong đó tất cả các node đều có một vùng ảnh hưởng như nhau là r, 0 < r < rmax
được được gọi là đồng nhất r. Cần chú ý rằng đồ thị truyền thông được sinh ra bởi RA
đồng nhất có thể được coi như là đại lượng vô hướng, từ (u, v) thuộc E(t) ⇔ (v,u) thuộc
E(t).
Nếu mạng là di động, vùng ảnh hưởng có thể là khác nhau với thời gian để duy trì
tính ổn định của đồ thị truyền thông, chẳng hạn như là tính kết nối
Nói chung, chúng ta có thể xác định một số chuỗi những vùng ảnh hưởng trong
khoảng thời gian sống của mạng, RAti là vùng ảnh hưởng tại thời điểm ti , và sự chuyển
tiếp giữa các RA được xác định bởi các giao thức thích hợp.
Nếu mạng là tĩnh (nghĩa là vị trí của tất cả các node không thay đổi trong suốt thời
gian tồn tại của mạng) các mô hình đã được giới thiệu ở phía trên có thể được đơn giản
hóa bằng cách là coi L là một hàm của N mà thôi. Tuy nhiên vì nguyên tắc thì các RA có
thể khác nhau trong quá trình sử dụng của mạng.Các RA có thể được thay đổi, ví dụ như
để hỗ trợ các loại truy cập ( ví dụ, trong mạng cảm biến thông tin được gửi ra bên ngoài
phụ thuộc vào các sự kiện được phát hiện ) hoặc là để đạt được một sự cân bằng trong
việc sử dụng năng lượng giữa các node mạng. Vì vậy nói chung là đồ thị truyền thông sẽ
phụ thuộc vào thời gian, ngay cả khi mạng là tĩnh.
Hình 3: Đồ thị điểm 2 chiều
12
Tương tự như mô hình biểu đồ được sử dụng trong lý thuyết xác suất, như là đồ thị
liên thông và đồ thị hình học ngẫu nhiên.Trong các lý thuyết xác suất một đơn vị đĩa đồ
( unit disk graph ) là một đồ thị mà trong đó 2 node được kết nối bởi một cạnh khi và và
chỉ khi khoảng cách tối đa giữa 2 node là 1.Tiến đến việc tiêu chuẩn hóa, một đơn vị đĩa
đồ tương ứng với các mô hình đã được giới thiệu trong những phần trước với RA là đồng
nhất. Theo lý thuyết xác suất thì một tập hợp các điểm được phân phối theo một các hệ số
phân phối xác suất trong một số khu vực nhất định. Những điểm sau đó được kết nối theo
một số quy tắc nhất định (ví dụ như kết nối đến tất cả các điểm trong khoảng cách r hoặc
là kết nối đến k điểm gần nhất v. v ) để tạo ra đồ thị hình học ngẫu nhiên. Ngoài ra mô
hình này là một trường hợp đặc biệt của chúng ta trong đó các node được phân phối một
cách ngẫu nhiên và các RA được xác định theo một quy tắc đặc biệt nào đó.Nếu các bạn
quan tâm tới thông tin về lý thuyết về đồ thị liên thông và đồ thị hình học ngẫu nhiên có
thể tìm hiểu thêm trong tài liệu Topology Control in wireless ad-hoc and sensor networks,
còn trong phần này chúng ta sẽ không đi sâu vào các lý thuyết xác suất và lý thuyết về
hình học.
Điểm chính của mô hình đồ thị điểm đó là sự giả định về phạm vi vùng ảnh hưởng
thông thường đạt đến mức hoàn hảo: vùng ảnh hưởng là một vùng tròn d chiều với trung
tâm chính là điểm truyền sóng.Như đã thảo luận trong các phần trước giả thiết này là khá
thực tế trong môi trường phẳng. Thật không maylà thực tế trong cuôc sống khá nhiều sự
ảnh hưởng từ môi trưởng, chẳng hạn là có sự ngăn cản của các bức tường, các tòa nhà vv.
Tuy nhiên nếu gộp tất cả các chi tiết trên vào một mô hình mạng sẽ làm cho nó trở nên vô
cùng phức tạp và sẽ phụ thuộc nhiều vào các giả thiết, các kết quả thu được từ việc phân
tích và tổng hợp sẽ trở nên cực kỳ cồng kềnh. Vì lý do này, mặc dù mô hình đồ thị điểm
khả năng còn khá giới hạn nhưng nó vẫn đang được sử dụng rộng rãi trong việc ngiên
cứu các đặc tính của mạng ad-hoc.
Trước khi kết thúc chương này, chúng tôi muốn nhấn mạnh rằng các kết quả thu
được bằng cách sử dụng mô hình đồ thị điểm là rất hữu ích, ít nhất ở một vài mức độ,
chẳng hạn như với các điểm thu phát có các vùng ảnh hưởng là khác nhau.
2.3. Mô hình hóa sự tiêu thụ năng lượng
Một trong những mối quan tâm chính của người thiết kế mạng ad-hoc đó chính là
việc sử dụng hiệu quả sự tiêu thụ năng lượng.Vì vậy, cần một mô hình cơ bản để xác định
13
việc tiêu thụ năng lượng của các node một cách chính xác và hiệu quả.Sau đây chúng ta
sẽ tìm hiểu về việc sử dụng năng lương cho các node trong mạng ad-hoc
2.3.1 Mạng ad-hoc
Tùy thuộc vào các sự giả định, mạng ad-hoc có thể được tạo thành từ rất nhiều các
thiết bị rất đa dạng: máy tính xách tay, điện thoại di động, PDA, các thiết bị thông minh
vv. Hơn nữa, với nhiều ứng dụng tiềm năng trong tương lai, mạng có thể bao gồm cả
những thiết bị không đồng nhất.Do tính đa dạng của các node, một cách tiếp cận điển
hình là chỉ chú ý duy nhất tới việc tiêu thụ năng lượng của việc truyền các tín hiệu không
dây.Và đây cũng là sự lựa chọn của chúng ta, cụ thể chúng ta chỉ quan tâm đến việc giảm
sự tiêu thụ năng lượng được sử dụng để giao tiếp giữa các node. Trên các loại thiết bị
lượng tiêu thụ năng lượng được sử dụng để truyền thông giao tiếp dao động trong khoảng
từ 15% đến 35% trong tổng số năng lượng được sử dụng cho node. Những thông số sử
dụng năng lượng trước đây được cung cấp cho card không dây một máy tính xách tay
thuân thủ theo chuẩn IEEE 802.11. và mới đây là được sử dụng để cung cấp cho một
thiết bị PDA.Kể từ khi năng lượng được sử dụng cho card không dây là một phần trong
năng lượng được sử dụng cho một node thì việc tối ưu hóa việc sử dụng cho việc giao
tiếp trở thành một vấn đề quan trọng. Một số các nhóm phát triển đã tiến hành đo đạc sự
tiêu thụ năng lượng của một card không dây theo chuẩn 802.11.Một card không dây
chuẩn 802.11 thông thường sẽ có 4 chế độ hoạt động
- Nhàn rỗi: Card là được bật, tuy nhiên nó không được sử dụng
- Truyền: Card đang ở chế độ truyền các gói dữ liệu
- Nhận: Card đang ở chế độ nhận các gói dữ liệu
- Ngủ: Sự cung cấp năng lượng giảm.
Bảng bên dưới cho chúng ta thấy sự tiêu thụ năng lượng của card CISCO Aironet IEEE
802.11 a/b/g. (Trích Topology Control In Wireless Ad-hoc Networks (Paolo Santi))
Card
Gửi (mA)
318
Nhận(mA)
554
Nhàn rỗi(mA)
802.11 a
802.11 b
802.11 g
203
203
203
327
539
282
530
14
Card
802.11 a
802.11
b/g
Phạm vi truyền “Indoor” (m)
Phạm vi truyền “Outdoor” (m)
15 -30
30 -300
76- 396
27 – 91
Sự tiêu thụ năng lượng ở chế độ ngủ không được biểu diễn trong bảng, bảng này
còn cho chúng ta thấy pham vi truyền giới hạn khi card truyền với tối đa sức mạnh. Như
chúng ta thấy trong bảng phạm vi truyền giới hạn phụ thuộc vào nhiều yếu tố môi trường
(trong nhà hay điều kiện ngoài trời ) và tốc độ dữ liệu được sử dụng để gửi các gói tin.
Chúng ta cần chú ý rằng, các dữ liệu trong bảng bên trên chỉ là các kết quả rút ra từ
những thực nghiệm và có thể có sự khác biệt với thực tế thiêu thụ năng lượng của các
card không dây. Tất cả các kết quả thu được từ những thực nghiệm đã vạch ra cho chúng
ta một điểm rất quan trọng đó là bất kỳ sự chuyển trạng thái nào của đơn vị truyền cũng
có thể phải sử dụng năng lượng (và cả thời gian trễ nữa) Điều này đặc biệt đúng đối với
sự chuyển trạng thái từ chế độ ngủ chuyển sang chế độ nhàn rỗi. Trong phần này chúng ta
sẽ mô hình hóa việc sử dụng năng lượng của các node theo tỉ lệ Ngủ : Nhàn rỗi : Gửi và
Nhận, hay nói cách khác chúng ta sẽ không quan tâm đến chính xác một giá trị nào của
việc tiêu thụ năng lượng mà là chỉ là các giá trị tương đối. Trong mô hình đơn giản của
chúng ta chúng ta giả định rằng các card thu phát được quy ước là 1 khi ở chế độ nhàn rỗi,
1.X là khi nhận một gói tin , 1.Y khi gửi một gói tin với sức mạn tối đa , và 0 . Z khi ở
chế độ ngủ (các giá trị X, Y , Z phụ thuộc vào đặc tính của card mạng) .
Trước khi kết thúc chương này, chúng ta cần lưu ý rằng tỉ lệ 1.Y được sử dụng
liên quan tới sự tiêu thụ năng lương của card khi nó ở trạng thái truyền với sức mạnh tối
đa.Mặt khác chúng ta sẽ thấy rằng giao thức kiểm soát Topology được dựa trên nền tảng
đó là khả năng điều chỉnh khả năng truyền của các node không dây. Tính năng này được
cung cấp trên một vài sản card theo chuẩn 802.11, như là các sản phẩm của CISSCO
chẳng hạn.Ví dụ như card CISCO Aironet IEEE 802, 11 a / b / g có thể truyền với sức
mạnh vào khoảng từ 1 MW đến 100 MW. Trong thực tế các card không dây có thể tiêu
thụ năng lượng như là một hệ thống mạch tương tự hay kỹ thuật số. Như vậy, làm thế nào
để xây dựng mô hình thiêu thụ năng lượng sao cho hợp lý và hiệu quả, trong khi khả
năng hoạt động với tối đa sức mạnh của card không dây là chưa thực sự rõ ràng. Hầu hết
các phương pháp tiếp cận trong các tài liệu đều có liên quan đến sức mạnh truyền, nó
thường được mô hình hóa bằng các công thức được sử dụng trong chương 2, trừ khi có
15
một số các quy định khác được xác định, trong bài viết này chúng ta sẽ đơn giản hóa mô
hình tiêu thụ năng lương, cụ thể chúng ta sẽ sử dụng các định nghĩa về chi phí năng
lượng sau:
Định nghĩa 2.3.1(Chi phí năng lượng)
Cho một vùng ảnh hưởng RA của một mạng Md=(N, L) chi phí năng lượng cho
RA được tính theo công thức sau:
c(RA) =
RA(u)α
∑
u∈N
trong đó α là hệ số suy giảm năng lượng theo khoảng cách.
Lưu ý rằng định nghĩa của chi phí năng lượng được nêu ở phía trên là gắn liền với
giả thiết hoạt động của chúng ta, đó là những tín hiệu không dây lan truyền theo mô hình
log-distance path.
2.4. Mô hình hóa tính di động
Tính di động của những node là một trong những tính năng nổi bật trong mạng ad-
hoc. Như là một hệ quả tất yếu trong việc thiết kế các giao thức cho mạng ad-hoc, tính di
động là một phần quan trọng của việc thiết kế này.Từ thực tế là việc triển khai mạng ad-
hoc là khá khó, việc mô hình sự chuyển động thực là một công việc khá khó khăn, các
phương pháp tiếp cận phổ biến là sử dụng các mô hình tổng hợp và sự mô phỏng.
Mô hình hóa tính di động của mạng ad-hoc thường là:
Mô phỏng sự chuyển động: dành cho những ứng dụng của mạng ad-hoc trong một
diện rộng, mô hình phải mô hình được những sự chuyển động trong một khu vực rộng
lớn với nhiều thành phần tham gia: từ sự chuyển động của những sinh viên trong khuôn
viên trường tới những chiếc xe đang lưu thông trên đường cao tốc hay từ sự di chuyển
của các nhóm du lịch trên các vùng núi hay là những đội cứu hộ đang hoạt động trên
những khu vực thiên tai. Cung cấp một mô hình di động phù hợp với tất cả các loại hình
di động gần như là một công việc không thể thực hiện.Tuy nhiên một mô hình di động ít
nhất phải mô tả được tính chất của một ứng dụng nào đó.
Đơn giản hóa việc mô phỏng/ phân tích: cho đến khi việc mô hình hóa tính di
động được sử dụng trong mạng ad-hoc, thì mô việc mô hình hóa này nên được đơn giản
hóa bằng cách tích hợp thêm các sự mô phỏng theo một khoảng thời gian hợp lý. Hơn
nữa bằng cách sử dụng những mô hình tương đối đơn giản sẽ làm cho việc phân tích các
16
thông số của mạng ad-hoc trở nên dễ dàng hơn. Lần lượt các kết quả này có thể được sử
dụng để tối ưu hóa hiệu suất thực thi của các giao thức mạng ad-hoc.
Rõ ràng hai tiêu chí trên là mâu thuẫn: Mô hình thực tiễn thường có rất nhiều chi
tiết phải được bao gồm trong mô hình này và mô hình này sẽ ngày càng trở nên phức tạp.
Mặt khác việc mô phỏng, phân tích thì phải đơn giản để việc thiết kế các giao thức thực
thi cho mạng ad-hoc trở nên dễ dàng hơn. Như vây việc mô hình hóa tính di dộng phải
cân bằng được giữa tính chi tiết và việc đơn giản hóa, đó là chỉ xem xét đến các tính
năng nổi trội của mô hình chuyển động, trong khi chúng ta sẽ bỏ qua các chi tiết ít được
để ý hơn. Và trong chương này chúng ta sẽ mô tả ngắn gọn những mô hình di động quan
trong được sử dụng trong việc mô phỏng mạng ad-hoc
Mô hình Random waypoint (RWP): Đây là mô hình thông dụng nhất được sử dụng
trong mạng ad-hoc. Mô hình Random waypoint đã được giới thiệu trong một số tài liệu
và đã được thực thi trong giao thức đinh tuyến DSR ( Dynamic Source Routing). Trong
mô hình này mỗi node sẽ thống nhất chọn một điểm đích ngẫu nhiên (‘way point’) trong
một vùng R và di chuyển tới điểm đã chọn theo một đường thẳng. Tốc độ dịch chuyển
của node nằm được thống nhất chọn ngẫu nhiên trong khoảng [vmin, vmax] với vmin và vmax
là tốc độ dịch chuyển nhỏ nhất và lớn nhất của các node. Khi node di chuyển đến điểm
đến, sau đó nó sẽ dừng lại với một khoảng thời gian được xác định từ ban đầu. Sau đó nó
sẽ đi chuyển trở lại theo cùng một khuôn mẫu.
Mô hình RWP biểu diễn những sự di chuyển cá thể của node. Mỗi node di chuyển
độc lập với nhau và chúng có thể di chuyển bất kỳ trong khu vực R. Ví dụ như những
chuyển động tương tự được sinh ra khi những người dùng di chuyển trong một phòng lớn
hay trên một môi trường bằng phẳng. Do tính phổ biến mô hình RWP đã được ngiên cứu
nhiều hơn trong các tài liệu
Mặc dù mô hình này còn tương đối đơn giản nhưng trong tương lai những mô
hình RWP sẽ được khái quát hóa để ngày càng phù hợp với thực tế, Ví dụ mô hình RWP
sẽ cho phép một node bất kỳ dừng lại trong quá trình chuyển động tới đích theo một xác
suất ngẫu nhiên nào đó.
Mô hình hướng ngẫu nhiên (Random direction model (RDM)). Tương tự như mô
hình RWP, mô hình RDM cũng hướng theo việc mô hình hóa sự di chuyển cá nhân và có
xu hướng tự do.Mô hình này sẽ được tạo ra với một vùng tròn có bán kính R, với node là
trung tâm. Trong mô hình này các node sẽ chọn ngẫu nhiên một hướng trong khoảng từ
[0,2π] và tốc độ ngẫu nhiên trong khoảng [vmin,vmax]. Và sau đó node sẽ di chuyển theo
17
hướng đã được chọn và với tốc độ cũng đã được chọn. Khi nó đạt tới ranh giới R, nó sẽ
chọn một hướng mới và tốc độ mới
Brownian-like motion: ngược với mô hình di động RWP và RDM , những mô hình
này chuyển động có sự định hướng trước (điểm đích hoặc theo hướng ), mô hình
Brownian-like motion sẽ mô tả sự di chuyển một cách tự do, thi thoảng mô hình này còn
được gọi là mô hình drunkardlike
Trong mô hình Brownian-like motion, vị trí của một node tại một bước thời gian
phụ thuộc vào vị trí của node tại thời điểm trước đó.Cụ thể, tính chất di chuyển có đinh
hướng hay vận tốc di chuyển đều không được sử dụng tại mô hình này. Tính di động
được mô hình hóa bằng 3 tham số sau đây:
pstart, pmove, và m, Tham số đầu tiên thể hiện xác suất node ở trạng thái dừng trong toàn bộ
thời gian mô phỏng, pmove thể hiện xác suất, xác suất node sẽ di chuyển trong một bước
thời gian., m là tham số mô hình, tại một số mức, tốc đô: nếu một node đang di chuyển ở
bước i,vị trí của nó ở bước tiếp theo i+1 là một vị trí được chọn ngẫu nhiên trong vòng
bán kính là 2m với tâm là vị trí hiện thời của node.
Map-based mobility: Trong tất cả các mô hình đã giới thiệu từ trước đến giờ các
node được tự do di chuyển trong khu vực triển khai R. Tuy nhiên trong nhiều tình huống
thực tế, các node thường bị bắt buộc di chuyển theo một đường đặc biệt nào đó. Đây là
một trường hợp, chẳng hạn những chiếc xe di chuyển trên một xa lộ hay mọi người đi bộ
đều di chuyển trên vỉa hè, vv. Mô hình Map based sẽ được sử dụng để mô phỏng các tình
huống trên. Bước đầu tiên trong việc tạo nên mô hình Map based là thiết lập một bản đồ,
đó là định nghĩa những đường di chuyển trong đó các node sẽ được phép di chuyển trên
đó. Sau đó một số node có vị trí ngẫu nhiên nằm trên những con đường này và chúng sẽ
di chuyển theo lộ trình đã được quy định cụ thể.
Một ví dụ của mô hình map based mobilily là mô hình Freeway Mobiliy, chúng
được sử dụng để mô phỏng sự di chuyển của những chiếc xe trên xa lộ, trong mô hình
này một số xa lộ sẽ được xác định trong khu vực triển khai. Mỗi xa lộ sẽ bao gồm 1 con
đường và có 2 hướng. Node sẽ có vị trí ngẫu nhiên trên xa lộ, và chúng sẽ di chuyển với
vận tốc ngẫu nhiên, vận tốc này sẽ phụ thuộc theo thời gian vao vận tốc trước đó của nó.
Nếu 2 node mà trong cùng một làn xe với một khoảng cách tối thiểu (khoảng cách an
toàn) thì tốc độ của nó sẽ không được vượt quá tốc độ của node bên trên nó.
Một mô hình khác của map based mobilily là mô hình Manhattan mobility, chúng
được sử dụng để mô phỏng sự di chuyển … Đầu tiên Manhatta như là một bản đồ bao
18
gồm chiều dọc và chiều ngang của những con đường sẽ được tạo ra. Các node sẽ di
chuyển dọc theo những con đường theo hai hướng. Khi node di chuyển đến một chỗ cắt,
nó sẽ chọn ngẫu nhiên một con đường, có thể là đi thẳng theo hướng như ban đầu hoặc có
thể rẽ phải hoặc rẽ trái. Tương tự như mô hình FreeWay tốc đô hiện thời của node phụ
thuộc vào tốc độ trước đó của node theo bước thời gian.
Ví dụ thứ 3 của mô hình Map- based là mô hình the Obstacle mobility, trong mô
hình này bản đồ được tạo ra đầu tiên là thêm các vật cản (những tòa nhà chẳng hạn)
những trở ngại được thêm vào có thể được lấy một cách ngẫu nhiên hoặc dựa trên bản đồ
thực tế. Một khi các công trình xây dựng được triển khai những con đường nối những
công trình này sẽ được tạo ra và những node sẽ được giả định di chuyển theo những con
đường này. Một tính năng thú vị của mô hình này đó là những vật cản cũng được tính
toán cho việc mô phỏng tín hiệu được lan truyền trong môi trường. Nói cách khác mô
hình này còn giả định được những tín hiệu sẽ bị cản bởi các vật cản trong môi trường
Group-based mobility: Tất cả những mô hình được giới thiệu từ trước đều mô
phỏng sự di chuyển của từng cá thể. Tuy nhiên trong nhiều tình huống các node có thể di
chuyển theo một nhóm (ví dụ như một nhóm du lịch di chuyển trong thành phố) Group-
based Mobility được tạo ra để mô hình những tình huống như trên.Trong mô hình Group-
based Mobility một nhóm nhỏ các node mạng được coi như là những trưởng nhóm
(group leaders). Những node còn lại sẽ được gán ngẫu nhiên với những trưởng nhóm tạo
thàn một nhóm.Đầu tiên các nhóm trưởng sẽ ngẫu nhiên phân phối vùng triển khai R và
các thành viên trong nhóm sẽ có vị trí ngẫu nhiên trong vùng R và là ‘hàng xóm’ của
trưởng nhóm.Sau đó các trưởng nhóm sẽ di chuyển theo một mô hình đã được giới thiệu
ở phía trên, Chẳng hạn như là RWP hay RDM. Các thành viên trong nhóm sẽ làm theo
người đứng đầu, các thành viên này sẽ có hướng và tốc độ theo hướng và tốc độ của
trưởng nhóm. Khi hai nhóm giao nhau, một thành viên bất kỳ có thể rời nhóm của nó và
gia nhập vào một nhóm khác theo một xác suất đã biết. Chi tiết về mô hình Group-based
Mobility có thể tham khảo ở một số tài liệu khác như Hong et al. 1999; Wang and Li
2002
19
Chương 3. Tối ưu hóa Topology
3.1. Vấn đề về vùng ảnh hưởng
Trong chương này chúng ta sẽ xem xét các vấn đề để phân bố được một cấp độ
truyền để tạo ra một đồ thị truyền thông với một khoảng thời gian trong khi sẽ giảm thiểu
được sự tiêu thụ năng lượng. Vấn đề này được hiệu như là một vấn đề của vùng ảnh
hưởng
3.1.1. Định nghĩa vấn đề
Chúng ta nhắc lại rằng, thiết lập cho tập hợp những node N trên mạng, một vùng
ảnh hưởng cho N là một hàm RA, hàm này sẽ gán cho mỗi node thuộc N một vùng ảnh
hưởng RA(u) với 0 < RA(u) ≤ rmax với rmax là vùng ảnh hưởng lớn nhất. Chú ý rằng, dưới
giả thuyết là mô hình Path Loss được sử dụng cho mọi Node, và hiệu ứng
Shadowing/fading không được xem xét, và vùng truyền (Transmitting Range) và cấp độ
truyền (transmit power level) là những khái niệm tương đương. Hàm RA trước đây được
định nghĩa như là các quy tắc về phạm vi thay vi sức mạnh và chúng ta vẫn giữ những
quy ước này. Những vấn đề về Range Assigment được định nghĩa như sau:
Định nghĩa 3.1.1(Vấn đề RA): Cho N là tập hợp những node trong không gian d
chiều (d= 1, 2, 3) Một hàm range assigment RA được xác định tương đương như là một
đồ thị truyền thông với những kết nối mạnh, và c(RA) = u∈N (RA(u))α là hàm kết nối tất
∑
cả các RA với một khoảng cách nhỏ nhất, với α là độ suy giảm cường độ theo khoảng
cách.
Chi phí đo c( RA ) được sử dụng trong định nghĩa vấn đề RA là tổng cấp độ
truyền( Transmit Power levels) được sử dụng tại các node trong mạng. Vì vậy một vấn đề
của RA có thể thực sự được bắt đầu với việc tìm một RA ‘minimal’ với những node, với
RA này các node sẽ kết nối với nhau để tạo thành một đồ thị truyền thông, và minimal ở
đây có thể được hiểu là ‘chi phí năng lượng nhỏ nhất’. Bên cạnh việc giảm thiểu sự tiêu
thụ năng lượng việc kết nối RA với sự tiêu thụ năng lượng nhỏ này sẽ giúp phần tăng
thêm khả năng của mạng
20
3.1.2. Vấn đề RA trong những mạng một chiều (One-Dimensional Networks).
Trong phần này chúng ta sẽ giới thiệu một số thuật toán cho việc tìm kiếm những
giải pháp cho vấn đề RA.Trước khi trình bày thuật toán chúng ta cần định nghĩa một cách
sơ bộ
Cho N là một tập hợp những điểm (Node) nằm trên một đường thẳng.Không mất
tính tổng quát, chúng ta giả sử rằng các node được sắp xếp tăng dần tùy thuộc theo tọa độ
trong không gian, chẳng hạn như u1 là node bên trái nhất và un là node bên phải nhất. Cho
một bộ những node và một RA, chúng ta gọi những cạnh (ui, uj) trong đồ thị truyền thông
thu được là một backward nếu mà i > j, có nghĩa là cạnh đi từ phải sang trái. Với bất kỳ i,
j nào (1≤ i < j ≤ n) chúng ta định nghĩa tập hợp Ei,j gồm tất cả các cạnh backward có
điểm đầu cuối thuộc {ui , uj}, Ei,j = {(us, ur) : i≤ r < s ≤ j} Một số cạnh backward được
giới thiệu trong hình bên dưới. (Những cạnh bôi đen là những cạnh backward)
Hình 4: Các cạnh backward
Thuật toán cho việc tìm kiếm một giải pháp tối ưu dựa trên nền tảng là những phép đệ
quy. Cho một RA tối ưu kết nối cho các node (u1, uk) với 1≤ k <n , sau đó chúng ta sẽ
xây dựng được một RA tối ưu kết nối cho (u1, uk+1). Tư tưởng chính của thuật toán này là
khi chúng ta đã có một RA tối ưu với k node là RAk thì RA tiếp theo có thể được xác
định. Giả sử chi phí của RAk là 0 (giả thiết, nghĩa là c(RAk) cũng bằng 0) và khi có thêm
một node gia nhập thêm vào thì chi phí của RAk+1 sẽ được tăng lên một giá trị đã được
xác định điều này được thể hiện trong định nghĩa sau:
Định nghĩa 3.2.1 (RA increamental cost)
Cho N = {u1, . . . , un} là một tập hợp các node và E là bộ những cạnh giữa những
node trong N. RA được sinh ra bởi E được gọi là RAE , RAE là “minimal assignment” khi
RAE(ui)≥ δ (ui ,u j ) với bất kỳ một cạnh có hướng (ui, uj)∈ E.Chi phí tăng thêm của range
assignment liên quan tới E được gọi là cE(RA), được xác định như sau: cE(RA) =
(RA(ui ))α . Chúng ta gọi những cạnh trong E là ‘free of cost ’ đối với range
∑
i:RAE (ui )≠RA(ui )
assignment RA.
21
Những giả thiết dựa trên nền tảng của thuật toán quay lui, với bất kỳ j ≤ k và bất kỳ l ≥
k, tồn tại một Range assigment RA với một chi phí nhỏ nhất trong số các đồ thị truyền
thông sẽ có các thuộc tính sau đây:
- Giữa một cặp node bất kỳ đều có đường tồn tại
- Có một cạnh nối trực tiếp giữa ui và ul, l<=i <=k
- Với bất kỳ một cạnh (backward) trong E thì đều free of cost với RA
Cho (N’, E) là một đồ thị kết nối tất cả các node N’ và có các cạnh là E, và N’ ⊂ N, và
khi đồ thị này nhận thêm một node v trong N chúng ta gọi là reciever node. Một Range
assigment được gọi là total cho ((N’ , E), v) khi và chỉ khi:
- Đồ thị được tạo ra bởi N’ node thu được bằng cách thêm vào các cạnh của E tạo
nên một kết nối mạnh nghĩa là (RA(ui) ≥ δ(ui, uj ))
- Đều tồn tại cạnh giữa (u,v ) với ui∈ N và kết nối giữa v và ui là mạnh nghĩa là
(RA(ui) ≥ δ(ui, v ))
Chi phí của cho tổng Range assigment của ((N’ , E), v) là chi phí được tăng thêm liên
quan đến RAE, hay như định nghĩa về RA increamental cost là cE(RA). Như vậy tổng
cộng range assigment cho ((N’ , E), v) với một chi phí nhỏ nhất được gọi là tối ưu . Trong
phần sau đây chúng ta gọi Feas((N’ , E), v) là tập hợp những range assigment Feas((N’ ,
E), v) và Opt ((N’ , E), v) là tập hợp những optimal range assigment. Cuối cùng, cho u ∈
N và một đại lượng xác thực là r, chúng ta coi rằng Opt((N’, E), v, (u, r))) là tập hợp
những range assigment với chi phí nhỏ nhất và RA(u) = r.
Thuật toán Optimal1dRA để tìm ra giải pháp tối ưu cho vấn đề RA được trình bày
sau đây:
1. Khởi tạo
1.1 Cho RAi có Range assigment là RAi (u1) = δ(u1, ui), và RAi(u1) = 0
nếu i =0
1.2 Nếu không for i = 2 … n khởi tạo Opt(({u1}, ∅), ui) = RAi
2. Bước k
2.1 Giả sử chúng ta biết Opt(({u1, . . . , uk}, Ei,k), ul) ,với bất kỳ 1≤ i
<≤ k và k ≤ l ≤ n.
2.2 Với j, m bất kỳ , 1 ≤ j ≤ k + 1 ≤ m ≤ n
2.3. Xét tất cả các giá trị có thể của RA(uk+1) (tương tự với k+2 )
22
2.4 for với mỗi giá trị của r, tìm một range assignment RA trong
Opt(({u1, . . . , uk}, Ej,k+1), uk+1, (uk+1, r))
2.5. Nếu RA có chi phí nhỏ hơn so với RA hiện thời cho j , m thì lưu
RA
2.6. Kết thúc bước k, chúng ta biết một range assignment
Opt(({u1, . . . , uk+1}, Ei,k+1), ul), với bất kỳ 1 ≤ i ≤ k + 1 ≤ l ≤ n
3. ở bước n
Một Range assignment tối ưu chính là một trong Opt(({u1, . . . , un},
∅), un)
Tư tưởng chính của thuật toán này là: đầu tiên khởi tạo một RAi(u1) nếu i là 1 thì RA1(u1)
= 0
Nếu i khác 1 thì tìm các RA tối ưu của u1 với bất kỳ 1 node khác.
Trong bước đệ quy giả sử chúng ta đã biết Opt(({u1, . . . , uk}, Ei,k), ul) với bất kỳ
1≤ i ≤ k và k≤ l ≤ n. với mỗi node thêm vào chúng ta tìm được một RA tối ưu khi thêm
vào mỗi node đó
Tại bước cuối cùng khi thêm một node cuối cùng chúng ta sẽ tìm được một RA tối
ưu nhất cho toàn bộ node N.
Các nhà nghiên cứu đã chứng minh được độ phức tạp của thuật toán này là O(n4).
So sánh thuật toán Optimal1dRA khi tìm kiếm một RA tối ưu với giả thiết là các
Transmitting Range là bằng nhau thì thuật toán sẽ đơn giản hơn rất nhiều .
3.1.3. Vấn đề RA trong mạng 2 và 3 chiều
Trong phần trước, chúng ta đã phân tích được vấn đề RA trong mạng 1 chiều. So
với vấn đề trong mạng 1 chiều thì vấn đề tính toán trở nên phức tạp hơn nhiều, sự tính
toán này cũng là một vấn đề lớn trong mạng 2 và 3 chiều này.
Mặc dù giải pháp cho mạng 2 và 3 chiều là một công việc khó khăn, nhưng một
giải pháp tối ưu xấp xỉ có thể dễ dàng được tính toán bằng cách xây dựng một Minimum
Spaining Tree (MST) trên các node.
Sự xây dựng một RA được tiến hành như sau:
1. Cho N= {u1, . . . , un} là một tập hợp những điểm (Node) trong không
gian mạng 2 hoặc 3 chiều
23
2. Xây dựng một đồ thị vô hướng G = (N, E), với các cạnh là (ui, uj) ∈ E
3. Tìm một MST của G
4. Xác đinh một RAT với RAT(ui) = MAXj|(ui,uj) Tδ(ui, uj).
∈
Một ví dụ về cây MST và tương ứng với những RAT được miêu tả trong hình bên dưới
Hình 5: Minimum Spanning Tree
Thời gian xây dựng RAT là O(n2) (Độ phức tạp của thuật toán khi xây dựng MST với n
node)
Định lý 3.2.3: (Kirousis et al. 2000)
Cho một tập hợp những điểm (nodes) trong không gian 2 hoặc 3 chiều, và cho
RAT được định nghĩa như trên, cho RA là một optimal range assignment với vấn đề RA
thì
c(RAT) < 2c( RA ).
Chứng minh: Việc chứng minh được thực hiện qua hai bước. Trước tiên chúng ta chứng
minh c( RA ) lớn c(T) nghĩa là chi phí của RA lớn hơn chi phí cả MST. Và sau đó chúng
ta sẽ chứng minh c(RAT) < 2c( RA ).
24
Tải về để xem bản đầy đủ
54 trang
24/06/2025
1790
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Tối ưu hóa topology trong mạng AD-HOC", để 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:
- khoa_luan_toi_uu_hoa_topology_trong_mang_ad_hoc.pdf
