Thuật toán tìm đường Bellman Ford

Giống Dijkstra, đây là thuật toán tìm đường ngắn nhất nhưng đại thể là có ưu điểm hơn là giải quyết được đồ thị chu trình âm nhưng nhược điểm là đôi khi nó quét lại cả các nút đã quét nên hiệu suất không cao bằng. Ở viễn thông thì không biết có trường hợp nào đường đi nào có giá trị âm nên mình cũng khó đánh giá.
Cái kia mỗi lần quét thì thêm vào 1 giá trị nhỏ nhất vào tập hợp các đường đã biết, lần sau không phải quét nữa còn cái này cứ quét đại trà với vòng lặp bằng số đỉnh thì dừng.

Theo wiki

Thuật toán Bellman-Ford là một thuật toán tính các đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng có trọng số (trong đó một số cung có thể có trọng số âm). Thuật toán Dijkstra giải cùng bài toán này với thời gian chạy thấp hơn, nhưng lại đòi hỏi trọng số của các cung phải có giá trị không âm. Do đó, thuật toán Bellman-Ford thường chỉ được dùng khi có các cung với trọng số âm.
Thuật toán Bellman Ford chạy trong thời gian O(V·E), trong đó V là số đỉnh và E là số cung của đồ thị.

Nội dung thuật toán

function BellmanFord(danh_sách_đỉnh, danh_sách_cung, nguồn)
   // hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh sách cung
   // hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh, 
   // sao cho các giá trị đỉnh_liền_trước sẽ lưu lại các đường đi ngắn nhất.

   // bước 1: khởi tạo đồ thị
   for each v in danh_sách_đỉnh:
       if v is nguồn then khoảng_cách(v) := 0
       else khoảng_cách(v) := vô cùng
       đỉnh_liền_trước(v) := null
   
   // bước 2: kết nạp cạnh
   for i from 1 to size(danh_sách_đỉnh):       
       for each (u,v) in danh_sách_cung:
           if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v) :
               khoảng_cách(v) := khoảng_cách(u) + trọng_số(u,v)
               đỉnh_liền_trước(v) := u

   // bước 3: kiểm tra chu trình âm
   for each (u,v) in danh_sách_cung:
       if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v) :
           error "Đồ thị chứa chu trình âm"

Chứng minh tính đúng đắn

Tính đúng đắn của thuật toán có thể được chứng minh bằng quy nạp. Thuật toán có thể được phát biểu chính xác theo kiểu quy nạp như sau:
Bổ đề. Sau i lần lặp vòng for:

1. Nếu Khoảng_cách(u) không có giá trị vô cùng lớn, thì nó bằng độ dài của một đường đi nào đó từ s tới u;
2. Nếu có một đường đi từ s tới u qua nhiều nhất i cung, thì Khoảng_cách(u) có giá trị không vượt quá độ dài của đường đi ngắn nhất từ s tới u qua tối đa i cung.

Chứng minh.
Trường hợp cơ bản: Xét i=0 và thời điểm trước khi vòng for được chạy lần đầu tiên. Khi đó, với đỉnh nguồn khoảng_cách(nguồn) = 0, điều này đúng. Đối với các đỉnh u khác, khoảng_cách(u) = vô cùng, điều này cũng đúng vì không có đường đi nào từ nguồn đến u qua 0 cung.
Trường hợp quy nạp:
Chứng minh câu 1. Xét thời điểm khi khoảng cách tới một đỉnh được cập nhật bởi công thức khoảng_cách(v) := khoảng_cách(u) + trọng_số(u,v). Theo giả thiết quy nạp, khoảng_cách(u) là độ dài của một đường đi nào đó từ nguồn tới u. Do đó, khoảng_cách(u) + trọng_số(u,v) là độ dài của đường đi từ nguồn tới u rồi tới v.
Chứng minh câu 2: Xét đường đi ngắn nhất từ nguồn tới u qua tối đa i cung. Giả sử v là đỉnh liền ngay trước u trên đường đi này. Khi đó, phần đường đi từ nguồn tới v là đường đi ngắn nhất từ nguồn tới v qua tối đa i-1 cung. Theo giả thuyết quy nạp, khoảng_cách(v) sau i-1 vòng lặp không vượt quá độ dài đường đi này. Do đó, trọng_số(v,u) + khoảng_cách(v) có giá trị không vượt quá độ dài của đường đi từ s tới u. Trong lần lặp thứ i, khoảng_cách(u) được lấy giá trị nhỏ nhất của khoảng_cách(v) + trọng_số(v,u) với mọi v có thể. Do đó, sau i lần lặp, khoảng_cách(u) có giá trị không vượt quá độ dài đường đi ngắn nhất từ nguồn tới u qua tối đa i cung.
Khi i bằng số đỉnh của đồ thị, mỗi đường đi tìm được sẽ là đường đi ngắn nhất toàn cục, trừ khi đồ thị có chu trình âm. Nếu tồn tại chu trình âm mà từ đỉnh nguồn có thể đi đến được thì sẽ không tồn tại đường đi nhỏ nhất (vì mỗi lần đi quanh chu trình âm là một lần giảm trọng số của đường).

