Giao Thức Mac Dựa Trên Đa Truy Cập Phân Chia Theo Thời Gian

Hình 2.9. Minh họa ưu tiên gửi khi bộ đệm đầy

Tuy nhiên, phải cẩn thận khi sử dụng giải pháp này, nó nguy hiểm trong trường hợp tải cao khi dạng truyền thông không phải là đẳng hướng. Khi những tất cả nút trong một mẫu truyền thông đa hướng bắt đầu giành quyền ưu tiên, cơ hội cho xung đột tăng nhanh chóng. T-MAC sử dụng một giới hạn: một nút có thể chỉ sử dụng giải pháp này khi nó đã mất cạnh tranh ít nhất hai lần. Giới hạn này bảo vệ sự thực hiện trong một mẫu truyền thông đa hướng, trong khi vẫn tăng thông lượng cực đại trong mẫu đơn hướng.

2.5. Giao thức MAC dựa trên đa truy cập phân chia theo thời gian

Mặc dù truy nhập ngẫu nhiên đạt được sự linh hoạt và độ trễ thập cho ứng dụng có tải lưu lượng thấp, lập lịch biểu đúng đắn và thực sự hiệu quả để loại bỏ các nguồn tiêu tốn năng lượng. Đồng thời với lịch biểu hoàn hảo, chỉ có một cặp truyền nhận có thể hoạt động trong một chu kỳ truyền. Do đó sẽ làm giảm xung đột và loại bỏ được nghe nhàn rỗi và nghe lỏm. Sử dụng TDMA là sự lựa chọn tự nhiên cho mạng WSN bởi sóng vô tuyến có thể tắt trong thời gian nhàn rỗi để tiết kiệm năng lượng. Tuy nhiên, để xây dựng lịch biểu TDMA đòi hỏi một chí phí lớn để duy trì việc đồng bộ chính xác giữa các nút cảm biến và trao đổi thông tin cục bộ. Hơn nữa TDMA chỉ định mỗi khe thời gian cho mỗi cảm biến sẽ làm tăng độ trễ đường truyền.

2.5.1. Giao thức CSMA (Đa truy cập cảm biến sóng mang)

CSMA là các giao thức mà trong đó các trạm làm việc lắng nghe đường truyền trước khi đưa ra quyết định làm gì để tương thích với trạng thái đường truyền đó được gọi là giao thức có cảm nhận đường truyền. Nó hoạt động bằng cách: lắng nghe kênh truyền, nếu thấy kênh truyền rỗi thì bắt đầu truyền khung, nếu thấy bận thì trì hoãn lại việc gửi khung. Việc trì hoàn gửi khung này không

Có thể bạn quan tâm!

Xem toàn bộ 97 trang tài liệu này.

thể kéo dài mãi nhưng vấn đề là không biết khi nào đường truyền rỗi nên người ta đã đưa ra ba giải pháp để giải quyết vấn đề này:

- Theo dõi không kiên trì (Non-persistent CSMA): Nếu đường truyền bận, đợi trong một khoảng thời gian ngẫu nhiên rồi tiếp tục nghe lại đường truyền.

- Theo dõi kiên trì (persistent CSMA): Nếu đường truyền bận, tiếp tục nghe đến khi đường truyền rỗi rồi thì truyền gói tin với xác suất bằng 1.

- Theo dõi kiên trì với xác xuất p (P-persistent CSMA): Nếu đường truyền bận, tiếp tục nghe đến khi đường truyền rỗi rồi thì truyền gói tin với xác suất bằng p.

Tuy nhiên, trong CSMA có thể phát sinh một vấn đề như sau: khi một nút vừa phát xong thì một nút khác cũng phát sinh yêu cầu phát khung và bắt đầu nghe đường truyền. Nếu tín hiệu của nút thứ nhất chưa đến nút thứ hai, nút thứ hai sẽ cho rằng đường truyền đang rỗi và bắt đầu phát khung. Khi đó thì xung đột sẽ xảy ra làm cho khung bị mất và toàn bộ thời gian từ lúc xung đột xảy ra cho đến khi phát xong khung là lãng phí. Một vấn đề mới phát sinh nữa là các nút cần phải quan tâm theo dõi xung đột và sau khi phát hiện thì các nút sẽ phải làm gì.

Từ đó người ta xây dựng thêm giao thức mở rộng CSMA/CD (Đa truy cập cảm nhận sóng mang tránh xung đột). Giao thức này cơ bản là giống CSMA với cơ chế lắng nghe trước khi truyền nhưng được cải tiến thêm việc phát hiện xung đột và làm lại sau xung đột. Xung đột có thể được phát hiện bằng cách theo dõi năng lượng hay độ rộng của xung tín hiệu nhận được và đem so sánh với độ rộng của xung vừa truyền đi. Sau khi bị xung đột, nút sẽ chạy một thuật toán gọi là back-off dùng để tính toán lại lượng thời gian nó phải chờ trước khi

gởi lại khung. Lượng thời gian này phải là ngẫu nhiên để các nút sau khi quay lại không bị xung đột với nhau nữa.

