Luận văn Tiếp cận đại số cho bài toán đảm bảo tính riêng tư dữ liệu trên mạng cảm ứng không dây

20 CHƯƠNG 3. PHƯƠNG PHÁP ĐỀ NGHN 3.1. Nhận xét về phương pháp Sheng-Li Bên cạnh dữ liệu cần truyền, các nút cảm ứng phải truyền thêm các dữ liệu để chống lại khả năng nút lưu trữ trả lời không đủ câu truy vấn của trạm chính. Thực vậy, giả sử nút cảm ứng thứ i có k dữ liệu phân bố vào p nhãn (tag) trong tập [T1,…,Tq] với q > p thì: (i) nút i phải truyền thêm q - p thông điệp để kiểm tra dữ liệu trong (q-p) nhãn (tag) còn lại là rỗng (ii) hơn nữa, nút i còn phải truyền thêm một số dữ liệu padding khi mã hóa. Vấn đề này làm cho nút cảm ứng tốn chi phí lớn cho truyền thông tin (chi phí truyền thường cao hơn rất nhiều chi phí tính toán) Vấn đề có thể nghiêm trọng hơn khi hệ thống có thể bị tấn công “dần dần” khi nút lưu trữ tự nó/ hoặc bị khống chế để khai thác tính thường trực của dữ liệu trên hệ thống. Với một thuật toán mã hóa khối, kích thước bản mã thường bằng với kích thước bản rõ. Như vậy nếu kích thước bản mã lớn, có thể suy ra kích thước bản rõ lớn, đồng nghĩa với số lượng dữ liệu nhiều. Bên cạnh đó, kích thước giá trị sau khi băm có số bit cố định, nên hoàn toàn xác định được tag nào không có dữ liệu. Hơn nữa, các tag là cố định nên có thể dò ra gần đúng biên của các đoạn dữ liệu (bucket) ứng với các tag. Như vậy, do dữ liệu thường trực trên hệ thống, theo thời gian hoàn toàn có thể suy ra hoặc xấp xỉ được phân phối của dữ liệu thật sự. Khi biết được phân phối, các giá trị min, max, trung bình, phương sai,… hoàn toàn có thể xấp xỉ được, nhất là đối với phân phối đều. Ngoài ra, nút lưu trữ có thể đóng vai trò người dùng, thực hiện câu truy vấn và gửi đến trạm chính (như vậy nút lưu trữ có bản rõ). Trạm chính sẽ gửi yêu cầu đến nút lưu trữ và nút lưu trữ trả về tập các dữ liệu và nhãn tương ứng (như vậy nút lưu trữ có bản mã). Khi đó, nút lưu trữ có thể thực hiện tấn công khi biết bản rõ và bản mã. Vì vậy phương pháp Sheng-Li rủi ro cao với tấn công khi biết bản rõ và bản mã, mà thực ra là tấn công tự điển. 21 Bên cạnh đó, một đặc điểm khác của phương pháp Sheng-Li là: nếu cùng một giá trị xuất hiện nhiều lần, thì các giá trị đó được xem như là các giá trị phân biệt. Từ các hạn chế trên của phương pháp Sheng-Li, chúng tôi muốn đề nghị một hướng cải tiến phương pháp nhằm chống lại tấn công bản rõ/ bản mã, đồng thời đưa ra một hướng tiếp cận khác có thể khắc phục hai hạn chế trên (tuy nhiên hướng tiếp cận này cũng có một số hạn chế nhất định). 3.2. Hướng cải tiến phương pháp Sheng-Li 3.2.1. Mô tả phương pháp đề xuất Trong phương pháp Sheng-Li, các nút cảm ứng trực tiếp mã hóa dữ liệu và gửi bản mã của dữ liệu đến các nút lưu trữ, nên trong trường hợp nút lưu trữ bị khống chế, nó có thể khai thác được các giá trị bản mã đang được lưu thường trực trên nó. Vì vậy, chúng tôi muốn thay đổi giá trị gửi đi từ nút cảm ứng. Giá trị gửi đi sẽ là một giá trị có thể bao gồm trong đó thông tin về giá trị dữ liệu thật sự, và số lần xuất hiện dữ liệu. Hướng tiếp cận của chúng tôi là áp dụng định lý số dư Trung Hoa để tìm ra giá trị đó. Giả sử tại thời điểm t, nút cảm ứng thứ i cần gửi m giá trị sau {d1,d2,…,dm}. Giá trị dj xuất hiện fj lần trong tập {d1,d2,…,dm}. Khi đó, áp dụng định lý số dư Trung Hoa để giải hệ phương trình đồng dư sau có thể tìm được giá trị xj đại diện cho cặp {dj, fj} xj = dj mod mi,1 xj = fj mod mi,2 với mi,1, mi,2 là hai số nguyên tố cùng nhau (điều kiện để hệ có nghiệm duy nhất) chia sẻ giữa nút thứ i và trạm chính. Gọi Di là miền giá trị của dữ liệu ghi nhận ở nút cảm ứng thứ i. Khi đó, để đảm bảo cho hệ có nghiệm với mọi dj thuộc miền Di và với mọi fj, mi,1 và mi,2 cần lớn hơn mọi dj và mọi fj. Nói cách khác mi,1, mi,2 ≥ max(Di) và mi,1, mi,2 ≥ m (m là số lượng dữ liệu cần gửi tại một thời điểm). 22 Các giá trị xj chính là các giá trị bao gồm trong nó thông tin về dữ liệu gốc (dj) và tần số xuất hiện (fj). Nút cảm ứng sau đó thực hiện mã hóa với khóa chia sẻ ki,t (hoặc có thể không cần mã hóa) các giá trị xj và gửi đi kèm với các nhãn (tag). Lưu ý là cách gán nhãn vẫn theo phương pháp Sheng-Li, nghĩa là gán nhãn dựa trên dữ liệu gốc ban đầu. Khi trạm chính nhận được kết quả truy vấn, trạm chính hoàn toàn có thể khôi phục lại các giá trị dj và tần số fj từ các xj, vì mi,1, mi,2 được chia sẻ giữa trạm chính và nút cảm ứng i với mọi i. q Ví dụ: Giả sử D = {1,…,30} được phân hoạch thành các vùng rời nhau (hội các vùng này chính xác là D) [05] và các tag tương ứng như sau: T1 T2 T3 T4 T5 [1, 5] [6, 15] [16, 23] [24, 28] [28, 30] Nút cảm ứng i cần gửi tập dữ liệu gồm 9 giá trị (m=9): {3, 3, 7, 1, 7, 7, 28, 29, 28} Chọn 2 số nguyên tố cùng nhau m1, m2 (nhằm thỏa điều kiện để áp dụng định lý số dư Trung Hoa) với m1, m2 ≥ max(D, m) = max{[1,30],9} = 30. Ví dụ chọn m1 = 31, m2 = 33 Các giá trị 3, 1 nằm trong khoảng [1,5] nên gán nhãn T1, 7 nằm trong [6,15] nên gán nhãn T2, 28 và 29 nằm trong [28,30] nên gán nhãn T5. Theo phương pháp Sheng- Li, dữ liệu cần gửi đi là: t, {T1, {3,3,1}}, {T2, {7,7,7}}, {T3, num(i||3||t)}, {T4, num(i||4||t)}, {T5, {28,28,29}} 23 Các giá trị đại diện xj được tính như sau: Giá trị 3 1 7 28 29 Số lần xuất hiện 2 1 3 2 1 Nhãn T1 T1 T2 T5 T5 Giá trị xj Giải hệ x=3 mod m1 x=2 mod m2 x= x1 Giải hệ x=1 mod m1 x=1 mod m2 x= x2 Giải hệ x=7 mod m1 x=3 mod m2 x= x3 Giải hệ x=28 mod m1 x=2 mod m2 x = x4 Giải hệ x=29 mod m1 x=1 mod m2 x= x5 Dữ liệu thực sự được mã hóa và gửi đi đến nút lưu trữ là các giá trị đại diện: t, {T1, {x1, x2}}, {T2, {x3}}, {T3, num(i||3||t)}, {T4, num(i||4||t)}, {T5, {x4, x5}} Dữ liệu x1 x2 x3 x4 x5 Nhãn (tag) T1 T1 T2 T5 T5 24 3.2.2. Thuật toán Bảng 3-1 Thuật toán cải tiến CRT Thuật toán cải tiến CRT Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng m = số dữ liệu gửi mỗi lần Tập bucket và các tag tương ứng. {B1, T1} … {Bk, Tk} m1, m2: hai số nguyên tố cùng nhau, m1, m2 > max(D), m1, m2 > m m1 -1 mod m2, m2-1 mod m1 Output Các giá trị đại diện và nhãn tương ứng. Thực hiện For x thuộc X f(x) = tan so cua x p = xm2m2 -1 mod m1 + fm1m1 -1 mod m2 (mod m1 m2) Gan nhan cho x End for 25 3.2.3. Phân tích phương pháp đề xuất Sau đây là các nhận xét của chúng tôi về các khác biệt trong hướng tiếp cận dựa vào định lý số dư Trung Hoa (CRT) so với phương pháp Sheng-Li. Để cho dễ theo dõi, chúng tôi tạm gọi tên các giá trị xj được tìm dựa vào định lý số dư Trung Hoa như trên là ‘giá trị đại diện’, và gọi hướng tiếp cận này là hướng tiếp cận CRT. Thứ nhất, theo hướng tiếp cận này, các giá trị được lưu giữ thường trực trên các nút lưu trữ là bản mã của các giá trị đại diện hoặc chính các giá trị đại diện (trường hợp không thực hiện mã hóa). Đồng thời, giá trị đại diện phụ thuộc vào dữ liệu gốc và tần số xuất hiện nên nếu cùng một giá trị, nhưng tại thời điểm t1 dữ liệu có số lần xuất hiện khác với thời điểm t2, thì giá trị đại diện tại thời điểm t1 cũng khác với thời điểm t2. Thứ hai, mỗi giá trị đại diện đã bao gồm thông tin về dữ liệu và tần số xuất hiện dữ liệu đó. Nghĩa là nếu một dữ liệu xuất hiện nhiều lần, dữ liệu đó vẫn chỉ được đặc trưng bởi một giá trị đại diện duy nhất. Như vậy, các giá trị giống nhau được xem như là một giá trị duy nhất (phương pháp Sheng-Li xem các giá trị này như các giá trị phân biệt) và chỉ gửi đi một lần. Nhờ đó, trong trường hợp dữ liệu không rải đều mà tập trung vào một số giá trị, chi phí truyền tải được tiết kiệm đáng kể. Ngược lại, nếu dữ liệu rải đều thì tùy thuộc vào tần số của từng giá trị dữ liệu. Nếu tần số cao thì chi phí giảm so với phương pháp Sheng-Li. Nếu tần số thấp thì chi phí có thể cao hơn. Thông thường, dữ liệu phân phối chuNn, dữ liệu thường tập trung vào các giá trị nằm trong vùng gần đỉnh (vùng có xác suất cao), nên cách này thường có thể giúp cải tiến chi phí đường truyền. Ngoài ra, các ứng dụng mà vấn đề thời gian thực là không quan trong, có thể chủ động kéo dài khoảng thời gian định kỳ (epoch) ra nhằm tích lũy dữ liệu nhiều hơn trước khi gửi đi. Khi đó thì các giá trị dữ liệu có khả năng có tần số xuất hiện cao nên chi phí truyền tải sẽ giảm. Đồng thời, số lần truyền tải giảm (do khoảng thời gian định kỳ tăng) nên chi phí cũng được giảm. Cụ thể, chi phí truyền tải dữ liệu có thể ước lượng như sau: Nếu mỗi giá trị dj thuộc D được biểu diễn bởi b byte thì m1, m2 cần (b+1) byte để biểu diễn, vì m1, m2 ≥ max(D). Giá trị đại diện xj thuộc Zm1×m2 nên 26 mỗi giá trị xj cần 2(b+1) byte. Do đó, nếu tập dữ liệu cần gửi là tập {d1, d2,.., dk} giá trị phân biệt với tần số xuất hiện tương ứng là {f1, f2, …, fk} (lưu ý là f1 + f2 + … + fk = m = số dữ liệu gửi mỗi thời điểm) thì số byte cần để biểu diễn cho k giá trị đại diện tương ứng là 2×k×(b+1) trong khi số byte biểu diễn tập dữ liệu gốc là m×b. Rõ ràng nếu dữ liệu cần gửi chỉ tập trung ở một số giá trị, k sẽ nhỏ hơn hẳn m, khi đó 2×k×(b+1) sẽ nhỏ hơn hẳn m×b. Cuối cùng, tuy có khả năng giảm chi phí truyền tải, hướng tiếp cận này cần tốn chi phí thực hiện giải hệ phương trình đồng dư (gồm hai phương trình) cho mỗi giá trị dữ liệu. Tuy nhiên, giá trị mi,1, mi,2 (ứng với mỗi nút i) là biết trước nên ta có thể lưu giữ luôn các giá trị mi,1-1, m i,2-1 và không cần tính lại mỗi lần giải hệ đồng dư. Khi đó, giả sử mỗi thời điểm t, nút cảm ứng i gửi đi k giá trị thì chi phí để giải các hệ phương trình đồng dư tại nút đó là O(k). Ngoài các khác biệt trên, hướng tiếp cận CRT còn giữ lại các hạn chế khác của phương pháp Sheng-Li, do đó chưa giải quyết được trọn vẹn các tấn công dựa vào tính thường trực của dữ liệu trên nút lưu trữ. Chính vì vậy, trong trường hợp kích thước miền dữ liệu nhỏ, chúng tôi đưa ra một hướng tiếp cận khác, tạm gọi là phương pháp Histogram, có thể tránh được tấn công khai thác vào tính thường trực của dữ liệu. 3.3. Phương pháp Histogram 3.3.1. Mô tả phương pháp Histogram Trong phương pháp Sheng-Li, sau mỗi khoảng thời gian cố định (epoch), nút cảm ứng gửi dữ liệu đã mã hóa, đồng thời gửi các con số định danh (encoding-number) cho các đoạn giá trị (bucket) không có dữ liệu. Biên của các đoạn dữ liệu (bucket) là bí mật. Tuy nhiên, theo thời gian, nút lưu trữ bị khống chế có khả năng dò ra được các biên đó. Vì vậy, một hướng tiếp cận khác, thay vì giấu dữ liệu (bằng mã hóa) và biên 27 của các bucket, chúng tôi công khai miền giá trị dữ liệu, nhưng giấu tần số xuất hiện của từng giá trị. Một giá trị có thể không xuất hiện, xuất hiện một lần, hai lần,… Nói cách khác, trong hướng tiếp cận này, nút cảm ứng sẽ gửi histogram của dữ liệu đi. Để đảm bảo tính bí mật của histogram, chúng tôi sử dụng các giá trị ngẫu nhiên để làm biến đổi histogram. Giá trị ngẫu nhiên được sinh ra bởi hàm băm với tham số thay đổi theo thời gian. Gọi Di là miền rời rạc các giá trị của dữ liệu có khả năng ghi nhận ở nút cảm ứng i. Không mất tính tổng quát, giả sử Di = {1,…,n}. Tại thời điểm t, nút i cần gửi {d1,…,dk} với tần số xuất hiện tương ứng là {f1,…,fk}. Gọi x là giá trị thuộc Di, f(x) là tần số xuất hiện của x trong tập dữ liệu cần gửi ở nút i. h(x) = hash(x||ki,t) nếu x không thuộc {d1,…,dk} h(x) = f(x) + hash(x||ki,t) nếu x thuộc {d1,…,dk}. Trong đó, f(x) là một trong các giá trị thuộc {f1,…,fk} (ký hiệu || là phép kết nối) Có thể gom hai công thức trên thành: h(x) = f(x) + hash(x||ki,t) với f(x) là số lần x xuất hiện trong tập dữ liệu cần gửi đi {d1,…,dk} h(x) được tính với mọi giá trị x thuộc Di. Nút cảm ứng sẽ gửi tất cả các giá trị h(x) này đến nút lưu trữ. q Ví dụ: Với D = {1,…,5}, m = 6. Tập dữ liệu cần gửi là {4, 2, 3, 4, 3, 4}, tương ứng với histogram như sau: 28 Hình 3-1 Ví dụ - Histogram của dữ liệu ban đầu Các giá trị h(x) được tính như sau: h(x) = f(x) + hash(x||ki,t) Giả sử các giá trị hash đã được tính rồi và có giá trị như trong bảng. 1 2 3 4 5 hash(x||ki,t) 4 0 3 2 1 f(x) 0 1 2 3 0 h(x) 4 1 5 5 1 Nút cảm ứng sẽ gửi tập dữ liệu {4,1,5,5,1} đến nút lưu trữ. Histogram của dữ liệu sau khi biến đổi như sau: Hình 3-2 Ví dụ - Histogram của dữ liệu sau khi biến đổi 29 3.3.2. Thuật toán Sau đây là thuật toán theo phương pháp histogram. Thuật toán này nhận các giá trị đầu vào là dữ liệu cần gửi từ một nút cảm ứng đến nút lưu trữ, sau đó thực hiện tính histogram và biến đổi histogram. Kết quả đầu ra là dữ liệu sẽ được gửi đi. Bảng 3-2 Thuật toán histogram-1 Thuật toán histogram - 1 Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng Output Histogram đã được biến đổi {h(d)} = { h(d) = giá trị tần số của d sau khi bị biến đổi } với mọi d thuộc D. Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for For x thuộc X h(x) = h(x) + 1 ; End for Sau đây là hai biến thể của thuật toán Histogram, giúp bảo toàn tính toàn vẹn dữ liệu trong trường hợp nút cảm ứng bị khống chế. 30 Bảng 3-3 Thuật toán histogram-2 Thuật toán histogram - 2 Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng Output Histogram đã được biến đổi: {h(d)} = { h(d) = giá trị tần số sau khi bị biến đổi } với mọi d thuộc D Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for For x thuộc X h(x) = h(x) + (1 + hash(x||ki,t)); End for 31 Bảng 3-4 Thuật toán histogram-3 Thuật toán histogram - 3 Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng Output Histogram đã được biến đổi: {h(d)} = { h(d) = giá trị tần số của d sau khi bị làm nhiễu } với mọi d thuộc D Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for For x thuộc X h(x) = h(x) + 1 ; End for For x thuộc X h(x) = Encki,t(h(x)); End for 3.3.3. Phân tích phương pháp Histogram Sau đây là một số đánh giá của chúng tôi về hướng tiếp cận Histogram. Kết quả trả về cho câu truy vấn khoảng trong phương pháp Sheng-Li là kết quả gần đúng, vì đơn vị nhỏ nhất được trạm chính sử dụng để truy vấn là các tag (ứng với các bucket). Sau khi nhận kết quả trả về từ nút lưu trữ, trạm chính mới thực hiện giải mã dữ liệu để loại bỏ các giá trị thừa. Còn trong phương pháp Histogram, đơn vị nhỏ 32 nhất là các giá trị, nên kết quả truy vấn trả về là kết quả chính xác. Trạm chính chỉ thực hiện biến đổi để đưa về dữ liệu gốc trước khi gửi kết quả cho người dùng. q Ví dụ: Nếu trạm chính cần truy vấn khoảng [3,5] thì các nút lưu trữ sẽ trả về chính xác các giá trị {h(3), h(4), h(5)} Phương pháp Sheng-Li xem các giá trị trùng nhau như các giá trị phân biệt. Trong khi đó, với mỗi giá trị trùng nhau, phương pháp Histogram chỉ cần tăng tần số xuất hiện của giá trị đó lên, cùng với giá trị băm của nó. Vì vậy, tương tự như trong phần nhận xét phương pháp CRT, tính chất này giúp cải tiến chi phí truyền tải. Sau mỗi khoảng thời gian cố định, nút cảm ứng phải gửi toàn bộ histogram đến nút lưu trữ. Nghĩa là ngay cả với giá trị x không có dữ liệu, nút cảm ứng cũng phải gửi giá trị h(x) của nó đi. Còn phương pháp Sheng-Li, mặc dù cũng phải gửi một con số định danh cho các bucket không chứa dữ liệu, nhưng số lượng bucket nhỏ hơn so với số lượng giá trị thực sự, nên chi phí truyền tải sẽ nhỏ hơn. Vì vậy, phương pháp Histogram chỉ thích hợp với lượng dữ liệu nhỏ và số lần truyền thông tin ít, nhưng mỗi lần truyền nhiều dữ liệu cùng lúc. Phương pháp Sheng-Li chủ yếu hỗ trợ câu truy vấn dạng khoảng. Tiếp cận dựa vào histogram cũng có thể trả lời câu truy vấn dạng khoảng nhưng đồng thời cũng hỗ trợ truy vấn count, sum, average. Trạm chính có thể yêu cầu tính tổng toàn bộ các dữ liệu, hoặc chỉ tính tổng các giá trị trong một khoảng giá trị nào đó. Đối với câu truy vấn count, trạm chính khi nhận được kết quả trả về, chỉ cần trừ đi tổng các giá trị hash(x||ki,t) (trạm chính biết được ki,t nên hoàn toàn có thể tính được giá trị băm). Đối với câu truy vấn sum, đầu tiên cần tính các giá trị s(x) = h(x) – hash(x||ki,t) với mọi x, sau đó chỉ cần cộng các giá trị s(x) lại với nhau. Có thể thực hiện mã hóa các giá trị h(x) trước khi gửi đi, nhằm chống lại tấn công vào tính toàn vẹn của giá trị h(x) [ 33 Bảng 3-4 Thuật toán histogram-3]. Một cách khác cũng giúp chống lại tấn công vào tính toàn vẹn của h(x) là thay vì sử dụng công thức tính h(x) như trên, có thể áp dụng công thức sau: h(x) = f(x)×(1+ hash(x||ki,t)) + hash(x||ki,t) [ 34 Bảng 3-3 Thuật toán histogram-2]. Giá trị hash(x||ki,t) được cộng dồn phía sau nhằm tránh trường hợp nếu không có dữ liệu, h(x) = 0 thì sẽ dễ dàng biết được. Theo công thức đó, f(x) = (h(x) - hash(x||ki,t))÷(1+hash(x||ki,t)), nên khi trạm chính nhận được h(x), nếu như (h(x) - hash(x||ki,t)) không chia hết cho (1+ h(x) - hash(x||ki,t)), có thể suy ra giá trị h(x) không toàn vẹn. Mặc dù hạn chế bởi phương pháp Histogram chỉ thích hợp với lượng dữ liệu nhỏ, và số lần truyền thông tin ít, nhưng mỗi lần truyền nhiều dữ liệu cùng lúc, nhưng trên thực tế, trong nhiều ứng dụng các giá trị do nút cảm ứng ghi nhận cũng có miền biến thiên không lớn, không không yêu cầu tính thời gian thực cao (ví dụ: nhiệt độ, chỉ số nước). Trong trường hợp lượng dữ liệu lớn, hoặc ứng dụng yêu cầu thời gian thực, hoặc mỗi lần truyền các dữ liệu phân bố rộng, không tập trung vào một số giá trị, phương pháp Histogram bộc lộ nhiều hạn chế về chi phí truyền tải. Hướng tiếp cận sau đây cũng dựa trên histogram nhưng thông tin truyền đi được giảm kích thước (nên tạm thời chúng tôi gọi là phương pháp Nén Histogram), làm giảm đáng kể chi phí truyền tải. Tuy nhiên, chúng tôi chỉ mới trình bày phương pháp này như là một hướng phát triển trong tương lai, vì hiện tại vẫn còn tồn tại một số vấn đề mà chúng tôi chưa giải quyết được trọn vẹn. 35 3.4. Phương pháp Nén Histogram 3.4.1. Mô tả phương pháp Nén Histogram Giả sử miền giá trị dữ liệu ở tất cả các nút cảm ứng đều như nhau (giả thiết này cũng phù hợp với thực tế vì các nút cảm ứng thường được gắn trong một khu vực hoặc nhiều khu vực để đo cùng một đại lượng quan tâm, chẳng hạn nhiệt độ. Và miền giá trị của đại lượng đó ở các khu vực là hoàn toàn xác định). Không mất tính tổng quát, giả sử miền giá trị dữ liệu là D = {1,2,…,n}, số lượng nút cảm ứng cùng gửi dữ liệu đến nút lưu trữ là l, lần lượt có các định danh là {1,…,l} Phương pháp này sử dụng các đa thức để nén histogram cần gửi đi. Số biến của đa thức bằng lực lượng của miền giá trị dữ liệu (|D| = n). Gọi k là số lượng đa thức sử dụng (k ≤ n), và x = (x1,x2,…,xn) là vec-tơ n thành phần. P1 (x) = a11x1 + a12x2 + … + a1nxn P2 (x) = a21x1 + a22x2 + … + a2nxn … Pk (x) = ak1x1 + ak2x2 + … + aknxn Với bộ hệ số a11 a12 … a1n a21 a22 … a2n … ak1 ak2 … akn trên là ta có thể biểu diễn lại k đa thức gốc. Bộ hệ số này sẽ được chia sẻ giữa các nút cảm ứng và trạm chính. 36 Ký hiệu vec-tơ n thành phần hi = {hi1, hi2, …, hin} là histogram của dữ liệu nút cảm ứng i muốn gửi tới (hij là tần số xuất hiện của giá trị j tại nút i, với 1≤ j ≤ n). Pi1 là giá trị đa thức P1 khi thế giá trị histogram của nút i vào. Pi1 (hi) = a11hi1 + a12hi2 + … + a1nhin … Pik (hi) = ak1hi1 + ak2hi2 + … + aknhin Với hi là vec-tơ n thành phần. Nút cảm ứng i sẽ tính giá trị các đa thức, và gửi đi tập giá trị này {Pi1,…,Pik} đến nút lưu trữ. Khi trạm chính gửi câu truy vấn dữ liệu tại thời điểm t (truy vấn khoảng giá trị, truy vấn count, average hay sum) , nút lưu trữ cộng các giá trị Pi1 lại với nhau (với mọi i), cộng các giá trị Pi2 lại với nhau, …, cộng các giá trị Pik lại với nhau. Ký hiệu P’1,P’2,…,P’n là kết quả cộng dồn. Sau đó nút lưu trữ gửi tập dữ liệu { P’1,P’2,…,P’n} trả về cho trạm chính. Rõ ràng: P’1 =∑Pi1 = a11∑hi1 + a12∑hi2 …+ a1n∑hin = a11h’1 + a12h’2 + … + a1nh’n= P1(h’) … P’ k = ∑Pik =ak1∑hi1 + ak2∑hi2 …+ akn∑hin = ak1h’1 + ak2h’2 + … + aknh’n = Pk(h’) với h’ = (h’1,h’2,…,h’n) là vec-tơ n thành phần và h’1 = ∑hi1 với mọi i, h’2 = ∑hi2 với mọi i, …, h’n = ∑hin với mọi i. Khi nhận được {P’1,P’2,…,P’n}, trạm chính sẽ giải hệ k phương trình n Nn (h’1,…,h’n) như trên. Lưu ý ngoài hệ phương trình trên, trạm chính luôn biết được ràng buộc như sau: h’1 + … + h’n = m×l với l là số nút cảm ứng, m là số lượng giá trị gửi đi mỗi thời điểm t. Ràng buộc này có thể sử dụng để giới hạn lại số nghiệm tìm ra của hệ k phương trình, n Nn (vì k ≤ n, mà hệ này luôn đảm bảo có nghiệm (chính là dữ liệu thực sự) nên hệ có một hoặc nhiều nghiệm). 37 q Ví dụ: Giả sử có l = 4 nút cảm ứng. Số lượng dữ liệu gửi đi mỗi thời điểm là m = 3. Số lượng đa thức sử dụng là k = 2. Hai đa thức sử dụng là: P1 = 2x1 + x2 + 3x3 + 4x4 + 5x5 P2 = 3x1 + 2x2 + x3 + 4x4 + 5x5 Không mất tính tổng quát, giả sử miền giá trị dữ liệu là D = {1,…,n} = {1,..,5} Giả sử dữ liệu ghi nhận được ở các nút cảm ứng lần lượt là: Nút 1: {3, 4, 3} Nút 2: {2, 1, 4} Nút 3: {1, 1, 2} Nút 4: {2, 3, 4} Histogram tương ứng với dữ liệu ở các nút là: Nút 1: h1={h11, h12, h13,h14,h15} = {0,0,2,1,1} Nút 2: h2={h21, h22, h23,h24,h25} = {1,1,0,1,0} Nút 3: h3={h31, h32, h33,h34,h35} = {2,1,0,0,0} Nút 4: h4={h41, h42, h43,h44,h45} = {0,1,1,1,0} Hình 3-3 Ví dụ histogram của các tập dữ liệu 38 Giá trị hai đa thức P1, P2 ứng với histogram dữ liệu ở các nút cảm ứng là: Bảng 3-5 Bảng giá trị đa thức ứng với dữ liệu trong ví dụ Nút 1 P11 = P1(h1) = 2x1 + x2 + 3x3 + 4x4 + 5x5 = 2*0 + 0+ 3*2 + 4*1 + 5*0 = 10 P12 = P2(h1) = 3x1 + 2x2 + x3 + 4x4 + 5x5 = 3*0 + 2*0 + 2 + 4*1 + 5*0 = 6 Nút 2 P21 = P1(h2) = 2x1 + x2 + 3x3 + 4x4 + 5x5 = 2*1 + 1+ 3*0 + 4*1 + 5*0 = 7 P22 = P2(h2) = 3x1 + 2x2 + x3 + 4x4 + 5x5 = 3*1 + 2*1 + 0 + 4*1 + 5*0 = 9 Nút 3 P31 = P1(h3) = 2x1 + x2 + 3x3 + 4x4 + 5x5 = 2*2 + 1+ 3*0 + 4*0 + 5*0 = 5 P32 = P2(h3) = 3x1 + 2x2 + x3 + 4x4 + 5x5 = 3*2 + 2*1 + 0 + 4*0 + 5*0 = 8 Nút 4 P41 = P1(h4) = 2x1 + x2 + 3x3 + 4x4 + 5x5 = 2*0 + 1+ 3*1 + 4*1 + 5*0 = 8 P42 = P2(h4) = 3x1 + 2x2 + x3 + 4x4 + 5x5 = 3*0 + 2*1 + 1 + 4*1 + 5*0 = 7 Các nút cảm ứng gửi các giá trị đa thức P1, P2 tới nút lưu trữ: Nút 1 nút lưu trữ: {10, 6} ; Nút 2 nút lưu trữ: {7, 9} Nút 3 nút lưu trữ: {5, 8} ; Nút 4 nút lưu trữ: {8, 7} Khi trạm chính thực hiện truy vấn, nút lưu trữ sẽ tổ hợp các giá trị đa thức lại (tổ hợp cộng): P’1 = P11 + P21 + P31 + P41 = 10 + 7 + 5 + 8 = 30 P’2 = P12 + P22 + P32 + P42 = 6 + 9 + 8 + 7 = 30 và gửi P’1, P’2 về cho trạm chính. Trạm chính nhận được {P’1, P’2}, sẽ thực hiện giải hệ phương trình sau đây để suy ra histogram của toàn bộ dữ liệu tại thời điểm t: 39 2x1 + x2 + 3x3 + 4x4 + 5x5 = P’1 = 30 3x1 + 2x2 + x3 + 4x4 + 5x5 = P’2 = 30 Ràng buộc về số lượng dữ liệu là: x1 + x2 + x3 + x4 + x5 = m×l = 3×4 = 12 (*) Hệ phương trình trên có các bộ nghiệm như sau: Bảng 3-6 Bộ nghiệm của hệ bất phương trình {0,0,0,0,6} {0,0,0,5,2} {0,2,1,0,5} {0,2,1,5,1} {0,4,2,0,4} {5,5,5,0,0} {0,4,2,5,0} {0,6,3,0,3} {0,8,4,0,2} {0,10,5,0,1} {0,12,6,0,0} {6,0,3,1,1} {1,1,1,1,4} {1,1,1,6,0} {1,3,2,1,3} {1,5,3,1,2} {1,7,4,1,1} {6,2,4,1,0} {1,9,5,1,0} {2,0,1,2,3} {2,2,2,2,2} {2,4,3,2,1} {2,6,4,2,0} {3,1,2,3,1} {3,3,3,3,0} {4,0,2,4,0} {5,1,3,0,2} {5,3,4,0,1} Điều kiện ràng buộc (*) có thể giảm bớt một số lượng lớn nghiệm không thỏa. Kết quả còn lại gồm 4 bộ nghiệm sau: {0 6 3 0 3} ; {1 5 3 1 2} ; {2 4 3 2 1} ; {3 3 3 3 0} Trong đó thực sự chỉ có {3 3 3 3 0} là bộ nghiệm đúng (vì {h11, h12, h13,h14,h15} + {h21, h22, h23,h24,h25} + {h31, h32, h33,h34,h35} + {h41, h42, h43,h44,h45} = {0,0,2,1,1} + {1,1,0,1,0} + {2,1,0,0,0} + {0,1,1,1,0} = {3,3,3,3,0}) Vấn đề đặt ra là làm thế nào trạm chính chỉ tìm được đúng một bộ nghiệm thực sự {3,3,3,3,0}. Hướng giải quyết sẽ được trình bày trong phần [3.4.5. Một giải pháp đề nghị]. 40 3.4.2. Thuật toán Bảng 3-7 Thuật toán Nén Histogram Thuật toán Nén Histogram Input D = miền giá trị của dữ liệu (|D| = n) X = tập dữ liệu cần gửi của nút cảm ứng Ak×n = ma trận hệ số k dòng, n cột (k ≤ n, m với m là số dữ liệu một lần gửi) ứng với k đa thức n Nn số (P1, …, Pk) Output Giá trị của k đa thức P1, …, Pk Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for //Tính histogram For x thuộc X h(x) = h(x) + 1 ; End for h = {h(d) với mọi d thuộc D} là vec-tơ n thành phần //Tính k đa thức For i = 1 to k Pi = Ai × h với Ai là dòng i của ma trận hệ số, h là vec-tơ n thành phần, × là tích vô hướng End for Output P1,….,Pk 41 3.4.3. Phân tích phương pháp Nén Histogram Sau đây là một số đánh giá của chúng tôi về hướng tiếp cận nén histogram. Vì cách tiếp cận này cũng dựa trên các giá trị tần số xuất hiện của dữ liệu, nên chúng tôi chủ yếu so sánh với phương pháp Histogram đã trình bày ở [3.3. Còn các ưu điểm cũng như hạn chế khác so với phương pháp Sheng-Li, phương pháp này giống như phương pháp histogram. Ưu điểm của phương pháp này là khả năng trả lời chính xác mọi câu truy vấn và khả năng cải tiến chi phí truyền tải. Phương pháp histogram gửi toàn bộ histogram bao gồm n giá trị (n là lực lượng của miền giá trị dữ liệu) từ nút lưu trữ về trạm chính, còn phương pháp này, chỉ cần gửi k giá trị (k là số đa thức sử dụng). Hơn nữa, từ nút lưu trữ đến trạm chính, thay vì có k ×l (với l là số nút cảm ứng) dữ liệu cần gửi như trong phương pháp histogram, nhờ vào việc cộng dồn các đa thức, số lượng dữ liệu cần gửi chỉ còn k. Trong trường hợp các câu truy vấn chỉ truy vấn theo thời gian t, hoặc theo một khoảng thời gian, hoặc theo vùng (vùng gồm nhiều nút cảm ứng, khi đó trong vùng có một nút lưu trữ để tiếp nhận tất cả dữ liệu trong vùng gửi về) mà không quan tâm dữ liệu do nút cảm ứng nào gửi tới. Khi đó, các dữ liệu trên cùng một nút lưu trữ chỉ cần phân biệt về thời gian, không phân biệt về nguồn gốc xuất phát từ nút cảm ứng nào. Do đó, nút lưu trữ có thể không cần phải lưu giá trị các đa thức của từng nút cảm ứng mà chỉ cần giữ các giá trị tổ hợp cộng các đa thức. Gọi c1, …, ck là giá trị của k đa thức (hoặc k giá trị tổ hợp cộng các đa thức). P1 = c1 P1 = c2 …. Pk = ck 42 k đa thức tạo thành các vế trái và {c1,…,ck} tạo các vế phải của hệ k phương trình, n Nn số. P1 (x) = a11x1 + a12x2 + … + a1nxn = c1 P2 (x) = a21x1 + a22x2 + … + a2nxn = c2 … Pk (x) = ak1x1 + ak2x2 + … + aknxn = ck Vì hệ chỉ có k phương trình nhưng lại có n Nn số với n ≥ k nên không đảm bảo hệ chỉ có nghiệm duy nhất. Điều kiện ràng buộc về số lượng dữ liệu giúp giảm phần lớn các bộ nghiệm, nhưng vẫn không đảm bảo chỉ còn lại một nghiệm duy nhất. Trong phần [3.4.5. Một giải pháp đề nghị], chúng tôi sẽ đề xuất một phương pháp giải quyết bài toán này. Với hệ k phương trình, n Nn (hệ luôn đảm bảo có ít nhất một bộ nghiệm, chính là giá trị dữ liệu thật sự), điều kiện để số nghiệm ít nhất có thể là: ma trận hệ số (k dòng, n cột) có k cột độc lập tuyến tính. Mặc dù tăng giá trị k sẽ làm giảm số lượng bộ nghiệm, và hệ có nghiệm duy nhất khi k = n, nhưng tăng giá trị k cũng đồng nghĩa với tăng chi phí truyền tải dữ liệu. Vì vậy, vấn đề là chọn giá trị k như thế nào để cân bằng được hai yếu tố: chi phí truyền tải và số lượng bộ nghiệm. Một hướng tiếp cận là dựa vào phân bố xác suất của dữ liệu, chọn k bằng số lượng các giá trị dữ liệu có xác suất xuất hiện lớn, và k cột độc lập tuyến tính ứng với k giá trị dữ liệu có xác suất lớn đó. Ngoài ra, có thể thêm thông tin bổ sung làm điều kiện ràng buộc cho bộ nghiệm của hệ phương trình. Ma trận hệ số được thống nhất giữa các nút cảm ứng và trạm chính. Như vậy, trong trường hợp một nút cảm ứng bị khống chế, ma trận này sẽ bị lộ. Để có thể bảo mật histogram ngay cả khi ma trận hệ số bị lộ, có thể áp dụng cách tiếp cận như trong phương pháp histogram: sử dụng các giá trị ngẫu nhiên để làm biến đổi histogram, sau đó mới áp dụng vào trong đa thức, hoặc cộng thêm một lượng nhiễu vào từng gia trị đa thức 43 3.4.4. Về khía cạnh triển khai Ta thấy, để triển khai phương pháp Nén Histogram, bộ số phải được triển khai trước cho các nút cảm ứng và cho trạm chính. Điều này là khó khả thi khi số lượng hệ số lớn. Để khắc phục giải pháp của ta là sinh ra hệ số khi cần; Nghĩa là, nếu nút thứ i có di1,…,dik dữ liệu tại thời điểm (epoch) t thì ta chỉ cần sinh các hệ số aji1,…,ajik theo một hàm sinh chia sẻ trước giữa các nút với trạm chính. Để đảm bảo mỗi thời điểm (epoch) là một khối dữ liệu khác nhau, nghĩa là để đảm bảo tính ngẫu nhiên của dữ liệu, thay vì truyền tổng aji1+…+ajik của một đa thức j ta cộng thêm một đại lượng uj; mặt khác, để chống các nút bị khống chế, mỗi nút i sẽ cộng thêm giá trị hj=hash(j||kt) với kt là khoá ở thời điểm t (được sinh từ khoá kt-1 ở thời điểm (epoch) t-1và được chia sẻ với trạm chính khoá k0). Như vậy, khối dữ liệu tương ứng với đa thức thứ j là aji1+…+ajik+uj+hj. Đại lượng uj cũng là một đại lượng được phát sinh nhưng có thể phụ thuộc vào khoá kt nếu cần. 3.4.5. Một giải pháp đề nghị Trong phần này, chúng tôi trình bày một giải pháp sinh bộ hệ số sao cho bộ nghiệm tìm được là duy nhất. Để đơn giản hóa, chúng tôi giả sử các nút cảm ứng không gửi các thông tin trùng nhau (trong trường hợp dữ liệu trùng, số bất phương trình cần giải sẽ nhiều hơn nhưng cũng có thể giải được bằng phương pháp như trình bày trong luận văn này). Các bộ hệ số của k đa thức tạo thành một ma trận k dòng, n cột, gọi là ma trận hệ số Ak×n. Vấn đề là làm thế nào xây dựng ma trận hệ số sao cho đảm bảo hệ phương trình tạo bởi k đa thức (vế trái) và giá trị thông tin sau khi nén bằng đa thức (vế phải) chỉ có đúng một nghiệm. Gọi D={1,…,n} là miền giá trị dữ liệu, Ak×n là ma trận hệ số ứng với hệ số của k đa thức, n Nn số với k≤m,n. Dữ liệu cần gửi đi gồm m giá trị không trùng nhau thuộc D, nghĩa là nếu sử dụng vec-tơ n phần tử x=(x1,…,xn) để biểu diễn cho m giá trị dữ liệu 44 đó thì vec-tơ x có đúng m phần tử bằng 1, các phần tử khác bằng 0. Giả sử m phần tử bằng 1 đó là ( )1 2, ,..., md d dx x x ứng với các cột {d1, …, dm} của đa thức. { } { } { } { }1 1, 2,..., : , ; 1, 2,..., ; ,..., 1, 2,..., ; k n ij ij m i j D n A a k m n a N N n d d n d d i j × = = ∈ ≠ ∀ ≠ Ta có: ( ) ( ) 1 2 1 2 1 11 1 1 1 1 1 1 1 1 1 1 1 ... ... ... ... ... m j m j m n n d d d d j m k k kn n kd kd kd kd k j P x a x a x a a a a c P x a x a x a a a a c = =  = + + = + + + = =     = + + = + + + = =  ∑ ∑ Nút cảm ứng sẽ gửi giá trị các đa thức đến cho nút lưu trữ: i,t, {c1,…,ck} Khi trạm chính gửi yêu cầu truy vấn i,t, [a,b] đến nút lưu trữ, nút lưu trữ sẽ gửi trả kết quả {c1,…,ck} về cho trạm chính. Trạm chính nhận được {c1,…,ck}, do biết được bộ hệ số nên hoàn toàn có thể thiết lập lại hệ phương trình: ( ) ( ) 1 2 1 2 1 11 1 1 1 1 1 1 1 1 ... ... (*) ... ... ... m m n n d d d k k kn n kd kd kd k P x a x a x a a a c P x a x a x a a a c  = + + = + + + =    = + + = + + + = Hệ (*) có k phương trình, n Nn số với k<n, và (*) có nghiệm (chính là vec-tơ x biểu diễn cho m giá trị dữ liệu thực sự) nên suy ra hệ có một nghiệm hoặc nhiều nghiệm. Vấn đề đặt ra là làm thế nào phát sinh bộ hệ số (aij) để đảm bảo hệ (*) chỉ có một nghiệm. Trước tiên, chúng tôi rút ra nhận xét sau: 45 Bảng 3-8 Nhận xét về nghiệm của hệ k phương trình, n (n số với k<n Nhận xét: Hệ (*) có nhiều hơn 1 nghiệm ( ) ( ) 1 21 1 1 2 2 21 1 1 1 ,..., ,..., sao cho i=1,...,k: j j m m m m iid id j j d d d d d d a a c = = ∃ = ≠ = ∀ = =∑ ∑ Do (*) luôn chắc chắn có ít nhất một nghiệm, suy ra: (*) có đúng 1 nghiệm ( ) ( ) { } 1 21 1 1 2 2 21 1 1 1 ,..., ,..., , i 1,...,k : (1) j j m m m m id id j j d d d d d d a a = = ∀ = ≠ = ∃ ∈ ≠∑ ∑ Dựa trên nhận xét đó, chúng tôi đề nghị cách sinh bộ hệ số (aij) thỏa (1) như sau: Bảng 3-9 Cách sinh bộ hệ số (aij) cho hệ k phương trình, n (n số Cách sinh bộ hệ số (aij) (i) { } { }i 1,...,k-1 ,j 1,..., n∀ ∈ ∈ : sinh aij ngẫu nhiên (ii) { }, j 1,...,i k n= ∀ ∈ : sinh akj thỏa điều kiện: ( ) ( ) { } 1 2 1 2 1 1 1 2 2 2 1 1 1 1 1 1 ,..., ,..., : 1,...,k-1 , j j j j m m m m m m qd qd kd kd j j j j d d d d d d q a a a a = = = = ∀ = ≠ =   ∀ ∈ = ⇒ ≠    ∑ ∑ ∑ ∑ Cách này giúp giảm chi phí sinh (aij) vì đa số (aij) đều được sinh ngẫu nhiên. Để sinh (akj) (hệ số ứng với phương trình thứ k trong (*)) thỏa (ii) trong [Bảng 3-9 Cách sinh bộ hệ số (aij)], chúng tôi đề nghị phương pháp sau đây: 46 Cách sinh bộ hệ số (akj) cho phương trình thứ k của hệ (*): Điều kiện (ii) trong Bảng 3-9 ( ) ( ) { } 1 2 1 2 1 1 1 2 2 2 1 1 1 1 1 1 ,..., ,..., : 1,...,k-1 , j j j j m m m m m m qd qd kd kd j j j j d d d d d d q a a a a = = = = ∀ = ≠ =   ∀ ∈ = ⇒ ≠    ∑ ∑ ∑ ∑ Tương đương: ( ) ( ) { } 1 2 1 2 1 1 1 2 2 2 1 1 1 1 1 1 ,..., ,..., : 1,...,k-1 , 0 j j j j m m m m m m qd qd kd kd j j j j d d d d d d q a a a a = = = = ∀ = ≠ =   ∀ ∈ = ⇒ − ≠    ∑ ∑ ∑ ∑ Để đơn giản về mặt ký hiệu, đặt bj = akj (với j=1,…n). Như vậy: 1 2 1 2 1 1 1 1 0 0 j j j j m m m m kd kd d d j j j j a a b b = = = = − ≠ ⇔ − ≠∑ ∑ ∑ ∑ 1 2 1 1 0 j j m m d d j j b b = = − ≠∑ ∑ sau khi loại bỏ các giá trị 1jdb và 2jdb thỏa 1 2 j jd d= thì có thể biểu diễn lại như sau: { } { }( )' ' ' 1 1 2 21 1 1 1 0 ; j: ; ,..., ; q ,..., j j m m p q j j j m j m j j b b m m n p q p d d d d = = − ≠ ≤ < ∀ ≠ ∈ ∈∑ ∑ ' ' 1 1 j j m m p q j j b b = = −∑ ∑ có thể được biểu diễn thành tích vô hướng của hai vec-tơ n thành phần như sau: Vec-tơ thứ 1: chỉ gồm các phần tử 0, 1 và -1. Các phần tử nằm ở cột { }'1,..., mp p có giá trị 1, các phần tử nằm ở cột { }'1,..., mq q có giá trị -1, còn lại đều có giá trị 0. Vec-tơ thứ 2: vec-tơ ( )1 2, ,..., nb b b 47 Như vậy, mỗi điều kiện ( ) ( ) { } 1 2 1 2 1 1 1 2 2 2 1 1 1 1 1 1 ,..., ,..., : 1,...,k-1 , 0 j j j j m m m m m m qd qd kd kd j j j j d d d d d d q a a a a = = = = = ≠ =   ∀ ∈ = ⇒ − ≠    ∑ ∑ ∑ ∑ có thể biểu diễn lại bằng điều kiện: tích vô hướng của vec-tơ n thành phần gồm các phần tử {0,1,-1} với vec-tơ ( )1 2, ,...,k k kna a a khác 0. Suy ra toàn bộ các điều kiện được xây dựng trong (ii) Bảng 3-9 có thể biểu diễn bằng điều kiện: Tích của ma trận gồm các dòng tạo bởi các vec-tơ n thành phần gồm các phần tử {0,1,-1} với ( )1 2, ,..., Tk k kna a a khác vec-tơ 0. Trong đó, ma trận {0,1,-1} được xác định bởi các điều kiện xây dựng trong (ii) Bảng 3-9; ( )1 2, ,...,k k kna a a là các giá trị cần phải sinh ra. Để dễ trình bày, chúng tôi gọi ma trận {0,1,-1} là ma trận M. Chúng tôi đề nghị phương pháp sau đây để sinh ra ( )1 2, ,...,k k kna a a khi đã biết ma trận M. Bảng 3-10 Heuristic tìm ( )1 2, ,...,k k kna a a Input: Ma trận M Output: ( )1 2, ,...,k k kna a a Thực hiện: Đặt : αi = số dòng của M có phần tử ở cột thứ i mang giá trị 1, tích của dòng với ( )1 2, ,..., Tk k kna a a khác 0 βi = số dòng của M có phần tử ở cột thứ i mang giá trị 1, tích của dòng với ( )1 2, ,..., Tk k kna a a bằng 0 γ = số dòng của M có tích của dòng với ( )1 2, ,..., Tk k kna a a bằng 0 48 val1 = 2 For i = 1 to n Chọn akj thỏa βj lớn nhất. Nếu có nhiều giá trị akj cùng có βj lớn nhất thì chọn akj với αj nhỏ nhất val2 = val1 While (true) do if (akj = val2) làm giảm γ Gán xj = val2 val1 = val2 Break; end if End while End for Phương pháp này vẫn áp dụng được trong trường hợp khi hệ chỉ có 1 phương trình (k=1), n Nn số. Khi đó, điều kiện cần thỏa khi sinh bộ hệ số sẽ nhiều hơn: ( ) ( ) 1 21 1 1 2 2 21 1 1 1 1 1 ,..., ,..., : 0 j j m m m m d d j j d d d d d d a a = = ∀ = ≠ = − ≠∑ ∑ Do đó ma trận M cũng có nhiều dòng hơn. Tuy nhiên, khi đó ma trận M luôn cố định, không thay đổi theo thời gian. Nếu k>1, hệ số của k-1 phương trình đầu tiên được sinh ngẫu nhiên. Ma trận M phụ thuộc vào các hệ số đã được sinh này, vì vậy tăng tính ngẫu nhiên cho M. Từ nhận xét đó, chúng tôi đề nghị không nên chỉ sử dụng 1 đa thức (k=1) mà nên sử dụng 1<k≤m, n. 49 q Ví dụ: Miền giá trị dữ liệu: D = {1,…,n} = {1,…,5} Số dữ liệu gửi đi mỗi lần truyền: m = 3 Số đa thức sử dụng: k = 2 (k<m, n) P1(x) = a11x1 + a12x2 + a13x3 + a14x4 + a15x5 P2(x) = a21x1 + a22x2 + a23x3 + a24x4 + a25x5 x = (x1,x2,x3,x4,x5) Cần sinh các hệ số 11 12 13 14 15 21 22 23 24 25 a a a a a a a a a a       Phát sinh ngẫu nhiên ( ) ( )11 12 13 14 15 2 1 3 2 1a a a a a = Với ( ) ( ) ( ) ( )1 1 1 1 2 2 2 21 2 3 1 2 3, , 1, 2,3 , , 2,3, 4d d d d d d d d= = ≠ = = : 11 12 13 12 13 14 6a a a a a a+ + = + + = Suy ra điều kiện cần khi sinh ( )11 12 13 14 15a a a a a : 21 22 23 22 23 24 21 24a a a a a a a a+ + ≠ + + ⇔ ≠ Tương tự với các 1 2,d d khác, ta suy ra được các điều kiện sau: 21 24 21 24 22 25 22 25 21 24 23 25 21 24 23 25 21 24 22 23 21 24 22 23 21 22 24 25 21 22 24 25 21 25 22 24 21 25 22 24 0 0 0 0 0 0 a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a ≠ − ≠       ≠ − ≠       + ≠ + + − − ≠ ⇔    + ≠ + + − − ≠       + ≠ + + − − ≠       + ≠ + + − − ≠     50 Các điều kiện trên có thể được biểu diễn lại bởi: ( ) ( ) 21 24 22 25 21 24 23 25 21 22 23 24 25 21 24 22 23 21 22 24 25 21 25 22 24 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 ... 0 0 1 1 1 1 0 1 1 0 1 10 1 1 0 1 10 T T a a a a a a a a a a a a a a a a a a a a a a a a a − ≠  −      − ≠ −       + − − ≠ − − ⇔ × ≠    + − − ≠ − −        − −+ − − ≠       − −+ − − ≠    Nghiệm tìm được là: ( ) ( )21 22 23 24 25 2 3 1 1 1a a a a a = Như vậy hai đa thức được sinh ra là: P1(x) = 2x1 + x2 + 3x3 + 2x4 + x5 P2(x) = 2x1 + 3x2 + x3 + x4 + x5 Để chứng tỏ với hai đa thức này, với mọi giá trị x = (x1,x2,x3,x4,x5) tương ứng với các bộ m=3 dữ liệu khác nhau thì cặp giá trị đa thức (P1, P2) cũng khác nhau, chúng tôi in ra kết quả của các P1(x) và P2(x) với mọi giá trị có thể của x. ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 2 1 2 1 2 1 2 1 2 1 2 1 1 1 1 0 0 P 6, P 6 1 1 0 1 0 P 5, P 6 1 1 0 0 1 P 4, P 6 1 0 1 1 0 P 7, P 4 1 0 1 0 1 P 6, P 4 P 5, P 41 0 0 1 1 P 6, P0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 X X X X X X X X X X =  = =  =  = =   = = =    = = =   = = = ⇒  = ==    ==    =    =     =  2 1 2 1 2 1 2 5 P 5, P 5 P 2, P 4 P 6, P 3                     =   = =   = =    = =  51 q Ví dụ: Miền giá trị dữ liệu: D = {1,…,n} = {1,…,4} Số dữ liệu gửi đi mỗi lần truyền: m = 2 Số đa thức sử dụng: k = 1 (k<m, n) P1(x) = a11x1 + a12x2 + a13x3 + a14x4 + a15x5 Khi đó cần sinh ( )11 12 13 14a a a a thỏa: ( ) ( ) 1 22 21 1 1 2 2 21 2 1 2 1 1 1 1 , , : 0 j j m m d d j j d d d d d d a a = = = = ∀ = ≠ = − ≠∑ ∑ Ma trận M tương ứng với điều kiện trên là: 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 −    −    −   −    −   −    − −   − −    − −  Kết quả tìm ra là: ( ) ( )11 12 13 14 2 3 5 1a a a a = 52 3.5. Thử nghiệm 3.5.1. Mô tả dữ liệu và mục tiêu thử nghiệm Dữ liệu ghi nhận từ 54 nút cảm ứng được thực hiện ở phòng nghiên cứu Intel Berkeley từ 28/04/2004 đến 05/05/2004, do Peter Bodik, Wei Hong, Carlos Guestrin, Sam Madden, Mark Paskin, Romain Thibaux, Joe Polastre và Rob Szewczyk thực hiện, thu thập. Tập tin dữ liệu có khoảng 2,3 triệu giá trị ghi nhận, kích thước tập tin 34MB (đã nén), khoảng 150MB (chưa nén). Cấu trúc tập tin dữ liệu gồm các cột thông tin sau: Bảng 3-11 Cấu trúc dữ liệu thực nghiệm Ngày tháng năm yyyy-mm-dd Giờ phút giây time:hh:mm:ss.xxx Epoch (int) ID của nút cảm ứng (int) Nhiệt độ (real) Độ Nm (real) Ánh sáng (real) Voltage (real) (int: số nguyên, real: số thực) Trên cùng một nút cảm ứng, giá trị epoch được tăng tuyến tính. Hai epoch giống nhau là của hai nút cảm ứng khác nhau tại cùng một thời điểm. Có một số thời điểm bị mất thông tin. Định danh (ID) của các nút cảm ứng từ 1 đến 54; dữ liệu của một số nút có thể bị mất hoặc bị mất một phần. Nhiệt độ được đo theo độ C. Độ Nm là độ Nm tương đối, giá trị từ 0 – 100%. Ánh sáng đo theo đơn vị Lux (1 lux tương ứng với ánh sáng của ánh trăng, 400 ứng với một văn phòng sáng trưng, 100000 lux ứng với ánh sáng mặt trời), điện thế đo theo vol, từ 2 vol đến 3 vol (pin là các cell lithium ion) [21]. Với dữ liệu trên, chúng tôi thực hiện thử nghiệm để minh họa cho các phân tích trong CHƯƠNG 3: (i) Phân bố dữ liệu trước và sau khi biến đổi theo phương pháp Histogram là hoàn toàn khác nhau và không đoán trước được. (ii) Xây dựng ma trận hệ số cho phương pháp Nén Histogram theo heuristic trình bày trong Bảng 3-10. 53 3.5.2. Tiền xử lý dữ liệu Hiện tại tất cả các dữ liệu được lưu trong cùng một tập tin. Đầu tiên chúng tôi thực hiện tiền xử lý dữ liệu như sau: • Xóa các dòng không đủ dữ liệu (mỗi dòng phải có đủ các cột dữ liệu sau: ngày tháng năm, giờ phút giây, thời điểm (epoch), định danh của nút cảm ứng (id), nhiệt độ, độ Nm, ánh sáng, điện thế. • Giả sử ta quan tâm đến dữ liệu về độ Nm, với độ chính xác là 1. Khi đó, ta chỉ giữ lại các cột: ngày tháng, giờ, epoch, định danh của nút cảm ứng (id), độ Nm, và xóa các cột khác đi. • Xóa các dòng có id>54 hoặc id<1 (vì id của nút chỉ từ 1 đến 54). • Xóa các dòng có độ Nm thấp hơn 0 hoặc lớn hơn 100 vì độ Nm có giá trị nằm trong khoảng [0, 100]. • Kiểm tra xem dữ liệu có phải sắp tăng dần theo con số định danh (id) hay không. • Kiểm tra xem dữ liệu có phải sắp tăng dần theo thời điểm (epoch) hay không. • Thời điểm sớm nhất trong tập dữ liệu là khi nào. • Thời điểm lớn nhất trong tập dữ liệu là khi nào. • Tổng số dòng dữ liệu còn lại là bao nhiêu. • Phân bố của dữ liệu về độ Nm Thực hiện tiền xử lý xong chúng tôi có kết quả như sau: • Tổng số dòng dữ liệu còn lại sau khi xóa các dòng không đủ dữ liệu và các dòng không thỏa điều kiện về id hoặc về humidity: 1920908. Kích thước tập tin dữ liệu: 85MB (kích thước tập tin dữ liệu trước khi xử lý là khoảng 150MB). • Có 52 nút cảm ứng, có id trong khoảng từ 1 đến 54. 54 • Dữ liệu được sắp tăng dần theo id. Trong mỗi id, dữ liệu sắp tăng dần theo epoch, nghĩa là tăng dần theo thời gian. • Thời điểm sớm nhất trong tập dữ liệu: 00:58:46 ngày 28/02/2004 • Thời điểm trễ nhất trong tập dữ liệu: 07:48:44 ngày 03/04/2004 • Phân bố của dữ liệu về độ Nm trước khi tiền xử lý Hình 3-4 Phân bố của dữ liệu thực nghiệm 55 • Phân bố của dữ liệu về độ Nm sau khi tiền xử lý Hình 3-5 Mật độ của dữ liệu thực nghiệm Hình 3-6 Tần số của dữ liệu thực nghiệm Rõ ràng ta thấy các giá trị độ Nm chỉ nằm trong khoảng [0,60], với các giá trị thống kê mổ tả mẫu là: mean = 39.26326, variance = 50.12565, median = 40.4328, standard deviation = 7.079947 56 3.5.3. Kết quả thử nghiệm Dữ liệu được ghi nhận ở các nút cảm ứng và gửi về nút lưu trữ theo khoảng thời gian định kỳ. Chúng tôi thực hiện thử nghiệm với khoảng thời gian định kỳ là 10 phút, và xét 4 lần gửi dữ liệu liên tiếp nhau. Ứng với từng thời điểm (epoch), chúng tôi lấy tất cả các dữ liệu và thực hiện: • Vẽ histogram ứng với dữ liệu lấy được, ứng với cột bên trái của các hình vẽ sau đây. • Thực hiện biến đổi phân phối của dữ liệu lấy được theo phương pháp Histogram. Hàm băm sử dụng khi thực hiện biến đổi là SHA1, tuy nhiên chỉ sử dụng 3 byte đầu nên tính ngẫu nhiên không cao. Sau đó vẽ histogram ứng với dữ liệu đã biến đổi, ứng với cột bên phải của các hình vẽ sau đây. 57 Hình 3-7 Phân bố dữ liệu trước và sau khi áp dụng phương pháp Histogram với khoảng thời gian định kỳ là 10 phút 58 Với khoảng thời gian định kỳ là 60 phút, kết quả được thể hiện trong hình vẽ sau: Hình 3-8 Phân bố dữ liệu trước và sau khi áp dụng phương pháp Histogram với khoảng thời gian định kỳ là 60 phút 59 Như vậy, phân bố của dữ liệu sau khi biến đổi không giúp suy đoán ra được phân bố của dữ liệu gốc ban đầu. Ngoài ra, chúng tôi cũng cài đặt heuristic tìm hệ số của đa thức thứ k khi biết ma trận M tương ứng với các điều kiện ràng buộc.