Ứng dụng trong định tuyến

Một biến thể phân tán của thuật toán Bellman-Ford được dùng trong các giao thức định tuyến vector khoảng cách, chẳng hạn giao thức RIP (Routing Information Protocol). Đây là biến thể phân tán vì nó liên quan đến các nút mạng (các thiết bị định tuyến) trong một hệ thống tự chủ (autonomous system), ví dụ một tập các mạng IP thuộc sở hữu của một nhà cung cấp dịch vụ Internet (ISP).
Thuật toán gồm các bước sau:

1. Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự chủ và lưu trữ thông tin này trong một bảng.
2. Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận.
3. Khi một nút nhận được các bảng thông tin từ các nút lân cận, nó tính các tuyến đường ngắn nhất tới tất cả các nút khác và cập nhật bảng thông tin của chính mình.

Nhược điểm chính của thuật toán Bellman-Ford trong cấu hình này là

• Không nhân rộng tốt
• Các thay đổi của tô-pô mạng không được ghi nhận nhanh do các cập nhật được lan truyền theo từng nút một.
• Đếm dần đến vô cùng (nếu liên kết hỏng hoặc nút mạng hỏng làm cho một nút bị tách khỏi một tập các nút khác, các nút này vẫn sẽ tiếp tục ước tính khoảng cách tới nút đó và tăng dần giá trị tính được, trong khi đó còn có thể xảy ra việc định tuyến thành vòng tròn)

Read more »

Thuật toán tìm đường Dijkstra

Đây là một thuật toán liên quan đến lý thuyết đồ thị, bản đồ, và trong viễn thông thì liên quan đến việc tìm đường ngắn nhất trong mạng. Code ví dụ trong cntt thì nhan nhản trên mạng, bạn nào học cntt mà cần thì tự search nhé.
Về cơ bản thì có thể diễn giải thế này :

• Từ nguồn tới chính nó thì có khoảng cách =0
• Từ các nút kề nguồn thì chọn nút có khoảng cách nhỏ nhất cập nhật vào danh sách đã tìm được đường kèm khoảng cách đến nguồn.
• Quét các nút còn lại , các nút này xem kề nút nào, nếu có kề các nút trong tập hợp danh sách đã biết được đường thì tính xem đường về đích là nhiêu, còn nếu không thì coi như bằng vô cùng. Sau đó trong các nút mới tìm được đường thì chọn nút có đường ngắn nhất cho vào danh sách.
• Cứ làm thế đến khi các nút đều vào danh sách đã tìm được đường thì thôi hoặc đến nút cần đến thì thôi

Ví dụ tí cho dễ hiểu, hình này mình chụp từ slide môn mạng viễn thông

• Theo đồ thị trên thì đến 1 có D3 gần nhất, lần quét đầu tiên cho D3 vào danh sách {1} -> {1,3} đó, các nút D5 D6 không liên hệ với tập hợp biết đường (hiện là {1}) nên cho là vô cùng.
• Tiếp với các nút còn lại thấy D2 liên hệ với D1 có khoảng cách là 3 là ngắn nhất, tống vào, danh sách tìm được đường thêm vào thành {1,2,3}.
• Quét tiếp, thấy D6 liên hệ với D3 có khoảng cách 1, D3 liên hệ nguồn có khoảng cách 2 -> D6 tới nguồn có khoảng cách là 3, ngắn nhất trong lần quét này, cập nhật tiếp. D6 chỉ cần lưu quãng đường và nút sẽ chuyển tiếp D3 thôi, vì khi đến D3, D3 sẽ có dữ liệu để đến đích rồi.
• Cứ thế đến hết.

Theo wiki :

Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm.