CSMA truyền thống không cảnh báo được miền đụng độ và không hiệu quả trong các mạng không dây do có 2 vấn đề chính : vấn đề các nút ẩn và các vấn đề các nút hiện.

Vấn đề các nút ẩn minh hoạ ở hình 2.10(a), ở đây nút A truyền tới nút B. Nút C, nút mà nằm ngoài sóng của A, sẽ cảm nhận thấy kệnh truyền tới nút A đang rảnh và cũng bắt đầu truyền tới nút B. Trong trường hợp này CSMA không phát hiện cảnh báo xung đột được do A và C ẩn với nhau.

Vấn đề nút hiện được minh hoạ bởi hình 2.10 (b). Ở đây, trong khi nút B truyền tới nút A, nút C có một gói dành cho nút D. Tại vì nút C nằm trong vùng phủ sóng của nút B, nó sẽ cảm thấy là đường truyền đang bận và nó sẽ không truyền. Tuy nhiên trên lý thuyết tại vì nút D nằm ngoài vùng phủ sóng của nút B, và A nằm ngoài vùng phủ sóng của C, có 2 phiên truyền mà không đụng độ với nhau. Việc trì hoãn việc truyền bởi C sẽ làm lãng phí băng thông.

Hình 2.10. Minh họa các vấn đề với CSMA trong môi trường không dây. a) nút ẩn, b) nút hiện.

Có hai vấn đề cần quan tâm trong mỗi một cảm biến : ở nút ẩn vấn đề các gói bị đụng độ vì nút gửi không biết có nút khác đang sử dụng đường truyền, trong khi vấn đề của nút hiện có sự lãng phí cơ hội truyền một gói vì nhận biết sai lệch của truyền chống nhiễu. Vấn đề chính của lỗi này là không phải bộ

truyền cảm nhận sóng mang mà là bộ thu. Một số giao tiếp giữa bộ truyền và bộ nhận cần phải có để giải quyết các vấn đề này.

2.5.2. LMAC (Lightweight MAC)

Giao thức LMAC được trình bày tại [6] có mục đích là tối thiểu hóa một số bộ ngắt mạch thu phát để tạo khoảng thời gian ngủ cho các nút cảm biến thích nghi với số lượng lớn lưu lượng dữ liệu. Trong suốt khe thời gian của nó, một nút sẽ truyền thông điệp gồm 2 phần là phần thông điệp điều khiển (Control Message - CM) và phần thông điệp dữ liệu (Data Message - DM). Giữa CM và DM là một khoảng nhỏ cho phép lớp MAC xử lý thông điệp vừa nhận được. Hình dưới dây minh họa khe thời gian LMAC.

Hình 2.11. Khe thời gian LMAC

Lưu ý rằng phần DM không có chiều dài cố định, thậm chí sẽ bỏ qua khi không có dữ liệu nào để truyền. LMAC là giao thức lập lịch. Khi một nút không yêu cầu kết nối thì nó sẽ chuyển sang chế độ chờ (standby) để tiết kiệm năng lượng. Giao thức MAC dựa trên lập lịch có ưu điểm là các nút không bao giờ tiêu tốn năng lượng cho bộ thu phát khi không cần thiết. Mỗi nút khi hoạt động sẽ có rất ít xung đột.

Khung và khe thời gian:

Trong giao thức LMAC thì thời gian được chia thành các khe và số khe được nhóm lại thành một khung. Mỗi khung có chiều dài cố định là số khe thời gian của nó. Số khe thời gian trong một khung nên thích hợp với dự tính của nút mạng hoặc theo yêu cầu của hệ thống. Nguyên tắc lập trình của LMAC rất

đơn giản đó là trong một khung mỗi nút truyền dữ liệu trong khe thời gian của nó. Khi một nút có dữ liệu để truyền, nó sẽ đợi đến khe thời gian tiếp theo của nó thì nó sẽ đánh địa chỉ cho các nút hàng xóm của nó và truyền các gói dữ liệu mà không gây xung đột hay phải có can thiệp khác để truyền.

Để có thể nhận được thông điệp thì các nút còn lại luôn luôn phải lắng nghe tại thời điểm bắt đầu khe thời gian của chúng để tìm hiểu xem liệu chúng có được đánh địa chỉ bằng định danh hay địa chỉ quảng bá. Trong giao thức LMAC, các nút có thể nhận được nhiều thông điệp trên một khung thời gain. Nhưng chỉ cho phép truyền một lần trong một khung.

Thông điệp điều khiển

Thông điệp CM có kích thước cố định và được sử dụng cho vài mục đích. Trong một mạng, thông điệp điều khiển mang ID của bộ điều khiển khe thời gian, nó cho biết khoảng cách đo bằng đơn vị chặng từ nút đó tới cổng của nó cho định tuyến đơn tới một cổng. Nó cho biết địa chỉ nút đích và biết chiều dài của đơn vị dữ liệu. Thông điệp điều khiển có cấu trúc gồm các trường thông tin và kich thước byte như trong bảng 2.1.

Bảng 2.1. Bảng cấu trúc thông điệp điều khiển của LMAC

