Đánh giá ảnh hưởng của sự mở rộng mạng đến thông lượng tổng cộng của mạng adhoc bằng mô phỏng

  • 37 trang
  • file .pdf
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Quang Hưng
ĐÁNH GIÁ ẢNH HƯỞNG CỦA SỰ MỞ RỘNG
MẠNG ĐẾN THÔNG LƯỢNG TỔNG CỘNG
CỦA MẠNG ADHOC BẰNG MÔ PHỎNG
LUẬN VĂN THẠC SĨ
HÀ NỘI - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Quang Hưng
ĐÁNH GIÁ ẢNH HƯỞNG CỦA SỰ MỞ RỘNG
MẠNG ĐẾN THÔNG LƯỢNG TỔNG CỘNG
CỦA MẠNG ADHOC BẰNG MÔ PHỎNG
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS.NGUYỄN ĐÌNH VIỆT
HÀ NỘI - 2011
MỤC LỤC
BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT
LỜI MỞ ĐẦU 1
CHƢƠNG 1. TỔNG QUAN VỀ MẠNG AD HOC 2
1.1. Tổng quan về mạng Ad hoc ............................................................................................. 2
1.2. Những sự thách thức ....................................................................................................... 5
1.3. Kết luận........................................................................................................................... 7
CHƢƠNG 2. ẢNH HƢỞNG CỦA SỰ MỞ RỘNG ĐẾN THÔNG LƢỢNG TỔNG CỘNG CỦA
MẠNG AD HOC 8
2.1. Mạng tùy chỉnh[1]: vị trí các nút và mẫu lƣu lƣợng là tùy ý ............................................. 8
2.2.1 Mô hình giao thức [1] ............................................................................................. 9
2.2.1 Mô hình vật lý [1] .................................................................................................. 9
2.2.3 Dung lƣợng vận chuyển của Mạng tùy chỉnh [1] .................................................. 10
2.2. Mạng ngẫu nhiên[1]: vị trí các nút và các mẫu lƣu lƣợng là ngẫu nhiên ......................... 12
2.2.1 Mô hình giao thức [1] ........................................................................................... 12
2.2.2 Mô hình vật lý [1] ................................................................................................ 13
2.2.3 Thông lƣợng của Mạng ngẫu nhiên [1] ................................................................. 13
CHƢƠNG 3. GIỚI THIỆU BỘ MÔ PHỎNG NS-2 16
3.1. Giới thiệu bộ mô phỏng NS-2 ........................................................................................ 16
3.2. Cấu trúc NS-2 ............................................................................................................... 16
3.3. Các đặc tính của NS-2 ................................................................................................... 18
3.4. Mô phỏng mạng Ad hoc bằng NS-2 [11] ....................................................................... 19
3.4.1 Mô hình mạng không dây đơn giản trong NS2 .......................................................... 19
3.4.2 Tạo topo mạng không dây ......................................................................................... 19
3.4.3 Tạo ra sự các hoạt động cho Nút ............................................................................... 21
3.4.4 Các thành phần cấu thành mạng trong một mobilenode [11] ..................................... 23
3.4.5 Các lệnh cơ bản sử dụng trong các trình mô phỏng wireless [8], [11] ........................ 23
3.4.6 Các thủ tục cơ bản sử dụng trong các trình mô phỏng wireless [8], [11] .................... 25
CHƢƠNG 4. THÍ NGHIỆM MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT QUẢ 27
4.1. Ý tƣởng xây dựng một chƣơng trình mô phỏng ............................................................. 27
4.2. Xây dựng chƣơng trình mô phỏng ................................................................................. 27
4.2.1 Xây dựng một mạng Ad hoc với các thông số cơ bản của node:............................ 27
4.2.2 Xây dựng các hàm có chức năng mô phỏng mạng Ad hoc .................................... 27
4.3. Xây dựng kịch bản di chuyển và thiết lập nguồn sinh lƣu lƣợng .................................... 28
4.4. Kết quả mô phỏng ......................................................................................................... 29
4.5. Nhận xét ........................................................................................................................ 30
CHƢƠNG 5. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 31
5.1. Kết luận......................................................................................................................... 31
5.2. Hƣớng phát triển ........................................................................................................... 31
TÀI LIỆU THAM KHẢO 32
DANH MỤC HÌNH ẢNH
Hình 1: Mô hình mạng Ad hoc ............................................................................................... 2
Hình 2: Một số ứng dụng của mạng phân phối những điểm thu nhận thông tin ...................... 5
Hình 3: Cấu trúc của NS - 2 ................................................................................................. 17
Hình 4: Luồng các sự kiện cho file Tcl chạy trong NS-2 ....................................................... 18
Hình 5: Lược đồ của một mobilenode dưới chuẩn wireless của Monarch của CMU mở rộng
ra NS. .................................................................................................................................. 21
Hình 6: Quá trình chạy mô phỏng ........................................................................................ 29
Hình 7: Đồ thị thông lượng tổng cộng của mạng theo thời gian ........................................... 29
BẢNG CÁC KÝ HIỆU, CHỮ VIẾT TẮT
AODV Adhoc On-demand Distance MANET Mobile Adhoc NETwork
Vector
CSMA/CA Carrier Sense Multiple Access MPR Multi-Point Relays
with Collision Avoidance
CSMA/CD Carrier Sense Multiple Access NS-2 Network Simulator
with Collision Detection version 2
DARPA Defense Advanced Research OLSR Optimized Link State
Projects Agency Routing Protocol
DSDV Destination-Sequenced PRnet Packet Radio Network
Distance Vector
DSR Dynamic Source Routing RREP Route Reply
IEEE Institute of Electrical and RREQ Route Request
Electronics Engineers
LAN Local Area Network TORA Temporally-Ordered
Routing Algorithm
MAC Media Access Control WLAN Wireless LAN
1
LỜI MỞ ĐẦU
Công nghệ mạng Ad hoc là một công nghệ mới và hữu dụng trong số các công
nghệ mạng không dây. Công nghệ này cho phép các nút mạng giao tiếp trực tiếp với
nhau bằng cách sử dụng máy thu phát vô tuyến mà không cần có cơ sở hạ tầng cố
định. Đây là một đặc trưng riêng của mạng Ad hoc so với các mạng truyền thống trước
đây như mạng di động kiểu tế bào (cellular) hay mạng LAN không dây, trong đó các
nút giao tiếp với nhau thông qua trạm gốc (Base Station). Tuy nhiên, mạng Ad hoc
phải đối mặt với một số thách thức như giới hạn phạm vi truyền dẫn, vấn đề trạm ẩn,
mất gói do lỗi đường truyền, sự chuyển động của các nút mạng làm thay đổi tuyến
đường, sự ràng buộc về băng thông và năng lượng, sự mở rộng của số lượng nút mạng.
Trong phạm vi luận văn này, tôi tập trung đưa ra đánh giá ảnh hưởng của sự mở
rộng mạng đến thông lượng tổng cộng của mạng Ad hoc bằng phương pháp mô phỏng.
Khoá luận được chia làm 5 chương:
- Chương 1: Tổng quan về mạng Ad hoc
- Chương 2: Ảnh hưởng của sự mở rộng mạng Ad hoc đến thông lượng tổng
cộng của mạng.
- Chương 3: Giới thiệu bộ mô phỏng NS2
- Chương 4: Mô phỏng và đánh giá kết quả.
- Chương 5: Kết luận và hướng phát triển tiếp theo của luận văn.
2
CHƢƠNG 1. TỔNG QUAN VỀ MẠNG AD HOC
Chương này trình bày tổng quan về mạng Ad hoc, các ứng dụng trong nhiều lĩnh
vực cuộc sống của mạng Ad hoc. Đồng thời, đề cập đến các thách thức mà mạng Ad
hoc đang phải đối mặt.
1.1. Tổng quan về mạng Ad hoc
Mạng Ad hoc là một loại mạng mới ra đời trong số các mạng truyền thông
không dây. Trong mạng Ad hoc, các node mạng vừa có thể di động vừa có thể truyền
thông với những node khác sử dụng những bộ thu/phát không dây mà không cần sử
dụng một cơ sở hạ tầng mạng cố định. Các nút mạng Ad hoc có thể truyền thông với
nhau kể cả khi giữa chúng không có liên kết không dây trực tiếp, nhờ việc mọi nút
mạng đều được trang bị chức năng của một router để có thể chuyển tiếp các gói tin
cho các nút khác. Điều này là một đặc điểm khác biệt rất lớn của mạng Ad hoc so với
các mạng không dây cổ điển như mạng truyền thông di động kiểu tế bào (cellular) hay
mạng LAN không dây (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 được kết nối với nhau và
kết nối với mạng có dây (thường là Internet).
Mạng Ad hoc đang được trông đợi sẽ làm nên một cuộc cách mạng 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 trên toàn cầu.
Hình 1: Mô hình mạng Ad hoc
3
Những ứng dụng trong tương lai theo xu hướng công nghệ mạng Ad hoc chắc
chắn sẽ chứng minh được 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 lạc của một thành phố lớn (gồm: hệ thống đường dây điện thoại, các trạm cơ sở
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 vùng bị thảm họa đó để cứu người. Để 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 máy 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
truyền thô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.
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 bị 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; Phần dưới đây trình bày các đặc điểm chính của
mạng này.
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ụ ở 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.
4
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 ví dụ trên.
Mạng phân tán: các nút trong mạng Ad hoc có thể 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
(truyền trực tiếp giữa nút gửi và nút nhận) 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 ứng dụng sau đây là có nhiều tiềm năng nhất:
Phân phối nhanh chóng lưu lượng truy cập các mạng viễn thông và Internet
trên các đường cao tốc và tại các khu đô thị: Những tuyến đường cao tốc và các khu
đô thị có thể được trang bị những trạm thu/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 (thí dụ thu tín hiệu GPS,
Wi-fi,...). Các xe hoạt động gần các trạm thu/phát có thể cập nhật được thông tin về
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 thông tin chính xác và nhanh chóng hơn.
Truy cập Internet khắp nơi: Ngày nay, tại hầu hết những khu vực công cộng
như, sân bay, nhà ga, khu mua sắm cao cấp, đều đượ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, cho cả những người không ở gần các điểm truy cập.
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ụ thu nhận 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. …
Ứng dung cho ma
5
Hình 2: Một số ứng dụng của mạng phân phối những điểm thu nhận thông tin
1.2. Những sự thách thức
Mặc dù các công nghệ có thể áp dụng 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 trong các
nguyên nhân chính của thực tế này 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à
nghiên cứu và các ngành công nghiệp trong những năm gần đây; kết quả của một loạt
các hoạt động nghiên cứu là 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. Thí dụ một số chuẩn được sử dụng phổ biến nhất là chuẩn
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 đa chặng (multihop) giữa các thiêt bị khác nhau
như điện thoại di động, máy tính xá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.
Nguyên nhân của việc có rất ít ứng dụng mạng Ad hoc đó 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 sử dụng
nguồn năng lượng pin được gắn cùng, do đó, một trong những mục tiêu chính của việc
thiết kế mạng là làm 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ị biểu diễn cho các nút
6
mạng và 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 node có thể 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 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 bị ảnh hưởng bởi các yếu tố môi trường (như: điều kiện
thời tiết, các vật cản, sự can nhiễu tín hiệu của các mạng không dây khác, …).Vì vậy
các ứng dụng cho mạng Ad hoc cần phải 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à 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 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 thì dữ liệu sẽ đi qua hầu hết các các mạng thành phần của mạng hỗn
hợp này: Ad hoc, cellular, vệ tinh, wireless LAN, Internet, v.v. 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. Để thực hiện
được điều này thì quả thực là một nhiệm vụ rất khó khăn về công nghệ.
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.
7
1.3. Kết luận
Chương này đã trình bày tổng quan về mạng Ad hoc. Trong mạng Ad hoc, topo
mạng thường xuyên thay đổi. Do vậy, các nút mạng đều phải thực hiện chức năng của
một router và giao thức định tuyến trong mạng Ad hoc cần giải quyết sự di chuyển của
nút, ràng buộc năng lượng và băng thông.
8
CHƢƠNG 2. ẢNH HƢỞNG CỦA SỰ MỞ RỘNG ĐẾN THÔNG LƢỢNG
TỔNG CỘNG CỦA MẠNG AD HOC
Do trong mạng Ad hoc, các nút mạng đều sử dụng sóng radio để truyền thông
với nhau, nên khi có một nút đang truyền, tất cả các nút mạng trong vùng không gian
xung quanh nó, nếu nhận được tín hiệu với cường độ lớn hơn một ngưỡng nhất định,
đều coi là môi trường truyền bận (đã được sử dụng) và không truyền. Như vậy, việc
mở rộng mạng, có thể là sự tăng mật độ nút, hoặc là tăng số nút trong mạng, đều ảnh
hưởng tới hiệu năng mạng, trong đó tham số hiệu năng chính là tổng thông lượng mà
mạng Ad hoc có thể vận chuyển.
Người ta thường đánh giá hiệu năng của mạng Ad hoc thông qua các tham số
sau đây:
- Tỷ lệ gói nhận được: Là tỷ lệ giữa số gói được nhận bởi nút mạng đích và số
gói được gửi đi từ lớp ứng dụng của nút nguồn (nút gửi).
- Phần tải thông tin định tuyến: Là tải sinh ra do hoạt động định tuyến, cho biết
hiệu năng sử dụng băng thông của giao thức định tuyến.
- Trễ từ đầu cuối đến đầu cuối: Là thời gian mà gói tin truyền trên mạng từ nút
mạng nguồn đến nút mạng đích.
- Thông lượng từ đầu cuối đến đầu cuối: Là lượng thông tin truyền thành công
đến nút mạng đích trong một đơn vị thời gian (Kbps).
- Tải của mạng: Tải thật sự mà mạng vận chuyển, tải có thể được đo bằng số gói
tin vận chuyển được trong một đơn vị thời gian, hoặc số lượng kết nối thực hiện
được,...
Trong khuôn khổ luận văn này, chúng tôi chỉ tập trung nghiên cứu ảnh
hƣởng của sự mở rộng mạng đến thông lƣợng tổng cộng của mạng Adhoc.
Chúng tôi sẽ xem xét trên hai loại hình mạng, Mạng tùy chỉnh[1], nơi vị trí các
node, điểm đích của điểm nguồn, và nhu cầu lưu lượng, tất cả đều tùy chỉnh, và Mạng
ngẫu nhiên[1], nơi các node và điểm đích được chọn hoàn toàn ngẫu nhiên
2.1. Mạng tùy chỉnh[1]: vị trí các nút và mẫu lưu lượng là tùy ý
Trong thiết lập cấu hình mạng tùy chỉnh, chúng tôi giả định rằng n node được
đặt tùy ý trong một diện tích hình tròn có diện tích bằng một đơn vị. Mỗi node có một
nút đích được chọn tùy ý để gửi lưu lượng đến với tốc độ tùy chỉnh; do vậy mẫu lưu
lượng là tùy chỉnh. Mỗi node có thể chọn dải tần hoặc mức công suất tùy chỉnh cho
mỗi lần truyền.
Chúng tôi cần diễn giải rằng khi một nút truyền thành công tới một nút đã định
của nó; việc nhận thành công này có thể được mô hình hóa bằng 2 mô hình sau: Mô
9
hình Giao thức (Protocol Model) và Mô hình Vật lý (Physical Model), chúng sẽ được
miêu tả chi tiết dưới đây. Trong đó, Xi biểu hiện vị trí của node, chúng ta cũng sẽ
thường dùng Xi để chỉ chính node đó cho tiện.
2.2.1 Mô hình giao thức [1]
Giả định node Xi truyền qua kênh phụ (sub-channel) thứ m đến node Xj; Việc
truyền này được nhận thành công tại node Xj nếu
Xk Xj (1 ) Xi Xj (1)
Với mọi node Xk khác truyền đồng thời qua cùng kênh phụ nêu trên.
Có thể giải thích một cách đơn giản hơn như sau: nếu có 2 nút mạng i và k cùng
truyền đến nút j, việc truyền từ i đến j sẽ thành công nếu khoảng cách từ i đến j nhỏ
hơn khoảng cách từ k đến j.
Đại lượng >0 mô hình hóa cho các tình huống mà giao thức chỉ rõ cần có
vùng bảo vệ nhằm tránh việc các node lân cận đồng thời truyền trên cùng một kênh
phụ. Nó cũng cho phép độ sai số nhất định trong miền nhận tin cậy.
Dưới đây trình bày một mô hình khác gần với các vấn đề cần khảo sát của tầng
vật lý hơn.
2.2.1 Mô hình vật lý [1]
Ký hiệu {Xk; k } là tập con các node đồng thời truyền tại một thời điểm nào
đó qua cùng một kênh phụ cho trước. Ký hiệu Pk là mức công suất được chọn tại node
Xk, với k . Do đó, việc truyền từ node Xi, với i , được nhận thành công tại node X j
nếu:
Pi
Xi Xj
Pk (2)
N k i
k T
Xk Xj
10
Có thể giải thích ý nghĩa của biểu thức (2) như sau: nếu có 2 nút mạng i và k
cùng truyền đến nút j, việc truyền từ i đến j sẽ thành công nếu mật độ công suất tín
hiệu của nút i tại nút nhận j lớn hơn lần mật độ công suất tín hiệu của nút k tại j.
Trong đó mật độ công suất tín hiệu là công suất trên một đơn vị diện tích.
Biểu thức này là mô hình cho tình huống khi tỉ số tín hiệu trên nhiễu (SIR) cần
phải không được nhỏ hơn β để việc nhận là thành công, mức năng lượng nhiễu của
1
môi trường là N, và độ suy giảm công suất tín hiệu theo khoảng r là . Chúng ta giả
r
thiết rằng α > 2, đây chính là giá trị thường được sử dụng trong các mô hình tính công
suất tín hiệu ngoài vùng lân cận của thiết bị truyền.
2.2.3 Dung lƣợng vận chuyển của Mạng tùy chỉnh [1]
Giả thiết đã có một số sự kiện truyền thành công xảy ra trong một khoảng thời
gian và trong một không gian nào đó, chúng ta đưa ra một đơn vị đo lượng vận chuyển
của mạng là bit-meter, tương ứng với việc truyền đi được 1 bit qua khoảng cách 1m
hướng đến đích. (Chúng tôi không xét trường hợp truyền multicast). Đơn vị đo này
tương tự đơn vị tấn/km mà người ta vẫn hay sử dụng để đánh giá năng lực vận chuyển
của các phương tiện vận tải. Khi sử dụng đơn vị đo này, lượng vận chuyển của mạng
sẽ là tổng của các tích giữa số bit mà mạng vận chuyển với chiều dài quãng đường,
được cộng lại đối với tất cả các kết nối. Đây là một chỉ số quan trọng để đánh giá dung
lượng vận chuyển của mạng.
Đối với phần được trình bày tiếp dưới đây, chúng tôi xin lưu lý rằng, nếu như
diện tích của miền mà các nút mạng được đặt là A m2 thay vì 1m2 như chúng ta đã
chuẩn hóa, thì tất cả các kết quả tính dung lượng vận chuyển phải được nhân với A.
Kết quả chính đạt được như trình bày sau đây. Trong đó sử dụng ký hiệu của
Knuth: f(n)= (g(n)) để biểu diễn f(n)=O(g(n)) cũng như g(n)=O(f(n))
Kết quả chính 1. Dung lượng vận chuyển của mạng tùy chỉnh theo mô hình
giao thức là (W n ) bit/meter/giây nếu các node được đặt ở các vị trí tối ưu, các
mẫu lưu lượng được chọn tối ưu, và miền phát tín hiệu cũng được chọn tối ưu.
11
8W
Cụ thể, giá trị cận trên là n bit-met/giây với mỗi Mạng tùy chỉnh cho
tất cả các chiến lược lập biểu đồ theo thời gian và không gian, trong khi
W n
bit-met/giây (với n là bội của 4) là dung lượng vận chuyển có thể đạt
1 2 n 8
được khi các node và mẫu lưu lượng được chọn một cách phù hợp, miền phát tín hiệu
(radio range) và lịch truyền cũng được chọn tương thích.
Nếu dung lượng vận chuyển này được chia đều cho tất cả các node trong tập
W
hợp n node, mỗi node sẽ đạt được ( ) bit-met/giây. Hơn nữa, nếu mỗi nút nguồn
n
có một nút đích của nó cách đó cùng một khoảng bằng nhau là 1m, thì mỗi node nhận
W
được thông lượng là ( ) bit/giây.
n
Cận trên của dung lượng vận chuyển không phụ thuộc vào việc truyền phải là
đẳng hướng như đã ngầm chỉ ra trong biểu thức (1), mà phụ thuộc vào việc các nút
hàng xóm của nút nhận được phân bố như thế nào.
Kết quả chính 2. Đối với Mô hình vật lý, có thể đạt được thông lượng vận
1
chuyển bằng cW n bit-met/giây, nhưng không thể đạt được giá trị c'Wn bit-
met/giây, với các giá trị c, c’ thích hợp.
1 Wn
Cụ thể, 2 1
bit-met/giây (với n là bội của 4) là khả thi
2
6 n 8
(16 (2 ))
2
1 1
1 2 2
khi mạng được thiết kế một cách thích hợp, trong đó cận trên là ( ) Wn
bit-met/giây.
Người ta đoán rằng cận trên có bậc (W n ) bit-met/giây thực tế có thể đạt
Pm ax
được. Trong trường hợp đặc biệt khi tỷ số giữa công suất lớn nhất và nhỏ nhất
Pm in
12
mà thiết bị truyền có thể đạt được có giới hạn trên cao hơn β, khi đó cận trên thực tế là
8 1
1
W n bit-met/giây.
P
( m in ) 1
Pm ax
Đáng lưu ý rằng, biểu thức cho cả hai cận đều cho thấy dung lượng vận chuyển
sẽ được cải thiện khi α cao hơn, nghĩa là khi công suất tín hiệu suy yếu nhanh hơn theo
khoảng cách.
2.2. Mạng ngẫu nhiên[1]: vị trí các nút và các mẫu lưu lượng là ngẫu
nhiên
Trong kịch bản ngẫu nhiên, n node được đặt ở các vị trí ngẫu nhiên, tức là có
phân bố độc lập và đều, hoặc trên bề mặt có diện tích S2 của mặt cầu 3 chiều với diện
tích 1 m2, hoặc trên một hình tròn với diện tích 1 m2 trên mặt phẳng. Mục đích của
việc chọn nghiên cứu diện tích S2 là để loại bỏ hiệu ứng biên khỏi các hiện tượng khác.
Mỗi node có một nút đích được chọn ngẫu nhiên để gửi với tốc độ λ(n) bit/giây. Nút
đích của mỗi node được chọn một cách độc lập và là node gần nhất với một điểm được
xác định ngẫu nhiên, nghĩa là phân bố nút mạng là độc lập và đều. (Do vậy, khoảng
cách trung bình giữa các nút đích và nút nguồn trong toàn mạng là 1m)
Chúng ta cũng giả định rằng các node là đồng nhất, tức là mọi việc truyền đều
có cùng công suất và phạm vị truyền (radio range) danh định. Đối với Mạng tùy chỉnh,
chúng ta cho phép sử dụng cả hai mô hình: mô hình giao thức và mô hình vật lý.
2.2.1 Mô hình giao thức [1]
Tất cả các node đều sử dụng miền r chung cho tất cả các lần truyền. Khi node Xi
truyền đến node Xj qua kênh phụ thứ m, việc truyền này sẽ được nhận thành công tại
Xj nếu:
i) Khoảng cách giữa Xi và Xj không lớn hơn r, tức là:
Xi Xj r (3)
ii) Với mọi node Xk khác đồng thời truyền qua cùng một kênh phụ
13
Xk Xj (1 )r (4)
Ý nghĩa của biểu thức này có thể được giải thích hoàn toàn tương tự như đối
với mô hình giao thức của mạng tùy chỉnh, đã được trình bày ở phần trên.
2.2.2 Mô hình vật lý [1]
Tất cả các node chọn một mức công suất chung P cho tất cả các lần truyền của
nó. Ký hiệu {Xk; k T} là tập con các node đồng thời truyền tại một thời điểm nào đó
qua cùng một kênh phụ cho trước. Việc truyền từ node Xi, với i є Τ, được nhận thành
công tại node Xj nếu:
P
Xi Xj
(5)
P
N k i
k T
Xk Xj
Ý nghĩa của biểu thức này có thể được giải thích hoàn toàn tương tự như đối
với mô hình vật lý của mạng tùy chỉnh, đã được trình bày ở phần trên.
2.2.3 Thông lƣợng của Mạng ngẫu nhiên [1]
Khái niệm về thông lượng được định nghĩa theo cách thông thường là số bit
trung bình truyền được từ nguồn đến đích trong 1 đơn vị thời gian, được tính bằng
bit/giây:
Định nghĩa: Thông lƣợng khả thi. Thông lượng λ(n) bit/giây với mỗi node
được coi là khả thi nếu tồn tại một biểu đồ thời gian và không gian cho việc truyền,
sao cho bằng cách vận hành mạng theo kiểu đa chặng và lưu tạm thời các gói tin các
node trung gian trong khi chờ được truyền đi, mỗi node có thể gửi trung bình λ(n)
bit/giây tới node đích được chọn sẵn của nó. Điều đó có nghãi là, có một giá trị T<∞
sao cho trong mọi khoảng thời gian [(i-1)T, iT] mọi node đều có thể gửi T*λ(n) bit đến
node đích tương ứng của nó.
Mức thông lượng cụ thể có khả thi hay không phụ thuộc vào vị trí các node.
Các vị trí này đều là ngẫu nhiên. Điểm đích cho lưu lượng vào mỗi node cũng vậy.
14
Như trong Lý thuyết Học thuật PAC, giả định tính ngẫu nhiên bao hàm trong
báo cáo sự cố, chúng ta cho phép triệt tiêu các xác suất nhỏ khi xác định “thông
lượng”. [1]
Định nghĩa: Thông lƣợng của Mạng không dây ngẫu nhiên. Chúng ta cho
rằng thông lượng của loại mạng ngẫu nhiên có bậc là (f(n)) bit/giây nếu có các hằng
số xác định c>0 và c’<+∞ như sau:
lim Prob( (n)=cf(n) =1 là khả thi
n
lim in f n Prob( (n)=c’f (n) <1 là khả thi
Các kết quả chính người ta đã chứng minh được như sau:
Kết quả chính 3. Trong cả hai trường hợp ứng với diện tích mặt cầu và đĩa
W
phẳng, bậc của thông lượng là (n)=(-)( ) bit/giây đối với mô hình giao thức.
n log n
Về cận trên, người ta thực sự chứng minh được hiện tượng cắt sắc nét với một vài c’
W
lim Prob( (n)=c’ n log n là khả thi) =0
n
Cụ thể, có các hằng số xác định c” và c”’ không phụ thuộc vào n, ∆ hay W, sao
c "W c '"W
cho các giá trị (n)=( ) bit/giây khả thi, và (n)=( ) bit/giây
(1 ) 2 n log n 2
n log n
khả thi, cả hai đều có xác suất tiến tới 1 khi n →∞.
Do các điểm nóng về định tuyến (routing hot spots) có thể hình thành tại trung
tâm trong trường hợp của đĩa phẳng, và bậc của thông lượng là giống nhau cho cả hai
trường họp nói trên, điều đó thể hiện rằng nguyên nhân của việc thông lượng không
tăng lên được không phải là do sự hình thành các điểm nóng về định tuyến, mà là nhu
cầu của tất cả các node cần chia sẻ kênh cục bộ với các node khác.
15
cW
Kết quả chính 4. Đối với mô hình vật lý, thông lượng (n)=( ) bit/giây
n log n
c 'W
là khả thi, trong khi (n)=( ) bit/giây thì không, cho các giá trị thích hợp c, c’ , cả
n
hai biểu thức trên đều tiến tới 1 khi n →∞.
Cụ thể, có các các hằng số quyết định c” và c’” không phụ thuộc vào n, N, α, β
c '' W
hay W, sao cho các giá trị (n)= 1
bit/giây khả
1 2 n log n
(2(c '" (3 )) 1) 2
1 2
thi, xác suất tiến tới 1 khi n →∞. Nếu L là khoảng cách trung bình giữa hai điểm phân
bố độc lập và đều trên miền xác định (trên diện tích mặt cầu hoặc đĩa phẳng của diện
tích đơn vị), do đó có một dãy số xác định є(n) → 0, không phụ thuộc vào n, N, α, β
8 W 1 (n)
hay W, sao cho giá trị 1
bit/giây khả thi và có xác suất tiến tới 1
n
L( 1)
khi n →∞.