diff --git a/include/ndn-cpp/interest.hpp b/include/ndn-cpp/interest.hpp
index 17b9b67..e55a554 100644
--- a/include/ndn-cpp/interest.hpp
+++ b/include/ndn-cpp/interest.hpp
@@ -132,8 +132,13 @@
   Milliseconds 
   getInterestLifetime() const { return interestLifetime_; }
 
+  /**
+   * @brief Get Interest's nonce
+   *
+   * If nonce was not set before this call, it will be automatically assigned to a random value
+   */
   uint32_t
-  getNonce() const { return nonce_; }
+  getNonce() const;
     
   void
   setName(const Name& name) { name_ = name; }
@@ -196,7 +201,7 @@
   bool mustBeFresh_;
   int scope_;
   Milliseconds interestLifetime_;
-  uint32_t nonce_;
+  mutable uint32_t nonce_;
 
   mutable Block wire_;
 };
diff --git a/src/interest.cpp b/src/interest.cpp
index 0c77d88..85ce0c1 100644
--- a/src/interest.cpp
+++ b/src/interest.cpp
@@ -9,10 +9,24 @@
 #include <ndn-cpp/common.hpp>
 #include <ndn-cpp/interest.hpp>
 
+#include <cryptopp/osrng.h>
+
 using namespace std;
 
 namespace ndn {
 
+uint32_t
+Interest::getNonce() const
+{
+  static CryptoPP::AutoSeededRandomPool rng;
+
+  if (nonce_ == 0)
+    nonce_ = rng.GenerateWord32();
+
+  return nonce_;
+}
+
+
 bool
 Interest::matchesName(const Name &name) const
 {
@@ -121,8 +135,11 @@
         (booleanBlock(Tlv::MustBeFresh));
     }
 
-    selectors.encode();
-    wire_.push_back(selectors);
+    if (!selectors.getAll().empty())
+      {
+        selectors.encode();
+        wire_.push_back(selectors);
+      }
   }
 
   // Nonce
diff --git a/tests_boost/test-encode-decode-interest.cpp b/tests_boost/test-encode-decode-interest.cpp
index ddfe03a..ca2ffeb 100644
--- a/tests_boost/test-encode-decode-interest.cpp
+++ b/tests_boost/test-encode-decode-interest.cpp
@@ -28,7 +28,7 @@
   0xe,  0x0,
   0x3,  0x4,  0x79,  0x79,  0x79,  0x79,
   0xc,  0x1,  0x1,
-  0x5,  0x1,  0x0,
+  0x5,  0x1,  0x1,
   0x6,  0x1,  0x1,
   0x7,  0x2,  0x3,  0xe8
 };
@@ -48,6 +48,7 @@
   BOOST_REQUIRE_EQUAL(i.getChildSelector(), 1);
   BOOST_REQUIRE_EQUAL(i.getMustBeFresh(), false);
   BOOST_REQUIRE_EQUAL(i.getExclude().toUri(), "alex,xxxx,*,yyyy");
+  BOOST_REQUIRE_EQUAL(i.getNonce(), 1);
 }
 
 BOOST_AUTO_TEST_CASE (Encode)
@@ -60,6 +61,7 @@
   i.setChildSelector(1);
   i.setMustBeFresh(false);
   i.getExclude().excludeOne("alex").excludeRange("xxxx", "yyyy");
+  i.setNonce(1);
 
   const Block &wire = i.wireEncode();
   BOOST_REQUIRE_EQUAL_COLLECTIONS(Interest1, Interest1+sizeof(Interest1),