Trong một khung, dữ liệu điều khiển sẽ được sử dụng để duy trì việc đồng bộ giữa các nút. Cho nên, các nút cũng phải truyền thông điệp điều khiển theo đúng số thứ tự khe thời gian của chúng. Việc truyền dữ liệu điều khiển là

thời điểm thận trọng, mặc dù chúng ta không cho rằng các nút đó đếm thời gian với sự chính xác cao. Tất cả các nút hàng xóm sẽ đặt nỗ lực vào việc nhận thông điệp điều khiển. Khi một nút không được đánh địa chỉ trong thông điệp hoặc thông điệp không được đánh địa chỉ như tất cả các thông điệp khác, nó sẽ tắt nguồn điện để dành thời gian thức tiếp theo. Sau khi hoàn thành việc truyền thông điệp, cả hai nguồn truyền và nhận sẽ tắt đơn vị chức năng truyền. Nếu nút được đánh địa chỉ, nó sẽ nghe đơn vị dữ liệu dù dữ liệu có thể không được đưa vào phần còn lại của khe thời gian. Sau khi hoàn thành việc truyền thông điệp, cả hai nguồn truyền và nhận sẽ tắt đơn vị có chức năng truyền.

Trong giao thức LMAC, mỗi nút chỉ được truyền một thông điệp trong một khung truyền. Hiện tại, giả sử rằng kích thước lớn nhất của đơn vị dữ liệu là 256 bytes, giá trị này sẽ dễ dàng được truyền qua mạng cảm biến không dây. Cần lưu ý rằng một nút có thể nhận được nhiều thông điệp từ nguồn khác nhau để tránh độ trễ cao.

Thông điệp dữ liệu

Phần thông diệp dữ liệu chứa dữ liệu gửi. Phần này không cố định, có chiều dài lớn nhất là 256byte. Nút được đánh địa chỉ sẽ thu thập dữ liệu đến tận khi hoàn thành việc truyền dữ liệu và chuyển mạch sang trạng thái chờ trong khe thời gian của nó.

Thuật toán tìm kiếm khe thời gian

Vấn đề ở đây của LMAC đó là giải quyết việc tìm kiếm khe thời gian rảnh để đảm bảo thực hiện truyền thông. Khi một nút mới tham gia vào mạng, nó cần tìm ra khe thời gian để điều khiển, trước khi nó bắt đầu gửi dữ liệu và tham gia vào mạng. Phương thức tìm kiếm này có thể được thực hiện hoàn toàn cục bộ và phân tán.

Đầu tiên, một nút xác định các khe thời gian đã được dùng bởi các nút hàng xóm của nó. Các khe thời gian không thuộc các khe như trên là khe thời gian “rảnh rỗi”. Thuật toán phân tán sẽ thực hiện như sau: Khi một nút tìm thấy hàng xóm đang truyền dữ liệu trong khe thời gian, nó thêm ‘1’ vào vector bit của các khe đang bị chiếm tại vị trí tương ứng với khe thời gian đó. Ngược lại, các khe thời gian khác là bit 0. Để có được một danh sách các khe thời gian rảnh rỗi, một nút đơn giản chỉ cần “OR” với tất cả các bit của khe bị chiếm được truyền trong khung. Bit 0 trong kết quả nghĩa là khe thời gian được tự do trong 2 chặng và bit 1 là kết quả cho thấy khe thời gian bị chiếm bới hàng xóm

đầu tiên hoặc thứ 2. Điều này để chắc chắn rằng, một khe thời gian chỉ được sử dụng ít nhất sau 3 chặng. Mô tả thuật toán được minh họa như đoạn mã giả phía dưới.

Khi không tìm thấy khe thời gian rảnh rỗi nào thì các nút duy trì trạng thái khởi tạo để theo dõi các khung nhằm tìm ra khe thời gian rảnh rỗi. Trong trạng thái này, các kỹ thuật tiết kiệm năng lượng được dùng để lấy mẫu kênh vô tuyến không dây.

Hình 2.12. Minh họa thuật toán phân tán để tìm kiếm khe thời gian rảnh rỗi của giao thức LMAC

Giả sử trong hình 2.12 thì nút có dấu “?” là nút mới trong mạng. Nó thực hiện việc nghe toàn bộ khung và khám phá ra các khe chưa dùng là nút 1,2,7. Nên nó có khể chọn một trong ba khe đó.

Giải quyết xung đột

Việc giải quyết xung đột được xử lý trong giao thức LMAC đó khi 2 hay nhiều nút cùng chọn một khe thời gian để điều khiển. Điều này xảy ra khi thiết lập mạng hoặc mô hình mạng bị thay đổi do nút di chuyển. Các nút gây ra xung đột thì không thể phát hiện xung đột do chúng gây ra. Chúng cần được thông báo bởi các nút hàng xóm, đơn giản vì khe thời gian bị chúng sở hữu thông báo với mạng là chúng tìm thấy xung đột các khe thời gian trong khung. Khi một nút được thông báo là CM của nó và có thể là DM của nó bị xung đột thì nó sẽ