Bài toán
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.

Thuật toán
Thuật toán Dijkstra có thể mô tả như sau:
Ta quản lý một tập hợp động S. Ban đầu S={s}.
Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.
Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa.
Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta dừng lại khi đỉnh t được bổ sung vào tập S.
Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính đúng đắn của thuật toán. Khi chứng minh tính đúng đắn của thuật toán, chúng ta phải dùng đến tính chất này.

Chứng minh
Ý tưởng của chứng minh như sau.
Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.
Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.
Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy.
Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các cạnh không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ đường đi, và do đó có giá trị bé hơn d[v]. Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh.

Read more »

MARCH (Media Access with Reduced Handshake)

Sự cải tiến bắt đầu từ MACA -> MACAW (nhiều bản tin quá) -> MACA-BI (yêu cầu ước lượng chính xác lưu lượng phát) -> cải tiến ra MARCH.
MARCH là giao thức dạng máy thu khởi đầu như MACA-BI nhưng MARCH này không cần phải ước lượng.
Ở lần truyền đầu tiên gói RTS được sử dụng chỉ trong gói đầu tiên. Từ gói thứ 2 trở đi chỉ dùng CTS .

Read more »

MACA-BI (MACA By Invitation)

Một loại MACA cải tiến khác ngoài MACAW
Ưu điểm của loại này là giảm số gói điều khiển hơn so với MACAW. Đặc điểm của nó là sẽ gửi tín hiệu RTR (ready to receive) cho máy phát kèm khoảng thời gian cho phép truyền.
Ở lớp thì mình học cái này chỉ lướt qua nên không biết nhiều lắm (trong vở chép 2 dòng), có 1 chú ý là hiệu suất phụ thuộc vào khả năng ước lượng của máy thu cho phép truyền.

Read more »

Hành trình mạng không dây: Từ Wi-Fi đến WiMax

Mạng không dây là một trong những bước tiến lớn nhất của ngành máy tính. Năm ngoái, hàng chục triệu thiết bị Wi-Fi đã được tiêu thụ và dự báo năm nay sẽ có khoảng 100 triệu người sử dụng. Con đường phát triển của công nghệ này từ quy mô hẹp ra phạm vi lớn thực ra mới chỉ bắt đầu cách đây 5 năm.

Sự khởi đầu

Năm 1985, Ủy ban liên lạc liên bang Mỹ FCC (cơ quan quản lý viễn thông của nước này), quyết định “mở cửa” một số băng tần của dải sóng không dây, cho phép sử dụng chúng mà không cần giấy phép của chính phủ. Đây là một điều khá bất thường vào thời điểm đó. Song, trước sự thuyết phục của các chuyên viên kỹ thuật, FCC đã đồng ý “thả” 3 dải sóng công nghiệp, khoa học và y tế cho giới kinh doanh viễn thông.

Ba dải sóng này, gọi là các “băng tần rác” (900 MHz, 2,4 GHz, 5,8 GHz), được phân bổ cho các thiết bị sử dụng vào các mục đích ngoài liên lạc, chẳng hạn như lò nướng vi sóng sử dụng các sóng vô tuyến radio để đun nóng thức ăn. FCC đã đưa các băng tần này vào phục vụ mục đích liên lạc dựa trên cơ sở: bất cứ thiết bị nào sử dụng những dải sóng đó đều phải đi vòng để tránh ảnh hưởng của việc truy cập từ các thiết bị khác. Điều này được thực hiện bằng công nghệ gọi là phổ rộng (vốn được phát triển cho quân đội Mỹ sử dụng), có khả năng phát tín hiệu radio qua một vùng nhiều tần số, khác với phương pháp truyền thống là truyền trên một tần số đơn lẻ được xác định rõ.

Hợp nhất tiêu chí

Dấu mốc quan trọng cho Wi-Fi diễn ra vào năm 1985 khi tiến trình đi đến một chuẩn chung được khởi động. Trước đó, các nhà cung cấp thiết bị không dây dùng cho mạng LAN như Proxim và Symbol ở Mỹ đều phát triển những thiết sản phẩm độc quyền, tức là thiết bị của hãng này không thể liên lạc được với của hãng khác. Nhờ sự thành công của mạng hữu tuyến Ethernet, một số công ty bắt đầu nhận ra rằng việc xác lập một chuẩn không dây chung là rất quan trọng. Vì người tiêu dùng khi đó sẽ dễ dàng chấp nhận công nghệ mới nếu họ không còn bị bó hẹp trong sản phẩm và dịch vụ của một hãng cụ thể.

Năm 1988, công ty NCR, vì muốn sử dụng dải tần “rác” để liên thông các máy rút tiền qua kết nối không dây, đã yêu cầu một kỹ sư của họ có tên Victor Hayes tìm hiểu việc thiết lập chuẩn chung. Ông này cùng với chuyên gia Bruce Tuch của Trung tâm nghiên cứu Bell Labs đã tiếp cận với Tổ chức kỹ sư điện và điện tử IEEE, nơi mà một tiểu ban có tên 802.3 đã xác lập ra chuẩn mạng cục bộ Ethernet phổ biến hiện nay. Một tiểu ban mới có tên 802.11 đã ra đời và quá trình thương lượng hợp nhất các chuẩn bắt đầu.

Thị trường phân tán ở thời điểm đó đồng nghĩa với việc phải mất khá nhiều thời gian để các nhà cung cấp sản phẩm khác nhau đồng ý với những định nghĩa chuẩn và đề ra một tiêu chí mới với sự chấp thuận của ít nhất 75% thành viên tiểu ban. Cuối cùng, năm 1997, tiểu ban này đã phê chuẩn một bộ tiêu chí cơ bản, cho phép mức truyền dữ liệu 2 Mb/giây, sử dụng một trong 2 công nghệ dải tần rộng là frequency hopping (tránh nhiễu bằng cách chuyển đổi liên tục giữa các tần số radio, còn gọi là truyền chéo) hoặc direct-sequence transmission (phát tín hiệu trên một dài gồm nhiều tần số, còn gọi là truyền thẳng).

Chuẩn mới chính thức được ban hành năm 1997 và các kỹ sư ngay lập tức bắt đầu nghiên cứu một thiết bị mẫu tương thích với nó. Sau đó có 2 phiên bản chuẩn, 802.11b (hoạt động trên băng tần 2,4 GHz) và 802.11a (hoạt động trên băng tần 5,8 GHz), lần lượt được phê duyệt tháng 12 năm 1999 và tháng 1 năm 2000. Sau khi có chuẩn 802.11b, các công ty bắt đầu phát triển những thiết bị tương thích với nó. Tuy nhiên, bộ tiêu chí này quá dài và phức tạp với 400 trang tài liệu và vấn đề tương thích vẫn nổi cộm. Vì thế, vào tháng 8/1999, có 6 công ty bao gồm Intersil, 3Com, Nokia, Aironet (về sau được Cisco sáp nhập), Symbol và Lucent liên kết với nhau để tạo ra Liên minh tương thích Ethernet không dây WECA.

Tìm một tên gọi phù hợp

Mục tiêu hoạt động của tổ chức WECA là xác nhận sản phẩm của những nhà cung cấp phải tương thích thực sự với nhau. Tuy nhiên, các thuật ngữ như “tương thích WECA” hay “tuân thủ IEEE 802.11b” vẫn gây bối rối đối với cả cộng đồng. Công nghệ mới cần một cách gọi thuận tiện đối với người tiêu dùng. Các chuyên gia tư vấn đề xuất một số cái tên như “FlankSpeed” hay “DragonFly”. Nhưng cuối cùng được chấp nhận lại là cách gọi “Wi-Fi” vì nghe vừa có vẻ công nghệ chất lượng cao (hi-fi) và hơn nữa người tiêu dùng vốn quen với kiểu khái niệm như đầu đĩa CD của công ty nào thì cũng đều tương thích với bộ khuếch đại amplifier của hãng khác. Thế là cái tên Wi-Fi ra đời. Cách giải thích “Wi-Fi có nghĩa là wireless fidelity” về sau này người ta mới nghĩ ra. Gần đây, nhiều chuyên gia cũng đã viết bài khẳng định lại Wi-Fi thực ra chỉ là một cái tên đặt ra cho dễ gọi chứ chả có nghĩa gì ban đầu.

Đi vào cuộc sống

Như vậy là công nghệ kết nối cục bộ không dây đã được chuẩn hóa, có tên thống nhất và đã đến lúc cần một nhà vô địch để thúc đẩy nó trên thị trường. Wi-Fi đã tìm được Apple, nhà sản xuất máy tính nối tiếng với những phát minh cấp tiến. “Quả táo” tuyên bố nếu hãng Lucent có thể sản xuất một bộ điều hợp adapter với giá chưa đầy 100 USD thì họ có thể tích hợp một khe cắm Wi-Fi vào mọi chiếc máy tính xách tay. Lucent đáp ứng được điều này và vào tháng 7/1999, Apple công bố sự xuất hiện của Wi-Fi như một sự lựa chọn trên dòng máy iBook mới của họ, sử dụng thương hiệu AirPort. Điều này đã hoàn toàn làm thay đổi thị trường mạng không dây. Các nhà sản xuất máy tính khác lập tức ồ ạt làm theo. Wi-Fi nhanh chóng tiếp cận với người tiêu dùng gia đình trong bối cảnh chi tiêu cho công nghệ ở các doanh nghiệp đang bị hạn chế năm 2001.

Wi-Fi sau đó tiếp tục được thúc đẩy nhờ sự phổ biến mạnh mẽ của kết nối Internet băng rộng tốc độ cao trong các hộ gia đình và trở thành phương thức dễ nhất để cho phép nhiều máy tính chia sẻ một đường truy cập băng rộng. Khi công nghệ này phát triển rộng hơn, các điểm truy cập thu phí gọi là hotspot cũng bắt đầu xuất hiện ngày một nhiều ở nơi công cộng như cửa hàng, khách sạn, các quán café. Trong khi đó, Ủy ban liên lạc liên bang Mỹ FCC một lần nữa thay đổi các quy định của họ để cho phép một phiên bản mới của Wi-Fi có tên 802.11g ra đời, sử dụng kỹ thuật dải phổ rộng tiên tiến hơn gọi là truy cập đa phân tần trực giao OFDM (orthogonal frequency-division multiplexing - còn gọi là ghép kênh chia tần số trực giao) và có thể đạt tốc độ lên tới 54 Mb/giây ở băng tần 2,4 Ghz.

Con đường phía trước

Những người ưa thích Wi-Fi tin rằng công nghệ này sẽ gạt ra lề hết những kỹ thuật kết nối không dây khác. Ví dụ, họ cho rằng các điểm truy cập hotspot sẽ cạnh tranh với các mạng điện thoại di động 3G vốn hứa hẹn khả năng truyền phát dữ liệu tốc độ cao. Tuy nhiên những suy luận như trên đã bị thổi phồng. Wi-Fi chỉ là một công nghệ sóng ngắn và sẽ không bao giờ có thể cung cấp được khả năng bao trùm rộng như mạng di động, nhất là khi các mạng này đang ngày một phát triển mạnh hơn về quy mô nhờ những dịch vụ chuyển vùng (roaming) và các thỏa thuận tính cước liên quốc gia.

Tuy nhiên, chỉ trong một vài năm nữa, thế hệ mạng đầu tiên dựa trên công nghệ mới WiMax, hay gọi theo tên kỹ thuật là 802.16, sẽ ra đời và trở nên phổ dụng. Như chính cái tên của mạng này cho thấy, WiMax chính là phiên bản phủ sóng diện rộng của Wi-Fi với thông lượng tối đa có thể lên đến 70 Mb/giây và tầm xa lên tới 50 km, so với 50 m của Wi-Fi hiện nay. Ngoài ra, trong khi Wi-Fi chỉ cho phép truy cập ở những nơi cố định có thiết bị hotspot (giống như các hộp điện thoại công cộng) thì WiMax có thể bao trùm cả một thành phố hoặc nhiều tỉnh thành giống như mạng điện thoại di động.

Ở thời điểm này, Wi-Fi là công nghệ mạng thống lĩnh trong các gia đình ở những nước phát triển. TV, đầu đĩa, đầu ghi và nhiều thiết bị điện tử gia dụng có khả năng dùng Wi-Fi đang xuất hiện ngày một nhiều. Điều đó cho phép người sử dụng truyền nội dung khắp các thiết bị trong nhà mà không cần dây dẫn. Điện thoại không dây sử dụng mạng Wi-Fi cũng đã có mặt ở các văn phòng nhưng về lâu dài, công nghệ truy cập không dây này có vẻ khó là kẻ chiến thắng trong cuộc đua đường dài trên các thiết bị này. Hiện nay, Wi-Fi tiêu tốn khá nhiều năng lượng của các thiết bị cầm tay và thậm chí ,chuẩn 802.11g không thể hỗ trợ ổn định cho hơn một đường phát video. Và thế là một chuẩn mới, có tên 802.15.3 hay còn gọi là WiMedia, đã được xúc tiến để trở thành chuẩn tầm ngắn cho mạng gia đình tốc độ cao, chủ yếu phục vụ thiết bị giải trí.

Quá trình phát triển của công nghệ Wi-Fi cũng đã cho thấy việc thống nhất cho ra một chuẩn chung có thể tạo nên một thị trường mới. Điều này càng được khẳng định thông qua quyết tâm của các công ty đang xúc tiến chuẩn WiMax. Trước đây các công nghệ mạng không dây tầm xa đều do các công ty lớn thao túng với những chuẩn bản quyền riêng và không cái nào được chấp nhận rộng rãi. Chính nhờ sự thành công của Wi-Fi mà những “người khổng lồ” giờ đây đã hợp lực với nhau để phát triển WiMax, một chuẩn phổ thông dễ tiếp cận đối với người tiêu dùng mà các hãng phát triển hy vọng sẽ giúp mở rộng thị trường và tăng doanh thu. Khó dự báo tương lai của Wi-Fi nhưng chắc chắn nó đã tạo nên một hướng đi cho nhiều công nghệ khác.

Nguồn http://vnexpress.net/gl/vi-tinh/2006/01/3b9e5ba6/

Read more »

PHÂN BIỆT WLAN VÀ LAN

WLANs cũng là một chuẩn trong hệ thống 802. Tuy nhiên việc truyền dữ liệu trong WLAN sử dụng sóng Radio. Trong mạng LAN, dữ liệu được truyền trong dây dẫn. Tuy nhiên đối với người dùng cuối thì giao diện sử dụng chúng là tương tự nhau. Cả WLAN và Wire LAN đều được định nghĩa dựa trên hai tầng Physical và Data Link (trong mô hình OSI). Các giao thức hay các ứng dụng đều có thể sử dụng trên nền tảng LAN và WLAN. Ví dụ như IP, IP Security (IPSec). Hay các ứng dụng như Web, FTP, Mail… Sự khác nhau giữa WLAN và LAN. - WLAN sử dụng sóng radio để truyền dữ liệu tại tầng Physcial. + WLAN sử dụng CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) còn LAN sử dụng công nghệ CSMA/CD (Carrier Sense Multiple Access with Collision Detect). Collision Dectect không thể sử dụng trong mạng WLAN bởi thông tin đã truyền đi không thể lấy lại được do đó chúng không thể có tính năng Collision Detect được. Để đảm bảo gói tin truyền không bị xung đột mạng WLAN sử dụng công nghệ CSMA/CA. Trước khi truyền gửi tín hiệu Request To Send (RTS) và Clear To Send (CTS) để hạn chế xung đột xảy ra.


+ WLAN sử dụng định dạng cho Frame dữ liệu khác với mạng LAN. WLAN bắt buộc phải thêm thông tin Layer 2 Header vào gói tin. - Sử dụng Radio vào việc truyền thông tin sẽ chịu một số vấn đề mà khi sử dụng dây dẫn không mắc phải: + Việc kết nối sẽ chịu ảnh hưởng bởi khoảng cách, do phản xạ sóng nên đôi khi nguồn phát tín hiệu có thể bị thay đổi và có nhiều tín hiệu đến trước đến sau, một card mạng WLAN có thể kết nối tới nhiều mạng WLAN khác nhau. + Do sóng Radio có thể tìm thấy nên việc kết nối và bảo mật trên Wireless LAN cũng là vấn đề không nhỏ. - WLAN sử dụng cho người dùng thường xuyên phải di chuyển trong công ty. - WLAN sử dụng một giải tần sóng Radio nên có thể bị nhiễu nếu một sóng Radio khác có cùng tần số. Tương tự như cơ chế truy cập đường truyền CSMA/CD của mạng có dây (IEEE 802.3), Trong mạng IEEE 802.11 sử dụng cơ chế CSMA/CA. CA có nghĩa là Collition Avoidance khác với CD là Collition Detection trong mạng có dây. Nói như vậy không có nghĩa là CSMA/CD không có cơ chế phát hiện Collition như trong mạng có dây bởi vì đặc thù của thiết bị không dây là haft-duplex (Một khi nó đang nhận thì không thể truyền và nếu đang truyển thì không thể nhận). Trong CSMA/CA có 2 khái niệm là CSMA/CA và CSMA/CA based on MACA CSMA/CA: máy phát sẽ lắng nghe trên môi trường truyền, và khi môi trường truyền rỗi thì nó sẽ tiến hành gửi dữ liệu ra môi trường truyền, còn không nó sẽ sử dụng giải thuật backoff để tiếp tục chờ. Cơ chế này bị giới hạn bởi trường hợp hidden node. Giả sử, có 3 máy A,B,C máy B nằm trong range của A và range của C. Khi A gửi cho B thì C không nhận được tín hiệu trên môi trường truyền, và nếu C cũng gửi cho B thì xảy ra Collition.CSMA/CA based on MACA xuất hiện giải quyết node bằng cách trước khi một máy truyền dữ liệu thì nó sẽ lắng nghe đường truyền, và nếu đường truyền rỗi thì nó sẽ gửi frame RTS (request to send), trong trường hợp này, máy nhận sẽ đáp lại bằng frame CTS (Clear to send), những máy còn lại nếu nhận được 1 trong 2 frame trên thì sẽ tự động tạo ra NAV (Network allocation vector) để ngăn cản việc truyền dữ liệu. Cơ chế CSMA/CA còn được gọi chung là DCF (Distribute Coordination Function) là tiêu chí bắt buộc của chuẩn 802.11, còn có 1 cơ chế khác ít thông dụng hơn là PCF (Point Coordination Function), hiện nay có rất ít thiết bị hỗ trợ cơ chế này (Chỉ áp dụng cho mô hình infrastructure). PCF làm việc tương tự như cơ chế truy cập đường truyền của mạng Tokenring. Theo cơ chế này, PC ( Point Controller) tích hợp trong Access Point làm nhiệm vụ polling cho các station theo 1 schedule và chỉ có station nào được poll thì mới được phép truyền. Cơ chế này thích hợp cho các ứng dụng đòi hỏi tính thời gian thực cao bởi vì nó sẽ làm cho các station tham gia vào mạng đều có cơ hội sử dụng môi trường truyền như nhau.

Nguồn http://www.mangbachkhoa.net/forum/showthread.php?t=9

Read more »

Multiple Access with Collision Avoidance for Wireless (MACAW)

MACAW là sự mở rộng của MACA với trình tự thêm vào là RTS-CTS-DS-DATA-ACK.
DS (Data Sending):
nói với các nút lân cận máy phát nghe thấy RTS nhưng không thấy CTS của máy thu (do nút ẩn nút hiện).
DS để thông báo là RTS-CTS đã ok và đang truyền, do DS phát từ chính nút gửi RTS nên nút nào nghe được RTS thì cũng nghe được DS, còn nếu nút lân cận không nghe được CTS và không dùng DS này thì sẽ chẳng biết là truyền có được hay không.
Đấy chính là sự cải tiến.

Read more »

Truyền dẫn kênh chia sẻ

Ở đây nói đến là truyền dẫn trên kênh chia sẻ HS-DSCH trong HSDPA 3.5G

Không giống như WCDMA sử dụng mã trải phổ biến thiên để thay đổi tốc độ, HSDPA sử dụng mã trải phổ cố định SF= 16, việc thay đổi và phân bố tài nguyên mã dựa trên số lượng mã được cấp và phân quyền download trên bao nhiêu khe thời gian.
Việc huy động tài nguyên hệ thống cho một người sử dụng cao nhất có thể là cấp 15/16 mã và truyền trên mọi khe thời gian, khi đó hầu hết tài nguyên hệ thống có thể được cung cấp cho mội người, do đó mà HSDPA có thể đẩy tốc độ lên đến 14.4 Mbps. Sở dĩ không cung cấp cả 16 mã vì cần một lượng tài nguyên cho báo hiệu, điều khiển.

Read more »

Multiple Access with Collision Avoidance (MACA)

Đây là một giao thức MAC (media access control) cho mạng không dây để tránh được hiện tượng nút ẩn và nút hiện.

Ý tưởng là so với các loại giao thức MAC khác dùng cho mạng có dây chỉ truyền luôn, hỏng truyền lại hay là cảm nhận sóng mang rồi mới truyền thì trong môi trường vô tuyến phức tạp hơn, phải xin "cấp phép" trước rồi mới truyền.
Khi một nút muốn truyền, nó sẽ gửi tín hiệu yêu cầu gửi (RTS - Request to Send) với độ dài của khung cần gửi.
Nếu máy thu cho phép truyền nó sẽ gửi lại tín hiệu Clear To Send với độ dài khung nó cho phép nhận.

Các trạm xung quanh nghe được RTS thì sẽ không thu phát tín hiệu trong khoảng thời gian truyền cho đến khi truyền xong thì thôi (căn cứ theo độ dài trong CTS)

Các thủ tực khi gửi trong MACA giữa 2 trạm là :
A -> B : RTS
B -> A : CTS
A -> B : truyền data

Read more »

Thư viện mô phỏng CML (Coded Modulation Library) trong Matlab

Vừa bảo vệ đồ án xong, thấy các thày ok chấp nhận cái này (dù dùng mã nguồn mở và sửa 1 tí thôi chứ không hùng hục từ đầu như nhiều thằng khủng).
Nói chung thư viện này dùng để minh họa lý thuyết khá tốt.
Đây là những gì thư viện này hỗ trợ:

The toolbox contains support for the following:

• Rate 1/n convolutional codes with log-MAP, max-log-MAP, constant-log-MAP, and linear-log-MAP soft-in/soft-out SISO decoding, and Viterbi soft-in/hard-out decoding.
• Tail-biting convolutional codes.
• Two types of convolutional turbo codes (CTCs): (1) binary turbo codes with terminated trellises; (2) duo-binary tail-biting turbo codes.
• Block turbo codes (BTCs).
• Low density parity check (LDPC) codes, both decoding and encoding (encoding limited to certain types of LDPC codes).
• Puncturing and rate-matching to change the base code rate to a desired rate.
• log-MAP (APP) and Viterbi decoding of binary cyclic block codes (Golay, Hamming, etc).
• Arbitrary complex modulation formats: BPSK, QPSK, M-ary PSK, QAM, APSK, with SISO demodulation.
• FSK modulation with multiple tones, arbitrary modulation index (orthogonal or nonorthogonal), and either coherent or noncoherent demodulation.
• Iterative demodulation and decoding, i.e. bit interleaved coded modulation with iterative decoding (BICM-ID).
• Channel types: AWGN, fully-interleaved (ergodic) Rayleigh fading, or block Rayleigh fading.
• Monte Carlo computation of modulation constrained channel capacity (in AWGN and ergodic fading) and information outage probability (in block fading).
• Calculation of throughput of hybrid-ARQ systems.
• Generation of s-random (spread) interleaver and interleavers conforming to UMTS, LTE, cdma2000, CCSDS,  IEEE 802.16 and DVB-RCS standards.
• Ability to run on a grid computer using the Frontier Compute Engine

While the system is generic, the following standards are incorporated as examples:

• IEEE 802.16e (mobile WiMax) tail-biting convolutional code.
• IEEE 802.16e (mobile WiMax) convolutional turbo code (CTC).
• IEEE 802.16e (mobile WiMax) block turbo code (BTC).
• IEEE 802.16e (mobile WiMax) LDPC code.
• DVB-RCS turbo code. 
• DVB-S2 LDPC code.
• UMTS (WCDMA) turbo code.
• HSDPA hybrid-ARQ using a rate-matched UMTS turbo code and QPSK/16-QAM modulation.
• LTE turbo code.
• CCSDS turbo code.
• cdma2000 turbo code.

Nói chung thì sử dụng thư viện này khá là dễ, vào matlab, truy cập đến thư viện, chạy file cmlstartup để nó khởi động,  nếu là các thành phần có sẵn thì chỉ cần chạy ví dụ :

[sim_param, sim_state] = Cmlsimulate('HsdpaScenarios', [1 2 3 4]);
[sim_param, sim_state] = Cmlplot('HsdpaScenarios', [1 2 3 4]);

cái 1 2 3 4 là các trường hợp mô phỏng trong HSDPA với các tham số ở trong thư mục scenarios file HsdpaScenarios.

Các bạn khi down chương trình về thì vào thư mục documentation sẽ thấy có mấy file hướng dẫn.

Ngoài ra thì ở thư mục demo có 1 file hướng dẫn sử dụng thư viện để tính thông lượng HSDPA với các trường hợp, mình chỉnh sửa để nó mô phỏng với nhiều trường hợp và vẽ đồ thị với các trường hợp đó.

Chúc các bạn áp dụng thư viện tốt để phục vụ mục đích đồ án hay để minh họa lý thuyết nào đó mà không cần học quá nhiều về matlab

Link http://www.iterativesolutions.com/Matlab.htm

Read more »